Hardness of preorder checking for basic formalisms

DOI10.1016/j.tcs.2011.08.037zbMath1227.68072OpenAlexW2001225349MaRDI QIDQ650916

Laura Bozzelli, Sophie Pinchinat, Axel Legay

Publication date: 7 December 2011

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2011.08.037

zbMATH Keywords

computational complexitytimed automatabehavioral preorders and equivalencesnon-flat finite-state systemspreorder and equivalence checking

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hardness of equivalence checking for composed finite-state systems
• Deciding bisimilarity is P-complete
• A theory of timed automata
• Deciding true concurrency equivalences on safe, finite nets
• Complexity of equivalence problems for concurrent systems of finite agents
• Alternation
• Equivalence-checking on infinite-state systems: Techniques and results
• A Lower Bound on Web Services Composition
• On the complexity of verifying concurrent transition systems
• Verifying abstractions of timed systems

This page was built for publication: Hardness of preorder checking for basic formalisms