Finite Automata with Undirected State Graphs

Abstract : 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [11 references]  Display  Hide  Download

https://hal.inria.fr/hal-01905634
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:01:28 AM
Last modification on : Friday, October 26, 2018 - 8:05:07 AM
Long-term archiving on : Sunday, January 27, 2019 - 12:48:02 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2021-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

198