Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2021.32
URN: urn:nbn:de:0030-drops-136770
URL: https://drops.dagstuhl.de/opus/volltexte/2021/13677/
Gamard, Guilhem ; Guillon, Pierre ; Perrot, Kevin ; Theyssier, Guillaume
Rice-Like Theorems for Automata Networks
| pdf-format: |
|
Abstract
We prove general complexity lower bounds on automata networks, in the style of Rice’s theorem, but in the computable world. Our main result is that testing any fixed first-order property on the dynamics of an automata network is either trivial, or NP-hard, or coNP-hard. Moreover, there exist such properties that are arbitrarily high in the polynomial-time hierarchy. We also prove that testing a first-order property given as input on an automata network (also part of the input) is PSPACE-hard. Besides, we show that, under a natural effectiveness condition, any nontrivial property of the limit set of a nondeterministic network is PSPACE-hard. We also show that it is PSPACE-hard to separate deterministic networks with a very high and a very low number of limit configurations; however, the problem of deciding whether the number of limit configurations is maximal up to a polynomial quantity belongs to the polynomial-time hierarchy.
BibTeX - Entry
@InProceedings{gamard_et_al:LIPIcs.STACS.2021.32,
author = {Gamard, Guilhem and Guillon, Pierre and Perrot, Kevin and Theyssier, Guillaume},
title = {{Rice-Like Theorems for Automata Networks}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {32:1--32:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-180-1},
ISSN = {1868-8969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13677},
URN = {urn:nbn:de:0030-drops-136770},
doi = {10.4230/LIPIcs.STACS.2021.32},
annote = {Keywords: Automata networks, Rice theorem, complexity classes, polynomial hierarchy, hardness}
}
| Keywords: | Automata networks, Rice theorem, complexity classes, polynomial hierarchy, hardness | |
| Seminar: | 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) | |
| Issue date: | 2021 | |
| Date of publication: | 10.03.2021 |
