Minimization of visibly pushdown automata is NP-complete

Autor: Olivier Gauwin, Anca Muscholl, Michael Raskin

Publikováno v: Logical Methods in Computer Science, Vol Volume 16, Issue 1 (2020)

We show that the minimization of visibly pushdown automata is NP-complete. This result is obtained by introducing immersions, that recognize multiple languages (over a usual, non-visible alphabet) using a common deterministic transition graph, such t

Externí odkaz: https://doaj.org/article/b50c8f184f414ac7881b8b6bfbaa87ee

Streamability of nested word transductions

Autor: Emmanuel Filiot, Olivier Gauwin, Pierre-Alain Reynier, Frédéric Servais

Publikováno v: Logical Methods in Computer Science, Vol Volume 15, Issue 2 (2019)

We consider the problem of evaluating in streaming (i.e., in a single left-to-right pass) a nested word transduction with a limited amount of memory. A transduction T is said to be height bounded memory (HBM) if it can be evaluated with a memory that

Externí odkaz: https://doaj.org/article/cb9a45171c924ea4981837832a8e555a

Untwisting two-way transducers in elementary time

Autor: Felix Baschenis, Olivier Gauwin, Anca Muscholl, Gabriele Puppis

Publikováno v: 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'17)
32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'17), Jun 2017, Reykjavik, Iceland. pp.1-12, ⟨10.1109/LICS.2017.8005138⟩

International audience; Functional transductions realized by two-way transducers (equivalently, by streaming transducers and by MSO transductions) are the natural and standard notion of "regular" mappings from words to words. It was shown recently (L

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0858102b33b0dfbdb47b287f5ea66d68

First-order definability of rational transductions

Autor: Emmanuel Filiot, Olivier Gauwin, Nathan Lhote

Publikováno v: LICS
Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16)
31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16)
31st Annual ACM/IEEE Symposium on Logic in Computer Science (LICS'16), Jul 2016, New York, United States. pp.387--396, ⟨10.1145/2933575.2934520⟩

The algebraic theory of rational languages has provided powerful decidability results. Among them, one of the most fundamental is the definability of a rational language in the class of aperiodic languages, i.e., languages recognized by finite automa

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::aee15eda3320354c20488791bfbaab4d
https://doi.org/10.1145/2933575.2934520

Early Nested Word Automata for XPath Query Answering on XML Streams

Autor: Olivier Gauwin, Denis Debarbieux, Tom Sebastian, Mohamed Zergaoui, Joachim Niehren

Publikováno v: Theoretical Computer Science
Theoretical Computer Science, 2015, 578, pp.100-125. ⟨10.1016/j.tcs.2015.01.017⟩
Theoretical Computer Science, Elsevier, 2015, pp.100-125. ⟨10.1016/j.tcs.2015.01.017⟩
Implementation and Application of Automata ISBN: 9783642392733
CIAA
18th International Conference on Implementation and Application of Automata
18th International Conference on Implementation and Application of Automata, Jul 2013, Halifax, Canada. pp.292-305

International audience; Algorithms for answering XPath queries on Xml streams have been studied intensively in the last decade. Nevertheless, there still exists no solution with high efficiency and large coverage. In this paper, we introduce early ne

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b84d9f711b1ed644334f7851a91f0a5f
https://inria.hal.science/hal-00966625/document