DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2022.76

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

Authors: Dominik Peteler and Karin Quaas

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

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.

Cite as

Dominik Peteler and Karin Quaas. Deciding Emptiness for Constraint Automata on Strings with the Prefix and Suffix Order. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 76:1-76:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@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/entities/document/10.4230/LIPIcs.MFCS.2022.76},
  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}
}

Search Results

Documents authored by Peteler, Dominik

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

Abstract

Cite as

Thanks for your feedback!

Could not send message