Recherche - Archive ouverte HAL Accéder directement au contenu

Filtrer vos résultats

16 résultats
Page :
triés par

Two-Way Automata and One-Tape Machines: Read Only Versus Linear Time

 Bruno Guillon , Giovanni Pighizzini , Luca Prigioniero , Daniel Průša
Developments in Language Theory, pp.366-378, 2018, ⟨10.1007/978-3-319-98654-8_30⟩
Chapitre d'ouvrage hal-02079083v1
Image document

Weight-Reducing Turing Machines

 Bruno Guillon , Giovanni Pighizzini , Luca Prigioniero , Daniel Průša
2023
Pré-publication, Document de travail hal-04093750v1
Image document

Which classes of origin graphs are generated by transducers? *

 Mikołaj Bojańczyk , Laure Daviaud , Bruno Guillon , Vincent Penelle
ICALP 2017, Jul 2017, Warszawa, Poland
Communication dans un congrès hal-01762979v1
Image document

Weight-reducing Turing machines

 Bruno Guillon , Giovanni Pighizzini , Luca Prigioniero , Daniel Průša
Information and Computation, 2023, 292, pp.105030. ⟨10.1016/j.ic.2023.105030⟩
Article dans une revue hal-04093540v1
Image document

Reversible Pushdown Transducers

 Bruno Guillon , Martin Kutrib , Andreas Malcher , Luca Prigioniero
Information and Computation, 2021, 281, pp.104813. ⟨10.1016/j.ic.2021.104813⟩
Article dans une revue hal-04093721v1
Image document

Linear-Time Limited Automata

 Bruno Guillon , Luca Prigioniero
Theoretical Computer Science, 2019, 798, pp.95-108. ⟨10.1016/j.tcs.2019.03.037⟩
Article dans une revue hal-04093789v1
Image document

Linear-Time Limited Automata

 Bruno Guillon , Luca Prigioniero
20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.126-138, ⟨10.1007/978-3-319-94631-3_11⟩
Communication dans un congrès hal-01905632v1

Reversible Pushdown Transducers

 Bruno Guillon , Martin Kutrib , Andreas Malcher , Luca Prigioniero
Development of Language Theory, pp.354-365, 2018, ⟨10.1007/978-3-319-98654-8_29⟩
Chapitre d'ouvrage hal-02079113v1

Linear-Time Limited Automata

 Bruno Guillon , Luca Prigioniero
Descriptional Complexity of Formal Systems, pp.126-138, 2018, ⟨10.1007/978-3-319-94631-3_11⟩
Chapitre d'ouvrage hal-02079122v1

Undecidability of a weak version of MSO+U

 Vincent Penelle , Mikolaj Bojanczyk , Laure Daviaud , Bruno Guillon , A. V. Sreejith
Logical Methods in Computer Science, 2020
Article dans une revue hal-02510685v1
Image document

Weakly and Strongly Irreversible Regular Languages

 Bruno Guillon , Giovanna J Lavado , Giovanni Pighizzini , Luca Prigioniero
International Journal of Foundations of Computer Science, 2022, 33 (3-4), pp.263-284. ⟨10.1142/S0129054122410052⟩
Article dans une revue hal-04093709v1
Image document

Converting nondeterministic two-way automata into small deterministic linear-time machines

 Bruno Guillon , Giovanni Pighizzini , Luca Prigioniero , Daniel Průša
Information and Computation, 2022, 289 (Part A), pp.104938. ⟨10.1016/j.ic.2022.104938⟩
Article dans une revue hal-04093745v1
Image document

Non-Self-Embedding Grammars, Constant Height Pushdown Automata, and Limited Automata

 Bruno Guillon , Giovanni Pighizzini , Luca Prigioniero
International Journal of Foundations of Computer Science, 2020, 31 (08), pp.1133-1157. ⟨10.1142/S0129054120420071⟩
Article dans une revue hal-04093781v1
Image document

Counter Machines and Distributed Automata

 Olivier Carton , Bruno Guillon , Fabian Reiter
24th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Jun 2018, Ghent, Belgium. pp.13-28, ⟨10.1007/978-3-319-92675-9_2⟩
Communication dans un congrès hal-01824873v1

Non-self-embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata

 Bruno Guillon , Giovanni Pighizzini , Luca Prigioniero
Implementation and Application of Automata, pp.186-197, 2018, ⟨10.1007/978-3-319-94812-6_16⟩
Chapitre d'ouvrage hal-02079141v1
Image document

Converting Nondeterministic Two-Way Automata into Small Deterministic Linear-Time Machines

 Bruno Guillon , Giovanni Pighizzini , Luca Prigioniero , Daniel Průša
2021
Pré-publication, Document de travail hal-04093737v1
Page :