It is Undecidable if Two Regular Tree Languages can be Separated by a Deterministic Tree-walking Automaton

Issue title: Elegant Structures in Computation. To Andrzej Ehrenfeucht on His 85th Birthday

Guest editors: Gheorghe Păun, Grzegorz Rozenberg and Arto Salomaa

Article type: Research Article

Authors: Bojańczyk, Mikołaj^{; *; †}

Affiliations: The University of Warsaw, Institute of Informatics, Banacha 2, 02-097 Warsaw, Poland. bojan@mimuw.edu.pl

Correspondence: [*] Address for correspondenece: The University of Warsaw, Institute of Informatics, Banacha 2, 02-097 Warszawa, Poland

Note: [†] The work was supported by the grant Lipa, which has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No 683080).

Abstract: The following problem is shown undecidable: given regular languages L, K of finite trees, decide if there exists a deterministic tree-walking automaton which accepts all trees in L and rejects all trees in K. The proof uses a technique of Kopczyński from [1].

DOI: 10.3233/FI-2017-1551

Journal: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 37-46, 2017