Expressive power and succinctness of the positive calculus of binary relations

DOI10.1016/j.jlamp.2022.100760OpenAlexW4213002236WikidataQ114013907 ScholiaQ114013907MaRDI QIDQ2141281

Yoshiki Nakamura

Publication date: 25 May 2022

Published in: Journal of Logical and Algebraic Methods in Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jlamp.2022.100760

zbMATH Keywords

expressive powersuccinctnessexistential positive logicthe positive calculus of relations

Mathematics Subject Classification ID

Computer science (68-XX)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the succinctness of some modal logics
• Relation algebras
• The calculus of relations as a foundation for mathematics
• Cylindric algebras. Part II
• Structure and complexity of relational queries
• An until hierarchy and other applications of an Ehrenfeucht-Fraïssé game for temporal logic
• The equational theory of union-free algebras of relations
• The undecidability of FO3 and the calculus of relations with just one binary relation
• An application of games to the completeness problem for formalized theories
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Expressive Power and Succinctness of the Positive Calculus of Relations
• Allegories
• Formula size games for modal logic and μ-calculus
• An n  ! lower bound on formula size
• The succinctness of first-order logic on linear orders
• Introduction to Relation Algebras
• On the complexity of existential positive queries

This page was built for publication: Expressive power and succinctness of the positive calculus of binary relations