Partial Derivative Automaton for Regular Expressions with Shuffle

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

Autores

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

Ata de Conferência Internacional

Título: Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015, Waterloo, ON, Canada, June 25-27, 2015. Proceedings

Páginas: 21-32

Indexação

Scopus - 0 Citações

Classificação Científica

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

Outras Informações

ID Authenticus: P-00G-6GC

DOI: 10.1007/978-3-319-19225-3_2

Abstract (EN): We generalize the partial derivative automaton to regular expressions with shuffle and study its size in the worst and in the average case. The number of states of the partial derivative automata is in the worst case at most 2m, where m is the number of letters in the expression, while asymptotically and on average it is no more than (4\3)m. © Springer International Publishing Switzerland 2015.

Idioma: Inglês

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