← All problems
Unverified

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 TT be the set of words encoding correct trees, KK be a regular language of tree with XML(K)\text{XML}(K) the associate languages of words. Can we decide if there exists a regular langage of words LL such that L∩T=XML(K)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

Coming soon

Organizer

Boyuan Wang portraitBoyuan Wang
Minghan Wang portraitMinghan Wang
Bochao Li portraitBochao Li
Hongwei Hu portraitHongwei Hu