Checking in polynomial time whether or not a regular tree language is deterministic top-down

Sebastian Maneth, Helmut Seidl

Publikation: Beitrag in FachzeitschriftArtikelBegutachtung

1 Zitat (Scopus)

Abstract

It is well known that for a given bottom-up tree automaton it can be decided whether or not an equivalent deterministic top-down tree automaton exists. Recently it was claimed that such a decision can be carried out in polynomial time (Leupold and Maneth, FCT'2021); but their procedure and corresponding property is wrong. Here we address this mistake and present a correct property which allows to determine in polynomial time whether or not a given tree language can be recognized by a deterministic top-down tree automaton. Furthermore, our new property is stated for arbitrary deterministic bottom-up tree automata, and not only for minimal such automata (as before).

OriginalspracheEnglisch
Aufsatznummer106449
FachzeitschriftInformation Processing Letters
Jahrgang184
DOIs
PublikationsstatusVeröffentlicht - Feb. 2024

Fingerprint

Untersuchen Sie die Forschungsthemen von „Checking in polynomial time whether or not a regular tree language is deterministic top-down“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren