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

succinctnessexpressive powerexistential positive logicthe 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

• 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?)
• Allegories: decidability and graph homomorphisms
• Cylindric algebras. Part II
• Elements of finite model theory.
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• 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

(2)

• Expressive power and succinctness of the positive calculus of binary relations
• On Positive Relational Calculi

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)