Series-Parallel Automata and Short Regular Expressions

• Type: Article in International Scientific Journal
• Date: 2009

Authors

Nelma Moreira (Author) FCUP; Rogerio Reis (Author) FCUP

Journal

Title: Fundamenta Informaticae

Vol. 91

Pages: 611-629

ISSN: 0169-2968

Publisher: IOS PRESS

Indexing

ISI Web of Knowledge - 8 Citations

Scopus - 9 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-003-Q5A

DOI: 10.3233/fi-2009-0061

Abstract (EN): 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 19