103 citations · 300 across the 45 of their papers we have counts for
4 papers · 1 filter
Locality Testing for NFAs is PSPACE-complete
Antoine Amarilli, Mikaël Monet, Rémi De Pretto
The class of local languages is a well-known subclass of the regular languages that admits many equivalent characterizations. In this short note we establish the PSPACE-completenes…
Confluence of the Node-Domination and Edge-Domination Hypergraph Rewrite Rules
Antoine Amarilli, Mikaël Monet, Rémi De Pretto
In this note, we study two rewrite rules on hypergraphs, called edge-domination and node-domination, and show that they are confluent. These rules are rather natural and commonly u…
On the Complexity of Language Membership for Probabilistic Words
Antoine Amarilli, Mikaël Monet, Paul Raphaël +1
We study the membership problem to context-free languages (CFLs) on probabilistic words, that specify for each position a probability distribution on the letters. Our task is to co…
Dynamic Membership for Regular Tree Languages
Antoine Amarilli, Corentin Barloy, Louis Jachiet +1
We study the dynamic membership problem for regular tree languages under relabeling updates: we fix an alphabet and a regular tree language over (expressed, e.g., as a…