Equivalence-checking on infinite-state systems: Techniques and results

ANTONÍN KUČERA; PETR JANČAR

doi:10.1017/S1471068406002651

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

The paper presents a selection of recently developed and/or used techniques for equivalence-checking on infinite-state systems, and an up-to-date overview of existing results (as of September 2004).

Crossref Citations

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Jančar, Petr 2008. Developments in Language Theory. Vol. 5257, Issue. , p. 56.

Jančar, Petr and Srba, Jivří 2008. Undecidability of bisimilarity by defender's forcing. Journal of the ACM, Vol. 55, Issue. 1, p. 1.

van Glabbeek, Rob and Ploeger, Bas 2008. Computer Aided Verification. Vol. 5123, Issue. , p. 517.

Crafa, Silvia Ranzato, Francesco and Tapparo, Francesco 2009. Saving Space in a Time Efficient Simulation Algorithm. p. 60.

Kučera, Antonín and Mayr, Richard 2010. On the complexity of checking semantic equivalences between pushdown processes and finite-state processes. Information and Computation, Vol. 208, Issue. 7, p. 772.

Bozzelli, Laura Legay, Axel and Pinchinat, Sophie 2010. Logic for Programming, Artificial Intelligence, and Reasoning. Vol. 6355, Issue. , p. 119.

Brázdil, Tomáš Jančar, Petr and Kučera, Antonín 2010. Automata, Languages and Programming. Vol. 6199, Issue. , p. 478.

Aceto, Luca Ingolfsdottir, Anna and Srba, Jirí 2011. Advanced Topics in Bisimulation and Coinduction. p. 100.

Stirling, Colin 2011. Advanced Topics in Bisimulation and Coinduction. p. 173.

Bozzelli, Laura Legay, Axel and Pinchinat, Sophie 2011. Hardness of preorder checking for basic formalisms. Theoretical Computer Science, Vol. 412, Issue. 49, p. 6795.

Kiefer, Stefan 2013. BPA bisimilarity is EXPTIME-hard. Information Processing Letters, Vol. 113, Issue. 4, p. 101.

Benedikt, Michael Goller, Stefan Kiefer, Stefan and Murawski, Andrzej S. 2013. Bisimilarity of Pushdown Automata is Nonelementary. p. 488.

Francesco, Nicoletta de Lettieri, Giuseppe Santone, Antonella and Vaglini, Gigliola 2014. GreASE. ACM Transactions on Software Engineering and Methodology, Vol. 23, Issue. 3, p. 1.

Yin, Qiang Fu, Yuxi He, Chaodong Huang, Mingzhang and Tao, Xiuting 2014. Automata, Languages, and Programming. Vol. 8573, Issue. , p. 363.

Yang, Fei and Huang, Hao 2015. A polynomial time algorithm for checking regularity of totally normed process algebra. Journal of Shanghai Jiaotong University (Science), Vol. 20, Issue. 3, p. 273.

Fu, Yuxi 2016. Theory of interaction. Theoretical Computer Science, Vol. 611, Issue. , p. 1.

Kučera, Antonín and Mayr, Richard 2018. A generic framework for checking semantic equivalences between pushdown automata and finite-state automata. Journal of Computer and System Sciences, Vol. 91, Issue. , p. 82.

Zhang, Wenbo Long, Huan and Xu, Xian 2019. Programming Languages and Systems. Vol. 11893, Issue. , p. 388.

Jasper, Marc Schlüter, Maximilian and Steffen, Bernhard 2020. Characteristic invariants in Hennessy–Milner logic. Acta Informatica, Vol. 57, Issue. 3-5, p. 671.

Xu, Xian and Zhang, Wenbo 2021. On Decidability of the Bisimilarity on Higher-order Processes with Parameterization. Electronic Proceedings in Theoretical Computer Science, Vol. 339, Issue. , p. 76.

Download full list

Article contents

Equivalence-checking on infinite-state systems: Techniques and results

Abstract

Keywords

Information

This article has been cited by the following publications. This list is generated based on data provided by Crossref.

Article contents

Equivalence-checking on infinite-state systems: Techniques and results

Abstract

Keywords

Information

Save article to Kindle

Save article to Dropbox

Save article to Google Drive

Reply to: Submit a response

Your details

You have entered the maximum number of contributors

Conflicting interests