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 metadatas

Cited literature [2 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 : Friday, October 26, 2018 - 8:05:10 AM
Long-term archiving on : Sunday, January 27, 2019 - 1:08:44 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

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

33