Efficient enumeration algorithms for annotated grammars - Equipe Data, Intelligence and Graphs Accéder directement au contenu
Communication Dans Un Congrès Année : 2022

Efficient enumeration algorithms for annotated grammars

Résumé

We introduce annotated grammars, an extension of context-free grammars which allows annotations on terminals. Our model extends the standard notion of regular spanners, and has the same expressiveness as the extraction grammars recently introduced by Peterfreund. We study the enumeration problem for annotated grammars: fixing a grammar, and given a string as input, enumerate all annotations of the string that form a word derivable from the grammar. Our first result is an algorithm for unambiguous annotated grammars, which preprocesses the input string in cubic time and enumerates all annotations with output-linear delay. This improves over Peterfreund's result, which needs quintic time preprocessing to achieve this delay bound. We then study how we can reduce the preprocessing time while keeping the same delay bound, by making additional assumptions on the grammar. Specifically, we present a class of grammars which only have one derivation shape for all outputs, for which we can enumerate with quadratic time preprocessing. We also give classes generalizing regular spanners for which linear time preprocessing suffices.

Dates et versions

hal-03654592 , version 1 (28-04-2022)

Identifiants

Citer

Antoine Amarilli, Louis Jachiet, Martín Muñoz, Cristian Riveros. Efficient enumeration algorithms for annotated grammars. PODS 2022, Jun 2022, Philadelphie, United States. ⟨10.1145/3517804.3526232⟩. ⟨hal-03654592⟩
56 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More