Search Results

Documents authored by Gallot, Paul D.

Found 2 Possible Name Variants:

Gallot, Paul D.

Document
DOI: 10.4230/LIPIcs.MFCS.2020.38
Linear High-Order Deterministic Tree Transducers with Regular Look-Ahead

Authors: Paul D. Gallot, Aurélien Lemay, and Sylvain Salvati

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We introduce the notion of high-order deterministic top-down tree transducers (HODT) whose outputs correspond to single-typed lambda-calculus formulas. These transducers are natural generalizations of known models of top-tree transducers such as: Deterministic Top-Down Tree Transducers, Macro Tree Transducers, Streaming Tree Transducers... We focus on the linear restriction of high order tree transducers with look-ahead (HODTR_lin), and prove this corresponds to tree to tree functional transformations defined by Monadic Second Order (MSO) logic. We give a specialized procedure for the composition of those transducers that uses a flow analysis based on coherence spaces and allows us to preserve the linearity of transducers. This procedure has a better complexity than classical algorithms for composition of other equivalent tree transducers, but raises the order of transducers. However, we also indicate that the order of a HODTR_lin can always be bounded by 3, and give a procedure that reduces the order of a HODTR_lin to 3. As those resulting HODTR_lin can then be transformed into other equivalent models, this gives an important insight on composition algorithm for other classes of transducers. Finally, we prove that those results partially translate to the case of almost linear HODTR: the class corresponds to the class of tree transformations performed by MSO with unfolding (not closed by composition), and provide a mechanism to reduce the order to 3 in this case.
Cite as

Paul D. Gallot, Aurélien Lemay, and Sylvain Salvati. Linear High-Order Deterministic Tree Transducers with Regular Look-Ahead. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gallot_et_al:LIPIcs.MFCS.2020.38,
  author =	{Gallot, Paul D. and Lemay, Aur\'{e}lien and Salvati, Sylvain},
  title =	{{Linear High-Order Deterministic Tree Transducers with Regular Look-Ahead}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{38:1--38:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.38},
  URN =		{urn:nbn:de:0030-drops-127050},
  doi =		{10.4230/LIPIcs.MFCS.2020.38},
  annote =	{Keywords: Transducers, \lambda-calculus, Trees}
}

Gallot, Paul

Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2024.138
Deciding Linear Height and Linear Size-To-Height Increase of Macro Tree Transducers

Authors: Paul Gallot, Sebastian Maneth, Keisuke Nakano, and Charles Peyrat

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
We present a novel normal form for (total deterministic) macro tree transducers (mtts), called "depth proper normal form". If an mtt is in this normal form, then it is guaranteed that each parameter of each state appears at arbitrary depths in the output trees of that state. Intuitively, if some parameter only appears at certain bounded depths in the output trees of a state, then this parameter can be eliminated by in-lining the corresponding output paths at each call site of that state. We use regular look-ahead in order to determine which of the paths should be in-lined. As a consequence of changing the look-ahead, a parameter that was previously appearing at unbounded depths, may be appearing at bounded depths for some new look-ahead; for this reason, our construction has to be iterated to obtain an mtt in depth-normal form. Using the normal form, we can decide whether the translation of an mtt has linear height increase or has linear size-to-height increase.
Cite as

Paul Gallot, Sebastian Maneth, Keisuke Nakano, and Charles Peyrat. Deciding Linear Height and Linear Size-To-Height Increase of Macro Tree Transducers. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 138:1-138:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gallot_et_al:LIPIcs.ICALP.2024.138,
  author =	{Gallot, Paul and Maneth, Sebastian and Nakano, Keisuke and Peyrat, Charles},
  title =	{{Deciding Linear Height and Linear Size-To-Height Increase of Macro Tree Transducers}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{138:1--138:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.138},
  URN =		{urn:nbn:de:0030-drops-202818},
  doi =		{10.4230/LIPIcs.ICALP.2024.138},
  annote =	{Keywords: automata, formal language theory, macro tree transducer, normal form}
}
Document
DOI: 10.4230/LIPIcs.STACS.2017.34
On the Decomposition of Finite-Valued Streaming String Transducers

Authors: Paul Gallot, Anca Muscholl, Gabriele Puppis, and Sylvain Salvati

Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)

Abstract
We prove the following decomposition theorem: every 1-register streaming string transducer that associates a uniformly bounded number of outputs with each input can be effectively decomposed as a finite union of functional 1-register streaming string transducers. This theorem relies on a combinatorial result by Kortelainen concerning word equations with iterated factors. Our result implies the decidability of the equivalence problem for the considered class of transducers. This can be seen as a first step towards proving a more general decomposition theorem for streaming string transducers with multiple registers.
Cite as

Paul Gallot, Anca Muscholl, Gabriele Puppis, and Sylvain Salvati. On the Decomposition of Finite-Valued Streaming String Transducers. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{gallot_et_al:LIPIcs.STACS.2017.34,
  author =	{Gallot, Paul and Muscholl, Anca and Puppis, Gabriele and Salvati, Sylvain},
  title =	{{On the Decomposition of Finite-Valued Streaming String Transducers}},
  booktitle =	{34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-028-6},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{66},
  editor =	{Vollmer, Heribert and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.34},
  URN =		{urn:nbn:de:0030-drops-69997},
  doi =		{10.4230/LIPIcs.STACS.2017.34},
  annote =	{Keywords: Streaming Transducers, finite valuedness, equivalence}
}
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 About DROPS Imprint Privacy Contact