Name
Abstract | ||
|---|---|---|
In general, the representation of combinatorial objects is decisive for the
feasibility of several enumerative tasks. In this work, we show how a (unique)
string representation for (complete) initially-connected deterministic automata
(ICDFAs) with n states over an alphabet of k symbols can be used for counting,
exact enumeration, sampling and optimal coding, not only the set of ICDFAs but,
to some extent, the set of regular languages. An 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). We present also a uniform
random generator for ICDFAs that uses a table of pre-calculated values. Based
on the same table it is also possible to obtain an optimal coding for ICDFAs. |
Year | Venue | Keywords |
|---|---|---|
2006 | Computing Research Repository | regular language,formal language,automata theory,generic algorithm |
DocType | Volume | Citations |
Conference | abs/0906.3 | 3 |
PageRank | References | Authors |
0.51 | 3 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Marco Almeida | 1 | 31 | 3.99 |
| Nelma Moreira | 2 | 180 | 33.98 |
| Rogério Reis | 3 | 140 | 25.74 |