On the size of partial derivatives and the word membership problem

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

Autores

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

Revista

Título: Acta Informatica

Vol. 58

Páginas: 357-375

ISSN: 0001-5903

Editora: Springer Nature

Indexação

ISI Web of Knowledge - 3 Citações

Scopus - 3 Citações

Outras Informações

ID Authenticus: P-00V-5J8

DOI: 10.1007/s00236-021-00399-6

Abstract (EN): Partial derivatives are widely used to convert regular expressions to nondeterministic automata. For the word membership problem, it is not strictly necessary to build an automaton. In this paper, we study the size of partial derivatives on the average case. For expressions in strong star normal form, we show that on average and asymptotically the largest partial derivative is at most half the size of the expression. The results are obtained in the framework of analytic combinatorics considering generating functions of parametrised combinatorial classes defined implicitly by algebraic curves. Our average case estimates suggest that a detailed word membership algorithm based directly on partial derivatives should be analysed both theoretically and experimentally.

Idioma: Inglês

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

Nº de páginas: 19