On logics with two variables

DOI10.1016/S0304-3975(98)00308-9zbMATH Open0948.03023MaRDI QIDQ1960419FDOQ1960419

Martin Otto, Erich Grädel

Publication date: 12 January 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

surveycomplexitymodel checkingdecidabilitymodal logicssatisfiabilitytwo-variable logics

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Decidability of theories and sets of sentences (03B25) Logic in computer science (03B70) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Undecidable theories
• A finite model theorem for the propositional \(\mu\)-calculus
• Remarks on Berger's paper on the domino problem
• A calculus of communicating systems
• Automatic verification of finite-state concurrent systems using temporal logic specifications
• On the Decision Problem for Two-Variable First-Order Logic
• The undecidability of the domino problem
• On languages with two variables
• On model checking for the \(\mu\)-calculus and its fragments
• On the Restraining Power of Guards
• Complexity results for classes of quantificational formulas
• Undecidability results on two-variable logics
• Bounded variable logics: Two, three, and more

Cited In (32)

• Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic
• Data-complexity of the two-variable fragment with counting quantifiers
• Title not available (Why is that?)
• Small substructures and decidability issues for first-order logic with two variables
• On the Restraining Power of Guards
• Title not available (Why is that?)
• Communicating Finite-State Machines and Two-Variable Logic
• A logical approach to locality in pictures languages
• Regular Graphs and the Spectra of Two-Variable Logic with Counting
• First-order definable counting-only queries
• Expressive power of ``now and ``then operators
• A Note on C² Interpreted over Finite Data-Words
• Complexity of two-variable dependence logic and IF-logic
• Title not available (Why is that?)
• Two-Variable Separation Logic and Its Inner Circle
• Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs
• The guarded fragment with transitive guards
• Group announcement logic
• Model Checking Games
• A Decidable Fragment of First Order Modal Logic: Two Variable Term Modal Logic
• Comparing the succinctness of monadic query languages over finite trees
• QUESTIONS IN TWO-DIMENSIONAL LOGIC
• Graphs Identified by Logics with Counting
• Title not available (Why is that?)
• On Preservation Theorems for Two-Variable Logic
• Two variable first-order logic over ordered domains
• Two-Variable Logic over Countable Linear Orderings
• Quantitative Logic Reasoning
• Complexity of the two-variable fragment with counting quantifiers
• Undecidability of First-Order Intuitionistic and Modal Logics with Two variables
• Title not available (Why is that?)
• An event-based fragment of first-order logic over intervals

This page was built for publication: On logics with two variables

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