Partial Derivative and Position Bisimilarity Automata

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

Authors

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

Conference proceedings International

Title: IMPLEMENTATION AND APPLICATION OF AUTOMATA, CIAA 2014

Pages: 264-277

19th International Conference on Implementation and Application of Automata (CIAA)

Giessen, GERMANY, JUL 30-AUG 02, 2014

Indexing

ISI Web of Knowledge - 3 Citations

Scopus - 0 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-009-PPG

DOI: 10.1007/978-3-319-08846-4_20

Abstract (EN): Minimization of nondeterministic finite automata (NFA) is a hard problem (PSPACE-complete). Bisimulations are then an attractive alternative for reducing the size of NFAs, as even bisimilarity (the largest bisimulation) is almost linear using the Paige and Tarjan algorithm. NFAs obtained from regular expressions (REs) can have the number of states linear with respect to the size of the REs and conversion methods from REs to equivalent NFAs can produce NFAs without or with transitions labelled with the empty word (epsilon-NFA). The standard conversion without epsilon-transitions is the position automaton, A(pos). Other conversions, such as partial derivative automata (A(pd)) or follow automata (A(f)), were proven to be quotients of the position automata (by some bisimulations). Recent experimental results suggested that for REs in (normalized) star normal form the position bisimilarity almost coincide with the A(pd) automaton. Our goal is to have a better characterization of A(pd) automata and their relation with the bisimilarity of the position automata. In this paper, we consider A(pd) automata for regular expressions without Kleene star and establish under which conditions they are isomorphic to the bisimilarity of A(pos).

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14