Dynamic Data Structures for Timed Automata Acceptance

Simple item page
dc.contributor.authorGrez, Alejandro
dc.contributor.authorMazowiecki, Filip
dc.contributor.authorPilipczuk, Michal
dc.contributor.authorPuppis, Gabriele
dc.contributor.authorRiveros, Cristian
dc.date.accessioned2025-01-20T21:02:44Z
dc.date.available2025-01-20T21:02:44Z
dc.date.issued2022
dc.description.abstractWe 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 A with amortized update time 2(O(vertical bar A vertical bar)) per input symbol.
dc.fuente.origenWOS
dc.identifier.doi10.1007/s00453-022-01025-8
dc.identifier.eissn1432-0541
dc.identifier.issn0178-4617
dc.identifier.urihttps://doi.org/10.1007/s00453-022-01025-8
dc.identifier.urihttps://repositorio.uc.cl/handle/11534/93078
dc.identifier.wosidWOS:000850021200004
dc.issue.numero11
dc.language.isoen
dc.pagina.final3245
dc.pagina.inicio3223
dc.revistaAlgorithmica
dc.rightsacceso restringido
dc.subjectTimed automata
dc.subjectData stream
dc.subjectDynamic data structure
dc.titleDynamic Data Structures for Timed Automata Acceptance
dc.typeartículo
dc.volumen84
sipa.indexWOS
sipa.trazabilidadWOS;2025-01-12
Files
Collections
Artículos de revistas