Prefix and Right-Partial Derivative Automata

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2015

Autores

Eva Maia (Autor) Outra; Nelma Moreira (Autor) FCUP; Rogerio Reis (Autor) FCUP

Ata de Conferência Internacional

Título: EVOLVING COMPUTABILITY

Páginas: 258-267

11th Conference on Computability in Europe (CiE)

Univ Bucharest, Fac Math & Comp Sci, Bucharest, ROMANIA, JUN 29-JUL 03, 2015

Indexação

ISI Web of Knowledge - 3 Citações

Scopus - 5 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-00G-T00

DOI: 10.1007/978-3-319-20028-6_26

Abstract (EN): Recently, Yamamoto presented a new method for the conversion from regular expressions (REs) to non-deterministic finite automata (NFA) based on the Thompson epsilon-NFA (A(T)). The A(T) automaton has two quotients discussed: the suffix automaton A(suf) and the prefix automaton, A(pre). Eliminating epsilon-transitions in A(T), the Glushkov automaton (A(pos)) is obtained. Thus, it is easy to see that A(suf) and the partial derivative automaton (A(pd)) are the same. In this paper, we characterise the A(pre) automaton as a solution of a system of left RE equations and express it as a quotient of A(pos) by a specific left-invariant equivalence relation. We define and characterise the right-partial derivative automaton ((A) over left arrow (pd)). Finally, we study the average size of all these constructions both experimentally and from an analytic combinatorics point of view.

Idioma: Inglês

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

Nº de páginas: 10