The Prefix Automaton

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

Authors

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

Journal

Title: Journal of Automata, Languages and Combinatorics

Vol. 26

Pages: 17-53

ISSN: 1430-189X

Publisher: Institut fur Informatik, Justus-Liebig-Universitat Giessen

Indexing

Scopus - 3 Citations

Other information

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

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 36