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

• Type: Article in International Conference Proceedings Book
• Date: 2018

Authors

Ferreira, M (Author) Other; Nelma Moreira (Author) FCUP; Rogério Reis (Author) FCUP

Conference proceedings International

Title: DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2018

Pages: 88-100

20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems (DCFS)

Saint Mary's Univ, Halifax, CANADA, JUL 25-27, 2018

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 1 Citation

Scientific classification

CORDIS: Physical sciences > Computer science

FOS: Natural sciences > Computer and information sciences ; Engineering and technology

Other information

Authenticus ID: P-00P-262

DOI: 10.1007/978-3-319-94631-3_8

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 13