Capturing bisimulation-invariant Ptime

DOI10.1007/3-540-63045-7_30MaRDI QIDQ4376070zbMATH OpenFDO

Authors Martin Otto

Publication date 8 July 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-63045-7_30

zbMATH Keywords

bisimulation equivalencebisimulation-invariant PTIME queriesdescriptive complexity theoryfinite Kripke structurespolynomial timepropositional \(\mu\)-calculus

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Complexity of computation (including implicit computational complexity) (03D15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
• Bisimulation invariant monadic-second order logic in the finite
• Bisimulation Invariant Monadic-Second Order Logic in the Finite
• Bisimulation invariance and finite models

Cited in

(5)

• On logics with two variables
• Linear ordering on graphs, anti-founded sets and polynomial time computability
• Bisimulation-invariant PTIME and higher-dimensional \(\mu\)-calculus
• PDL is the bisimulation-invariant fragment of weak chain logic
• Capturing bisimulation-invariant exponential-time complexity classes

This page was built for publication: Capturing bisimulation-invariant Ptime

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