Browsing by Author "Mazowiecki, Filip"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Item
    Copyless cost-register automata : Structure, expressiveness, and closure properties
    (2019) Mazowiecki, Filip; Riveros Jaeger, Cristian
  • No Thumbnail Available
    Item
    Dynamic Data Structures for Timed Automata Acceptance
    (2022) Grez, Alejandro; Mazowiecki, Filip; Pilipczuk, Michal; Puppis, Gabriele; Riveros, Cristian
    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 A with amortized update time 2(O(vertical bar A vertical bar)) per input symbol.
  • No Thumbnail Available
    Item
    PUMPING LEMMAS FOR WEIGHTED AUTOMATA
    (2021) Chattopadhyay, Agnishom; Mazowiecki, Filip; Muscholl, Anca; Riveros, Cristian
    We present pumping lemmas for five classes of functions definable by fragments of weighted automata over the min-plus semiring, the max-plus semiring and the semiring of natural numbers. As a corollary we show that the hierarchy of functions definable by unambiguous, finitely-ambiguous, polynomially-ambiguous weighted automata, and the full class of weighted automata is strict for the min-plus and max-plus semirings.