2 papers
cs.FL2025
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…
cs.DS2025
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…