Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Efficient Enumeration for Annotated Grammars
Indexado
WoS WOS:000850439300025
Scopus SCOPUS_ID:85131631625
DOI 10.1145/3517804.3526232
Año 2022
Tipo proceedings paper

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



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 is more expressive than 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 that generalize regular spanners for which linear time preprocessing suffices.

Revista



Revista ISSN
978-1-4503-9260-0

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Sin Disciplinas
Scopus
Sin Disciplinas
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 Amarilli, Antoine Hombre Institut Polytechnique de Paris - Francia
Inst Polytech Paris - Francia
2 Jachiet, Louis Hombre Institut Polytechnique de Paris - Francia
Inst Polytech Paris - Francia
3 Muñoz, Martín Hombre Pontificia Universidad Católica de Chile - Chile
4 Riveros, Cristian Hombre Pontificia Universidad Católica de Chile - Chile
5 ACM Corporación

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
Deutsche Forschungsgemeinschaft
Deutsche Forschungsgemeinschaft (DFG, German Research Foundation)
ANR project
Agencia Nacional de Investigación y Desarrollo
ANID - Millennium Science Initiative Program

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
Acknowledgements. Amarilli was partially supported by the ANR project EQUUS ANR-19-CE48-0019 and by the Deutsche Forschungs-gemeinschaft (DFG, German Research Foundation) – 431183758. Muñoz and Riveros were funded by ANID - Millennium Science Initiative Program - Code ICN17_002.
Amarilli was partially supported by the ANR project EQUUS ANR-19-CE48-0019 and by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) - 431183758. Munoz and Riveros were funded by ANID - Millennium Science Initiative Program - Code ICN17_002.

Muestra la fuente de financiamiento declarada en la publicación.