Bisimilarity in Fresh Register Automata

Andrzrej Murawski, Steven Ramsay, Nikos Tzevelekos

Research output: Chapter in Book/Report/Conference proceedingConference Contribution (Conference Proceeding)

7 Citations (Scopus)
12 Downloads (Pure)

Abstract

Register automata are a basic model of computation over infinite alphabets. Fresh-register automata extend register automata with the capability to generate fresh symbols in order to model computational scenarios involving name creation. This paper investigates the complexity of the bisimilarity problem for classes of register and fresh-register automata. We examine all main disciplines that have appeared in the literature: general register assignments, assignments where duplicate register values are disallowed, and assignments without duplicates in which registers cannot be empty. In the general case, we show that the problem is EXPTIME-complete. However, the absence of duplicate values in registers enables us to identify inherent symmetries inside the associated bisimulation relations, which can be used to establish a polynomial bound on the depth of Attacker-winning strategies. Furthermore, they enable a highly succinct representation of the corresponding bisimulations. By exploiting results from group theory and computational group theory, we can then show solvability in PSPACE and NP respectively for the latter two register disciplines. In each case, we find that freshness does not affect the complexity class of the problem. The results allow us to close a complexity gap for language equivalence of deterministic register automata. We show that deterministic language in equivalence for the no-duplicates fragment is NP-complete, which disproves an old conjecture of Sakamoto. Finally, we discover that, unlike in the finite-alphabet case, the addition of pushdown store makes bisimilarity undecidable, even in the case of visibly pushdown storage.
Original languageEnglish
Title of host publication2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015)
PublisherIEEE Computer Society
Pages156-167
Number of pages12
ISBN (Electronic)978-1-4799-8875-4
ISBN (Print)1043-6871
DOIs
Publication statusPublished - Jul 2015

Fingerprint

Dive into the research topics of 'Bisimilarity in Fresh Register Automata'. Together they form a unique fingerprint.

Cite this