Bisimulation-invariant PTIME and higher-dimensional -calculus

DOI10.1016/S0304-3975(98)00314-4zbMATH Open0930.03030OpenAlexW1981996395MaRDI QIDQ1960425FDOQ1960425

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

polynomial timebisimulation equivalenceModel checkingFinite model theoryDescriptive complexityModal logicLogic in computer sciencehigher-dimensional \(\mu\)-calculusProcess logicsstates in finite transition systemsworlds in finite Kripke structures

Mathematics Subject Classification ID

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

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?)
• Fixed-point extensions of first-order logic
• Deciding bisimilarity is P-complete
• A finite model theorem for the propositional \(\mu\)-calculus
• Remarks on Berger's paper on the domino problem
• On the expressive completeness of the propositional mu-calculus with respect to monadic second order logic
• A calculus of communicating systems
• Results on the propositional \(\mu\)-calculus
• The undecidability of the domino problem
• An automata theoretic decision procedure for the propositional mu- calculus
• Canonization for two variables and puzzles on the square
• Recurring Dominoes: Making the Highly Undecidable Highly Understandable
• Relational queries computable in polynomial time
• Interpolation, preservation, and pebble games
• Undecidability results on two-variable logics
• Structure and complexity of relational queries
• Infinitary logic and inductive definability over finite structures
• Modal correspondence for models
• Bounded variable logics: Two, three, and more
• The expressive power of fixed-point logic with counting

Cited In (8)

• The Descriptive Complexity of Parity Games
• Title not available (Why is that?)
• The Complexity of Model-Checking Tail-Recursive Higher-Order Fixpoint Logic
• Title not available (Why is that?)
• Generalising automaticity to modal properties of finite structures
• Fixed-Point Definability and Polynomial Time on Chordal Graphs and Line Graphs
• Model-checking process equivalences
• Fixed-Point Definability and Polynomial Time

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)