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.IPEC.2021.20
URN: urn:nbn:de:0030-drops-154037
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/15403/
Go to the corresponding LIPIcs Volume Portal

Grez, Alejandro ; Mazowiecki, Filip ; Pilipczuk, Michał ; Puppis, Gabriele ; Riveros, Cristian

Dynamic Data Structures for Timed Automata Acceptance

pdf-format:
LIPIcs-IPEC-2021-20.pdf (0.7 MB)

Abstract

We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so through the lenses of parameterized dynamic data structures: we assume that the automaton is fixed and its size is the parameter, while the input word is revealed as in a stream, one symbol at a time following the natural order on positions. The goal is to design a dynamic data structure that can be efficiently updated upon revealing the next symbol, while maintaining the answer to the query on whether the word consisting of symbols revealed so far is accepted by the automaton. We provide complexity bounds for this dynamic acceptance problem for timed automata that process symbols interleaved with time spans. The main contribution is a dynamic data structure that maintains acceptance of a fixed one-clock timed automaton ? with amortized update time 2^{?(|?|)} per input symbol.

BibTeX - Entry

@InProceedings{grez_et_al:LIPIcs.IPEC.2021.20,
  author =	{Grez, Alejandro and Mazowiecki, Filip and Pilipczuk, Micha{\l} and Puppis, Gabriele and Riveros, Cristian},
  title =	{{Dynamic Data Structures for Timed Automata Acceptance}},
  booktitle =	{16th International Symposium on Parameterized and Exact Computation (IPEC 2021)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-216-7},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{214},
  editor =	{Golovach, Petr A. and Zehavi, Meirav},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15403},
  URN =		{urn:nbn:de:0030-drops-154037},
  doi =		{10.4230/LIPIcs.IPEC.2021.20},
  annote =	{Keywords: timed automata, data stream, dynamic data structure}
}

Keywords: timed automata, data stream, dynamic data structure
Collection: 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Issue Date: 2021
Date of publication: 22.11.2021

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