Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Fundamenta Informaticae

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

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

Bojańczyk M.

Fundamenta Informaticae

2017

Vol. 154, nr 1/4

37--46

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].

On the Borel Complexity of MSO Definable Sets of Branches

Bojańczyk M., Niwiński D., Rabinovich A., Radziwończyk–Syta A., Skrzypczak M.

Fundamenta Informaticae

2010

Vol. 98, nr 4

337-349

An infinite binaryword can be identified with a branch in the full binary tree. We consider sets of branches definable in monadic second-order logic over the tree, where we allow some extra monadic predicates on the nodes. We show that this class equals to the Boolean combinations of sets in the Borel class Σ over the Cantor discontinuum. Note that the last coincides with the Borel complexity of ω-regular languages.