Go to:
Logótipo
Comuta visibilidade da coluna esquerda
Você está em: Start > Publications > View > Partial Derivative and Position Bisimilarity Automata
Publication

Publications

Partial Derivative and Position Bisimilarity Automata

Title
Partial Derivative and Position Bisimilarity Automata
Type
Article in International Conference Proceedings Book
Year
2014
Authors
Eva Maia
(Author)
Other
The person does not belong to the institution. The person does not belong to the institution. The person does not belong to the institution. Without AUTHENTICUS Without ORCID
Nelma Moreira
(Author)
FCUP
View Personal Page You do not have permissions to view the institutional email. Search for Participant Publications View Authenticus page View ORCID page
Rogerio Reis
(Author)
FCUP
View Personal Page You do not have permissions to view the institutional email. Search for Participant Publications View Authenticus page View ORCID page
Conference proceedings International
Pages: 264-277
19th International Conference on Implementation and Application of Automata (CIAA)
Giessen, GERMANY, JUL 30-AUG 02, 2014
Indexing
Scientific classification
FOS: Natural sciences > Computer and information sciences
Other information
Authenticus ID: P-009-PPG
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
Documents
We could not find any documents associated to the publication.
Related Publications

Of the same authors

Incomplete operational transition complexity of regular languages (2015)
Article in International Scientific Journal
Eva Maia; Nelma Moreira; Rogerio Reis
Prefix and Right-Partial Derivative Automata (2015)
Article in International Conference Proceedings Book
Eva Maia; Nelma Moreira; Rogerio Reis
Recommend this page Top
Copyright 1996-2025 © Faculdade de Direito da Universidade do Porto  I Terms and Conditions  I Acessibility  I Index A-Z
Page created on: 2025-07-25 at 17:01:06 | Privacy Policy | Personal Data Protection Policy | Whistleblowing