Series-Parallel Automata and Short Regular Expressions

Article type: Research Article

Authors: Moreira, Nelma | Reis, Rogério

Affiliations: DCC-FC & LIACC, Universidade do Porto, R. do Campo Alegre 1021/1055, 4169-007 Porto, Portugal. {nam,rvr}@ncc.up.pt

Note: [] Address for correspondence: DCC-FC & LIACC, Universidade do Porto, R. do Campo Alegre 1021/1055, 4169-007 Porto, Portugal

Abstract: Computing short regular expressions equivalent to a given finite automaton is a hard task. In this work we present a class of acyclic automata for which it is possible to obtain in time O(n^{2} log n) an equivalent regular expression of size O(n). A characterisation of this class is made using properties of the underlying digraphs that correspond to the series-parallel digraphs class. Using this characterisation we present an algorithm for the generation of automata of this class and an enumerative formula for the underlying digraphs with a given number of vertices.

DOI: 10.3233/FI-2009-0061

Journal: Fundamenta Informaticae, vol. 91, no. 3-4, pp. 611-629, 2009