Automata for regular expressions with shuffle

• Tipo: Artigo em Revista Científica Internacional
• Data: 2018

Autores

Broda, S (Autor) FCUP; António Machiavelo (Autor) FCUP; Nelma Moreira (Autor) FCUP; Rogério Reis (Autor) FCUP

Revista

Título: Information and Computation

Vol. 259

Páginas: 162-173

ISSN: 0890-5401

Editora: Elsevier

Indexação

ISI Web of Knowledge - 13 Citações

Scopus - 16 Citações

Outras Informações

ID Authenticus: P-00N-R77

DOI: 10.1016/j.ic.2017.08.013

Abstract (EN): We generalize the partial derivative automaton and the position automaton to regular expressions with shuffle, and study their state complexity in the worst, as well as in the average case. The number of states of the partial derivative automaton (A(pd)) is, in the worst case, at most 2(m), where mis the number of letters in the expression. The asymptotic average is bounded by (4/3)(m). We define a position automaton (A(pos)) that is homogeneous, but in which several states can correspond to a same position, and we show that Apdis a quotient of A(pos). The number of states of the position automaton is at most 1 + m(2(m)-1), while the asymptotic average is no more than m(4/3)(m). (c) 2017 Published by Elsevier Inc.

Idioma: Inglês

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

Nº de páginas: 12