Bruno Guillon

33 papers A* 2A 2C 6Journal 17Unranked 6
YearRankTypeTitle / Venue / Authors
2026 A conf
Polynomial Complementation of Nondeterministic Two-Way Finite Automata by 1-Limited Automata.
STACS
Bruno Guillon, Luca Prigioniero, Javad Taheri
2025 A conf
CMSO-Transducing Tree-Like Graph Decompositions.
STACS
Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté, Eun Jung Kim, Noleen Köhler
2025 C conf
Nondeterminism Makes Unary 1-Limited Automata Concise.
DLT
Bruno Guillon, Luca Prigioniero, Javad Taheri
2025 J jnl
Nondeterminism makes unary 1-limited automata concise.
CoRR
Bruno Guillon, Luca Prigioniero, Javad Taheri
2025 J jnl
Polynomial Complementation of Nondeterministic 2-Way Finite Automata by 1-Limited Automata.
CoRR
Bruno Guillon, Luca Prigioniero, Javad Taheri
2025 A* conf
Recognisability Equals Definability for Finitely Representable Matroids of Bounded Path-Width.
LICS
Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté, Eun Jung Kim, Sang-il Oum
2024 J jnl
CMSO-transducing tree-like graph decompositions.
CoRR
Rutger Campbell, Bruno Guillon, Mamadou Moustapha Kanté, Eun Jung Kim, Noleen Köhler
2023 J jnl
Weight-reducing Turing machines.
Inf. Comput.
Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero, Daniel Prusa
2022 J jnl
Converting nondeterministic two-way automata into small deterministic linear-time machines.
Inf. Comput.
Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero, Daniel Prusa
2022 J jnl
Weakly and Strongly Irreversible Regular Languages.
Int. J. Found. Comput. Sci.
Bruno Guillon, Giovanna J. Lavado, Giovanni Pighizzini, Luca Prigioniero
2021 J jnl
Converting Nondeterministic Two-Way Automata into Small Deterministic Linear-Time Machines.
CoRR
Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero, Daniel Prusa
2021 J jnl
Reversible pushdown transducers.
Inf. Comput.
Bruno Guillon, Martin Kutrib, Andreas Malcher, Luca Prigioniero
2021 J jnl
Weight-Reducing Turing Machines.
CoRR
Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero, Daniel Prusa
2020 J jnl
Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata.
Int. J. Found. Comput. Sci.
Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero
2020 J jnl
Undecidability of a weak version of MSO+U.
Log. Methods Comput. Sci.
Mikolaj Bojanczyk, Laure Daviaud, Bruno Guillon, Vincent Penelle, A. V. Sreejith
2019 J jnl
Linear-time limited automata.
Theor. Comput. Sci.
Bruno Guillon, Luca Prigioniero
2018 — conf
Counter Machines and Distributed Automata - A Story About Exchanging Space and Time.
Automata
Olivier Carton, Bruno Guillon, Fabian Reiter
2018 J jnl
Counter Machines and Distributed Automata: A Story about Exchanging Space and Time.
CoRR
Olivier Carton, Bruno Guillon, Fabian Reiter
2018 — conf
Linear-Time Limited Automata.
DCFS
Bruno Guillon, Luca Prigioniero
2018 C conf
Non-self-embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata.
CIAA
Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero
2018 — conf
On nondeterministic two-way transducers.
NCMA
Bruno Guillon
2018 C conf
Reversible Pushdown Transducers.
DLT
Bruno Guillon, Martin Kutrib, Andreas Malcher, Luca Prigioniero
2018 C conf
Two-Way Automata and One-Tape Machines - Read Only Versus Linear Time.
DLT
Bruno Guillon, Giovanni Pighizzini, Luca Prigioniero, Daniel Prusa
2018 J jnl
Undecidability of MSO+"ultimately periodic".
CoRR
Mikolaj Bojanczyk, Laure Daviaud, Bruno Guillon, Vincent Penelle, A. V. Sreejith
2017 A* conf
Which Classes of Origin Graphs Are Generated by Transducers.
ICALP
Mikolaj Bojanczyk, Laure Daviaud, Bruno Guillon, Vincent Penelle
2016 C conf
Both Ways Rational Functions.
DLT
Christian Choffrut, Bruno Guillon
2016 J jnl
Input- or output-unary sweeping transducers are weaker than their 2-way counterparts.
RAIRO Theor. Informatics Appl.
Bruno Guillon
2015 — conf
Sweeping weakens two-way transducers even with a unary output alphabet.
NCMA
Bruno Guillon
2014 — conf
An Algebraic Characterization of Unary Two-Way Transducers.
MFCS (1)
Christian Choffrut, Bruno Guillon
2014 — conf
An algebraic characterization of unary two-way transducers.
ICTCS
Christian Choffrut, Bruno Guillon
2014 J jnl
Two-way automata making choices only at the endmarkers.
Inf. Comput.
Viliam Geffert, Bruno Guillon, Giovanni Pighizzini
2012 C conf
Two-Way Automata Making Choices Only at the Endmarkers.
LATA
Viliam Geffert, Bruno Guillon, Giovanni Pighizzini
2011 J jnl
Two-Way Automata Making Choices Only at the Endmarkers
CoRR
Viliam Geffert, Bruno Guillon, Giovanni Pighizzini