Finite Automata with Undirected State Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2018

Finite Automata with Undirected State Graphs

Résumé

We investigate finite automata whose state graphs are undirected. This means that for any transition from state p to q consuming some letter a from the input there exists a symmetric transition from state q to p consuming a letter a as well. So, the corresponding language families are subregular and, in particular in the deterministic case, subreversible. In detail, we study the operational descriptional complexity of deterministic and nondeterministic undirected finite automata. To this end, the different types of automata on alphabets with few letters are characterized. Then the operational state complexity of the Boolean operations as well as the operations concatenation and iteration is investigated, where tight upper and lower bounds are derived for unary as well as arbitrary alphabets under the condition that the corresponding language classes are closed under the operation considered.
Fichier principal
Vignette du fichier
470153_1_En_18_Chapter.pdf (328.96 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01905634 , version 1 (26-10-2018)

Licence

Paternité

Identifiants

Citer

Martin Kutrib, Andreas Malcher, Christian Schneider. Finite Automata with Undirected State Graphs. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.212-223, ⟨10.1007/978-3-319-94631-3_18⟩. ⟨hal-01905634⟩
185 Consultations
77 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More