Hardness of preorder checking for basic formalisms

DOI10.1016/J.TCS.2011.08.037zbMATH Open1227.68072OpenAlexW2001225349MaRDI QIDQ650916FDOQ650916

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

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
• Publication:4508303
• On the complexity of checking semantic equivalences between pushdown processes and finite-state processes

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)

Cites Work

• A theory of timed automata
• Deciding bisimilarity is P-complete
• Title not available (Why is that?)
• Alternation
• Title not available (Why is that?)
• Title not available (Why is that?)
• Verifying abstractions of timed systems
• On the complexity of verifying concurrent transition systems
• A Lower Bound on Web Services Composition
• Complexity of equivalence problems for concurrent systems of finite agents
• Title not available (Why is that?)
• Title not available (Why is that?)
• Equivalence-checking on infinite-state systems: Techniques and results
• Hardness of equivalence checking for composed finite-state systems
• Deciding true concurrency equivalences on safe, finite nets
• Behavioural equivalences on finite-state systems are PTIME-hard
• Title not available (Why is that?)
• Title not available (Why is that?)

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)