Concise Representations of Reversible Automata - Descriptional Complexity of Formal Systems (DCFS 2017)
Conference Papers Year : 2017

Concise Representations of Reversible Automata

Abstract

We present two concise representations of reversible automata. Both representations have a size which is comparable with the size of the minimum equivalent deterministic automaton and can be exponentially smaller than the size of the explicit representations of corresponding reversible automata. Using those representations it is possible to simulate the computations of reversible automata without explicitly writing down their complete descriptions.
Fichier principal
Vignette du fichier
440206_1_En_19_Chapter.pdf (335.15 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-01657009 , version 1 (06-12-2017)

Licence

Identifiers

Cite

Giovanna J. Lavado, Luca Prigioniero. Concise Representations of Reversible Automata. 19th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2017, Milano, Italy. pp.238-249, ⟨10.1007/978-3-319-60252-3_19⟩. ⟨hal-01657009⟩
45 View
72 Download

Altmetric

Share

More