On the size of partial derivatives and the word membership problem

• Type: Article in International Scientific Journal
• Date: 2021

Authors

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

Journal

Title: Acta Informatica

Vol. 58

Pages: 357-375

ISSN: 0001-5903

Publisher: Springer Nature

Indexing

ISI Web of Knowledge - 3 Citations

Scopus - 3 Citations

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 19