Exact generation of acyclic deterministic finite automata

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

Authors

Almeida, M (Author) Other; Moreira, N (Author) FCUP; Reis, R (Author) FCUP

Conference proceedings International

Title: Descriptional Complexity of Formal Systems - 10th International Workshop, DCFS 2008

Pages: 48-60

10th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2008

Charlottetown, PE, 16 July 2008 through 18 July 2008

Indexing

ISI Web of Knowledge

Scopus - 1 Citation

Other information

Authenticus ID: P-009-5AB

Abstract (EN): We give a canonical representation for trim acyclic deterministic finite automata (ADFA) with n states over an alphabet of k symbols. Using this normal form, we present a backtracking algorithm for the exact generation of ADFAs. This algorithm is a non trivial adaptation of the algorithm for the exact generation of minimal acyclic deterministic finite automata (MADFA), presented by Almeida et al.

Language: English

Type (Professor's evaluation): Scientific