Hardness of preorder checking for basic formalisms
From MaRDI portal
Publication:650916
DOI10.1016/j.tcs.2011.08.037zbMath1227.68072MaRDI 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
computational complexity; timed automata; behavioral preorders and equivalences; non-flat finite-state systems; preorder and equivalence checking
68Q60: Specification and verification (program logics, model checking, etc.)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Cites Work
- 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
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item