19.16 Weak validation of tree-languages by extended automata

The weak validation problem is an open problem stated in 2007 by Segoufin and Sirangelo. The problem is about checking if a regular langage of trees, seen as a languages of word (with an XML encoding), can be validated by a finite automaton with the assumption that the input is a correct tree encoding. More formally, let \(T\) be the set of words encoding correct trees, \(K\) be a regular language of tree with \(\text{XML}(K)\) the associate languages of words. Can we decide if there exists a regular langage of words \(L\) such that \(L\cap T =\text{XML}(K)\).

Weak validation sounds out of reach and a very difficult question although generalisation of the problem considering extended version of finite automata (e.g. Parikh automaton) could be in same time easier to deal with and provides a more interesting class of weakly validating regular languages of trees.

Some recent work on a close subject:

Eryk Kopczyński. 2016. Invisible Pushdown Languages. LICS '16