1 Search Results for "Peteler, Dominik"

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-dev.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}
}
  • Refine by Author
  • 1 Peteler, Dominik
  • 1 Quaas, Karin

  • Refine by Classification
  • 1 Theory of computation → Automata over infinite objects

  • Refine by Keyword
  • 1 Automata
  • 1 Constraints
  • 1 Data Languages
  • 1 Linear Temporal Logic
  • 1 Prefix
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact