11 DEZEMBRO / SEGUNDA FEIRA / 22:45
FCUP PT 
 EN
 
 
APRESENTAÇÃO
PESSOAS
ENSINO
INVESTIGAÇÃO
BIBLIOTECA
NOTÍCIAS
CONTACTOS

Technical Report: DCC-2006-07

Enumeration and Generation of Initially Connected Deterministic Finite Automata

Marco Almeida, Nelma Moreira, and Rogério Reis

DCC-FC & LIACC, Universidade do Porto

E-mail: {mfa,nam,rvr}@dcc.fc.up.pt

December 2006

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 (ICDFA's) 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 ICDFA's. The exact generation algorithm can be used to partition the set of ICDFA's in order to parallelize the counting of minimal automata (and thus of regular languages). A uniform random generator for ICDFA's is presented that uses a table of pre-calculated values. Based on the same table, an optimal coding for ICDFA's is obtained. We also establish an explicit relationship between our method and the one used by Nicaud et al..


FCUP 2017