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.MFCS.2022.76
URN: urn:nbn:de:0030-drops-168743
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16874/
Go to the corresponding LIPIcs Volume Portal

Peteler, Dominik ; Quaas, Karin

Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order

pdf-format:
LIPIcs-MFCS-2022-76.pdf (0.6 MB)

Abstract

We study constraint automata that accept data languages on finite string values. Each transition of the automaton is labelled with a constraint restricting the string value at the current and the next position of the data word in terms of the prefix and the suffix order. We prove that the emptiness problem for such constraint automata with Büchi acceptance condition is NL-complete. We remark that since the constraints are formed by two partial orders, prefix and suffix, we cannot exploit existing techniques for similar formalisms. Our decision procedure relies on a decidable characterization for those infinite paths in the graph underlying the automaton that can be completed with string values to yield a Büchi-accepting run. Our result is - to the best of our knowledge - the first work in this context that considers both prefix and suffix, and it is a first step into answering an open question posed by Demri and Deters.

BibTeX - Entry

@InProceedings{peteler_et_al:LIPIcs.MFCS.2022.76,
  author =	{Peteler, Dominik and Quaas, Karin},
  title =	{{Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{76:1--76:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16874},
  URN =		{urn:nbn:de:0030-drops-168743},
  doi =		{10.4230/LIPIcs.MFCS.2022.76},
  annote =	{Keywords: Data Languages, Strings, Constraints, Prefix, Suffix, Automata, Linear Temporal Logic}
}

Keywords: Data Languages, Strings, Constraints, Prefix, Suffix, Automata, Linear Temporal Logic
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

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