Polynomial-time equivalence testing for deterministic fresh-register automata
Register automata are one of the most studied automata models over infinite alphabets. The complexity of language equivalence for register automata is quite subtle. In general, the problem is undecidable but, in the deterministic case, it is known to be decidable and in NP. Here we propose a polynom...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
Schloss Dagstuhl
2018
|