16 citations · 48 across the 14 of their papers we have counts for
3 papers · 1 filter
Constant-delay enumeration for SLP-compressed documents
Martín Muñoz, Cristian Riveros
We study the problem of enumerating results from a query over a compressed document. The model we use for compression are straight-line programs (SLPs), which are defined by a cont…
Probabilistic Automata of Bounded Ambiguity
Nathanaël Fijalkow, Cristian Riveros, James Worrell
Probabilistic automata are an extension of nondeterministic finite automata in which transitions are annotated with probabilities. Despite its simplicity, this model is very expres…
Efficient Enumeration Algorithms for Annotated Grammars
Antoine Amarilli, Louis Jachiet, Martín Muñoz +1
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…