38 citations · 99 across the 20 of their papers we have counts for
3 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…