Expressive Power and Succinctness of the Positive Calculus of Relations

DOI10.1007/978-3-030-43520-2_13MaRDI QIDQ5098722zbMATH OpenOpenAlexFDO

Authors Yoshiki Nakamura

Publication date 30 August 2022

Published in Relational and Algebraic Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-030-43520-2_13

zbMATH Keywords

existential positive logicexpressive powersuccinctnessthe positive calculus of relations

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Expressive power and succinctness of the positive calculus of binary relations
• scientific article; zbMATH DE number 219206
• Reasoning with graphs
• On graph reasoning
• Relational expressive power of constraint query languages

Cites work

• Allegories: decidability and graph homomorphisms
• Cylindric algebras. Part II
• Elements of finite model theory.
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• scientific article; zbMATH DE number 193143 (Why is no real title available?)
• scientific article; zbMATH DE number 1946853 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• scientific article; zbMATH DE number 2201362 (Why is no real title available?)
• Introduction to Relation Algebras
• On the calculus of relations
• On the complexity of existential positive queries
• On the positive calculus of relations with transitive closure
• Partial derivatives on graphs for Kleene allegories
• Relation algebras
• Structure and complexity of relational queries
• The calculus of relations as a foundation for mathematics
• The equational theory of union-free algebras of relations
• The succinctness of first-order logic on linear orders
• The undecidability of FO3 and the calculus of relations with just one binary relation

Cited in

(6)

• Expressive power and succinctness of the positive calculus of binary relations
• On Positive Relational Calculi
• Derivatives on graphs for the positive calculus of relations with transitive closure
• Note on a translation from first-order logic into the calculus of relations preserving validity and finite validity
• Translating three-variable first-order predicate logic to relation algebra, implemented using Z3
• Undecidability of the positive calculus of relations with transitive closure and difference: hypothesis elimination using graph loops

This page was built for publication: Expressive Power and Succinctness of the Positive Calculus of Relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5098722)