Compressed Structures for Partial Derivative Automata Constructions

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

Authors

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

Journal

Title: International Journal of Foundations of Computer Science

Pages: 1-23

ISSN: 0129-0541

Publisher: World Scientific

Indexing

ISI Web of Knowledge - 0 Citations

Scopus - 0 Citations

Other information

Authenticus ID: P-017-RC1

DOI: 10.1142/s0129054124420061

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(PDS) from expressions in strong star normal form of size n that runs, on average, in time that asymptotically behaves as n(3/2) (4)root log(n), and space as n(3/2)/(log n)(3/4). Empirical results corroborate its good practical performance.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 23