Series-Parallel Automata and Short Regular Expressions

• Tipo: Artigo em Revista Científica Internacional
• Data: 2009

Autores

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

Revista

Título: Fundamenta Informaticae

Vol. 91

Páginas: 611-629

ISSN: 0169-2968

Editora: IOS PRESS

Indexação

ISI Web of Knowledge - 8 Citações

Scopus - 9 Citações

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 19