16 citations · 48 across the 14 of their papers we have counts for
5 papers · 1 filter
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…
Ranked enumeration of MSO logic on words
Pierre Bourhis, Alejandro Grez, Louis Jachiet +1
In the last years, enumeration algorithms with bounded delay have attracted a lot of attention for several data management tasks. Given a query and the data, the task is to preproc…
The monitoring problem for timed automata
Alejandro Grez, Filip Mazowiecki, Michał Pilipczuk +2
We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so under a…
Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties
Filip Mazowiecki, Cristian Riveros
Cost register automata (CRA) and its subclass, copyless CRA, were recently proposed by Alur et al. as a new model for computing functions over strings. We study some structural pro…