License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2023.24
URN: urn:nbn:de:0030-drops-174852
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17485/
Go to the corresponding LIPIcs Volume Portal

Hazard, Emile ; Kuperberg, Denis

Explorable Automata

pdf-format:
LIPIcs-CSL-2023-24.pdf (0.7 MB)

Abstract

We define the class of explorable automata on finite or infinite words. This is a generalization of History-Deterministic (HD) automata, where this time non-deterministic choices can be resolved by building finitely many simultaneous runs instead of just one. We show that recognizing HD parity automata of fixed index among explorable ones is in PTime, thereby giving a strong link between the two notions. We then show that recognizing explorable automata is ExpTime-complete, in the case of finite words or Büchi automata. Additionally, we define the notion of ω-explorable automata on infinite words, where countably many runs can be used to resolve the non-deterministic choices. We show that all reachability automata are ω-explorable, but this is not the case for safety ones. We finally show ExpTime-completeness for ω-explorability of automata on infinite words for the safety and co-Büchi acceptance conditions.

BibTeX - Entry

@InProceedings{hazard_et_al:LIPIcs.CSL.2023.24,
  author =	{Hazard, Emile and Kuperberg, Denis},
  title =	{{Explorable Automata}},
  booktitle =	{31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-264-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{252},
  editor =	{Klin, Bartek and Pimentel, Elaine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2023/17485},
  URN =		{urn:nbn:de:0030-drops-174852},
  doi =		{10.4230/LIPIcs.CSL.2023.24},
  annote =	{Keywords: Nondeterminism, automata, complexity}
}

Keywords: Nondeterminism, automata, complexity
Collection: 31st EACSL Annual Conference on Computer Science Logic (CSL 2023)
Issue Date: 2023
Date of publication: 01.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI