Skip to Main content Skip to Navigation
Conference papers

Forward Injective Finite Automata: Exact and Random Generation of Nonisomorphic NFAs

Abstract : We define the class of forward injective finite automata (FIFA) and study some of their properties. Each FIFA has a unique canonical representation up to isomorphism. Using this representation an enumeration is given and an efficient uniform random generator is presented. We provide a conversion algorithm from a nondeterministic finite automaton or regular expression into an equivalent FIFA. Finally, we present some experimental results comparing the size of FIFA with other automata.
Document type :
Conference papers
Complete list of metadata

Cited literature [10 references]  Display  Hide  Download

https://hal.inria.fr/hal-01905623
Contributor : Hal Ifip <>
Submitted on : Friday, October 26, 2018 - 8:00:59 AM
Last modification on : Monday, November 16, 2020 - 2:04:02 PM
Long-term archiving on: : Sunday, January 27, 2019 - 1:08:44 PM

File

470153_1_En_8_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Miguel Ferreira, Nelma Moreira, Rogério Reis. Forward Injective Finite Automata: Exact and Random Generation of Nonisomorphic NFAs. 20th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2018, Halifax, NS, Canada. pp.88-100, ⟨10.1007/978-3-319-94631-3_8⟩. ⟨hal-01905623⟩

Share

Metrics

Record views

92

Files downloads

12