Expressive Power and Succinctness of the Positive Calculus of Relations

DOI10.1007/978-3-030-43520-2_13OpenAlexW3014025647MaRDI QIDQ5098722

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

expressive powersuccinctnessexistential positive logicthe positive calculus of relations

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items

Expressive power and succinctness of the positive calculus of binary relations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• Relation algebras
• The calculus of relations as a foundation for mathematics
• Cylindric algebras. Part II
• Structure and complexity of relational queries
• The equational theory of union-free algebras of relations
• The undecidability of FO3 and the calculus of relations with just one binary relation
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Allegories
• The succinctness of first-order logic on linear orders
• Introduction to Relation Algebras
• On the complexity of existential positive queries
• On the calculus of relations