Bisimulation-invariant PTIME and higher-dimensional -calculus

DOI10.1016/S0304-3975(98)00314-4MaRDI QIDQ1960425zbMATH OpenOpenAlexFDO

Authors Martin Otto

Publication date 12 January 2000

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

Full work available at URL https://doi.org/10.1016/s0304-3975(98)00314-4

zbMATH Keywords

bisimulation equivalenceDescriptive complexityFinite model theoryhigher-dimensional \(\mu\)-calculusLogic in computer scienceModal logicModel checkingpolynomial timeProcess logicsstates in finite transition systemsworlds in finite Kripke structures

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Logic in computer science (03B70) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• scientific article; zbMATH DE number 1114351
• Bisimulation invariant monadic-second order logic in the finite
• Model-checking the higher-dimensional modal -calculus
• Bisimulation Invariant Monadic-Second Order Logic in the Finite
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science

Cites work

• A calculus of communicating systems
• A finite model theorem for the propositional \(\mu\)-calculus
• An automata theoretic decision procedure for the propositional mu- calculus
• Bounded variable logics: Two, three, and more
• Canonization for two variables and puzzles on the square
• Deciding bisimilarity is P-complete
• Fixed-point extensions of first-order logic
• scientific article; zbMATH DE number 3898850 (Why is no real title available?)
• scientific article; zbMATH DE number 4041866 (Why is no real title available?)
• scientific article; zbMATH DE number 3716792 (Why is no real title available?)
• scientific article; zbMATH DE number 3482302 (Why is no real title available?)
• scientific article; zbMATH DE number 515737 (Why is no real title available?)
• scientific article; zbMATH DE number 979011 (Why is no real title available?)
• scientific article; zbMATH DE number 1114341 (Why is no real title available?)
• scientific article; zbMATH DE number 1142326 (Why is no real title available?)
• scientific article; zbMATH DE number 952378 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 965572 (Why is no real title available?)
• Infinitary logic and inductive definability over finite structures
• Interpolation, preservation, and pebble games
• Modal correspondence for models
• On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic
• Recurring Dominoes: Making the Highly Undecidable Highly Understandable
• Relational queries computable in polynomial time
• Remarks on Berger's paper on the domino problem
• Results on the propositional \(\mu\)-calculus
• Structure and complexity of relational queries
• The expressive power of fixed-point logic with counting
• The undecidability of the domino problem
• Undecidability results on two-variable logics

Cited in

(10)

• Generalising automaticity to modal properties of finite structures
• The Descriptive Complexity of Parity Games
• Fixed-point definability and polynomial time on chordal graphs and line graphs
• Fixed-Point Definability and Polynomial Time
• scientific article; zbMATH DE number 1114351 (Why is no real title available?)
• Model-checking process equivalences
• The complexity of model-checking tail-recursive higher-order fixpoint logic
• The arity hierarchy in the polyadic -calculus
• Model-checking the higher-dimensional modal -calculus
• Capturing bisimulation-invariant exponential-time complexity classes

This page was built for publication: Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus

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