%0 Conference Proceedings
%T Forward Injective Finite Automata: Exact and Random Generation of Nonisomorphic NFAs
%+ Faculdade de Ciências da Universidade do Porto (FCUP)
%A Ferreira, Miguel
%A Moreira, Nelma
%A Reis, Rogério
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 20th International Conference on Descriptional Complexity of Formal Systems (DCFS)
%C Halifax, NS, Canada
%Y Stavros Konstantinidis
%Y Giovanni Pighizzini
%I Springer International Publishing
%3 Descriptional Complexity of Formal Systems
%V LNCS-10952
%P 88-100
%8 2018-07-25
%D 2018
%R 10.1007/978-3-319-94631-3_8
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.2
%2 https://inria.hal.science/hal-01905623/document
%2 https://inria.hal.science/hal-01905623/file/470153_1_En_8_Chapter.pdf
%L hal-01905623
%U https://inria.hal.science/hal-01905623
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-WG
%~ IFIP-DCFS
%~ IFIP-WG1-2
%~ IFIP-LNCS-10952