Hardness of preorder checking for basic formalisms

DOI10.1016/J.TCS.2011.08.037MaRDI QIDQ650916zbMATH OpenOpenAlexFDO

Authors Laura Bozzelli, Axel Legay, Sophie Pinchinat

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

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

Recommendations

• Hardness of preorder checking for basic formalisms
• Equivalence checking of non-flat systems is EXPTIME-hard.
• Hardness of equivalence checking for composed finite-state systems
• scientific article; zbMATH DE number 1512618
• On the complexity of checking semantic equivalences between pushdown processes and finite-state processes

Cites work

• scientific article; zbMATH DE number 42752 (Why is no real title available?)
• scientific article; zbMATH DE number 1306878 (Why is no real title available?)
• scientific article; zbMATH DE number 1927561 (Why is no real title available?)
• scientific article; zbMATH DE number 1512618 (Why is no real title available?)
• scientific article; zbMATH DE number 2102770 (Why is no real title available?)
• scientific article; zbMATH DE number 795666 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• A Lower Bound on Web Services Composition
• A theory of timed automata
• Alternation
• Behavioural equivalences on finite-state systems are PTIME-hard
• Complexity of equivalence problems for concurrent systems of finite agents
• Deciding bisimilarity is P-complete
• Deciding true concurrency equivalences on safe, finite nets
• Equivalence-checking on infinite-state systems: Techniques and results
• Hardness of equivalence checking for composed finite-state systems
• On the complexity of verifying concurrent transition systems
• Verifying abstractions of timed systems

Cited in

(1)

• Hardness of preorder checking for basic formalisms

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

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