Partial Derivative Automaton by Compressing Regular Expressions

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

Autores

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

Ata de Conferência Internacional

Título: Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings

Páginas: 100-112

23rd IFIP WG 1.02 International Conference on Descriptional Complexity of Format Systems, DCFS 2021

5 September 2021 through 5 September 2021

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 1 Citação

Outras Informações

ID Authenticus: P-00V-Z17

DOI: 10.1007/978-3-030-93489-7_9

Abstract (EN): The partial derivative automaton (A(PD)) is an elegant simulation of a regular expression. Although it is, in general, smaller than the position automaton (A(POS)), the algorithms that build A(PD) in quadratic worst-case time, first compute A(POS). Asymptotically, and on average for the uniform distribution, the size of A(PD) is half the size of A(POS), being both linear on the size of the expression. We address the construction of A(PD) efficiently, on average, avoiding the computation of A(POS). The expression and the set of its partial derivatives are represented by a directed acyclic graph with shared common subexpressions. We develop an algorithm for building A(PD)'S from expressions in strong star normal form of size n that runs in time O (n(3/2 ) (4)root log(n) ) and space O (n(3/2) /(log n)(3/4)), on average. Empirical results corroborate its good practical performance.

Idioma: Inglês

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

Nº de páginas: 13