It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton.
Mikolaj BojanczykPublished in: Fundam. Informaticae (2017)
Keyphrases
- regular tree languages
- tree automata
- tree languages
- regular expressions
- finite automata
- finite state
- xml schema
- sufficient conditions
- database
- context free grammars
- markov chain
- ordered trees
- markov decision processes
- deterministic finite automata
- pattern matching
- tree structure
- xml documents
- finite state automaton
- databases