Prefix and Right-Partial Derivative Automata

• Type: Article in International Conference Proceedings Book
• Date: 2015

Authors

Eva Maia (Author) Other; Nelma Moreira (Author) FCUP; Rogerio Reis (Author) FCUP

Conference proceedings International

Title: EVOLVING COMPUTABILITY

Pages: 258-267

11th Conference on Computability in Europe (CiE)

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

Indexing

ISI Web of Knowledge - 3 Citations

Scopus - 5 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

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

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 10