The Complexity of Bisimulation and Simulation on Finite Systems
In this paper the computational complexity of the (bi)simulation problem over restricted graph classes is studied. For trees given as pointer structures or terms the (bi)simulation problem is complete for logarithmic space or NC$^1$, respectively. This solves an open problem from Balc\'azar, Ga...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2018-10-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/4561/pdf |
| _version_ | 1797268560335077376 |
|---|---|
| author | Moses Ganardi Stefan Göller Markus Lohrey |
| author_facet | Moses Ganardi Stefan Göller Markus Lohrey |
| author_sort | Moses Ganardi |
| collection | DOAJ |
| description | In this paper the computational complexity of the (bi)simulation problem over
restricted graph classes is studied. For trees given as pointer structures or
terms the (bi)simulation problem is complete for logarithmic space or NC$^1$,
respectively. This solves an open problem from Balc\'azar, Gabarr\'o, and
S\'antha. Furthermore, if only one of the input graphs is required to be a
tree, the bisimulation (simulation) problem is contained in AC$^1$ (LogCFL). In
contrast, it is also shown that the simulation problem is P-complete already
for graphs of bounded path-width. |
| first_indexed | 2024-04-25T01:34:25Z |
| format | Article |
| id | doaj.art-5a8df5d4b9d6402e8463de7d5b8f4af8 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:34:25Z |
| publishDate | 2018-10-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-5a8df5d4b9d6402e8463de7d5b8f4af82024-03-08T10:27:52ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742018-10-01Volume 14, Issue 410.23638/LMCS-14(4:5)20184561The Complexity of Bisimulation and Simulation on Finite SystemsMoses GanardiStefan GöllerMarkus LohreyIn this paper the computational complexity of the (bi)simulation problem over restricted graph classes is studied. For trees given as pointer structures or terms the (bi)simulation problem is complete for logarithmic space or NC$^1$, respectively. This solves an open problem from Balc\'azar, Gabarr\'o, and S\'antha. Furthermore, if only one of the input graphs is required to be a tree, the bisimulation (simulation) problem is contained in AC$^1$ (LogCFL). In contrast, it is also shown that the simulation problem is P-complete already for graphs of bounded path-width.https://lmcs.episciences.org/4561/pdfcomputer science - logic in computer science |
| spellingShingle | Moses Ganardi Stefan Göller Markus Lohrey The Complexity of Bisimulation and Simulation on Finite Systems Logical Methods in Computer Science computer science - logic in computer science |
| title | The Complexity of Bisimulation and Simulation on Finite Systems |
| title_full | The Complexity of Bisimulation and Simulation on Finite Systems |
| title_fullStr | The Complexity of Bisimulation and Simulation on Finite Systems |
| title_full_unstemmed | The Complexity of Bisimulation and Simulation on Finite Systems |
| title_short | The Complexity of Bisimulation and Simulation on Finite Systems |
| title_sort | complexity of bisimulation and simulation on finite systems |
| topic | computer science - logic in computer science |
| url | https://lmcs.episciences.org/4561/pdf |
| work_keys_str_mv | AT mosesganardi thecomplexityofbisimulationandsimulationonfinitesystems AT stefangoller thecomplexityofbisimulationandsimulationonfinitesystems AT markuslohrey thecomplexityofbisimulationandsimulationonfinitesystems AT mosesganardi complexityofbisimulationandsimulationonfinitesystems AT stefangoller complexityofbisimulationandsimulationonfinitesystems AT markuslohrey complexityofbisimulationandsimulationonfinitesystems |