Enumeration and generation with a string automata representation |
| |
Authors: | Marco Almeida,Nelma Moreira,Rogé rio Reis |
| |
Affiliation: | DCC-FC & LIACC, Universidade do Porto, R. do Campo Alegre 1021/1055, 4169-007 Porto, Portugal |
| |
Abstract: | The representation of combinatorial objects is decisive for the feasibility of several enumerative tasks. In this work, we present a unique string representation for complete initially-connected deterministic automata (ICDFAs) with n states over an alphabet of k symbols. For these strings we give a regular expression and show how they are adequate for exact and random generation, allow an alternative way for enumeration and lead to an upper bound for the number of ICDFAs. The exact generation algorithm can be used to partition the set of ICDFAs in order to parallelize the counting of minimal automata, and thus of regular languages. A uniform random generator for ICDFAs is presented that uses a table of pre-calculated values. Based on the same table, an optimal coding for ICDFAs is obtained. |
| |
Keywords: | Finite automata Initially-connected deterministic finite automata Exact enumeration Random generation Minimal automata |
本文献已被 ScienceDirect 等数据库收录! |
|