The Prefix Automaton

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

Autores

Broda, S (Autor) FCUP; Eva Maia (Autor) FEUP; Nelma Moreira (Autor) FCUP; Rogério Reis (Autor) FCUP

Revista

A Revista está pendente de validação pelos Serviços Administrativos.

Título: J. Autom. Lang. Comb.

Vol. 26

Páginas: 17-53

ISSN: 1430189X

Indexação

Scopus - 2 Citações

Outras Informações

ID Authenticus: P-00V-5HM

DOI: 10.25596/jalc-2021-017

Abstract (EN): There are many different onstrutions when onverting regular expressions to finite automata. In this paper we fous on the prefix automaton, APre, introdued by Yamamoto in 2014. We present two different methods for the onstrution of APre. First, an indutive one, based on a system of expression equations. A seond one using an iterative funtion for omputing the states and transitions. We establish relationships between APre and other onstrutions, suh as the position automaton, partial derivative automaton and their double reversal (dual) ounterparts. We study the average size of these onstrutions, both experimentally and from an analyti ombinatoris point of view. Finally, we extend the onstrution of the prefix automaton to regular expressions with intersetion and show that the relationships with the other automaton onstrutions also hold for these expressions.

Idioma: Inglês

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

Nº de páginas: 36