Paper Info
Title
Enumeration and generation with a string automata representation
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.
Year
DOI
Venue
2007
10.1016/j.tcs.2007.07.029
Theor. Comput. Sci.
Keywords
DocType
Volume
unique string representation,finite automata,string automata representation,Minimal automata,minimal automata,Initially-connected deterministic finite automata,initially connected deterministic finite automata,Exact enumeration,Finite automata,regular expression,exact generation algorithm,regular language,k symbol,random generation,enumerative task,combinatorial object,complete initially-connected deterministic automaton,exact enumeration,Random generation,uniform random generator
Journal
387
Issue
ISSN
Citations 
2
Theoretical Computer Science
10
PageRank 
References 
Authors
0.70
11
3
Name
Order
Citations
PageRank
Marco Almeida1313.99
Nelma Moreira218033.98
Rogério Reis314025.74