On the Mother of All Automata: The Position Automaton

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

Autores

Broda, S (Autor) FCUP; Holzer, M (Autor) Outra; Eva Maia (Autor) FCUP; Nelma Moreira (Autor) FCUP; Rogério Reis (Autor) FCUP

Ata de Conferência Internacional

Título: DEVELOPMENTS IN LANGUAGE THEORY, DLT 2017

Páginas: 134-146

21st International Conference on Developments in Language Theory (DLT)

Liege, BELGIUM, AUG 07-11, 2017

Indexação

ISI Web of Knowledge - 1 Citação

Scopus - 2 Citações

Classificação Científica

CORDIS: Ciências Físicas > Ciência de computadores

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: P-00M-YKQ

DOI: 10.1007/978-3-319-62809-7_9

Abstract (EN): We contribute new relations to the taxonomy of different conversions from regular expressions to equivalent finite automata. In particular, we are interested in ordinary transformations that construct automata such as, the follow automaton, the partial derivative automaton, the prefix automaton, the automata based on pointed expressions recently introduced and studied, and last but not least the position, or Glushkov automaton (A(POS)), and their double reversed construction counterparts. We deepen the understanding of these constructions and show that with the artefacts used to construct the Glushkov automaton one is able to capture most of them. As a byproduct we define a dual version A (POS) over left arrow of the position automaton which plays a similar role as A(POS) but now for the reverse expression. It turns out that although the conversion of regular expressions and reversal of regular expressions to finite automata seems quite similar, there are significant differences.

Idioma: Inglês

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

Nº de páginas: 13