期刊
INFORMATION PROCESSING LETTERS
卷 184, 期 -, 页码 -出版社
ELSEVIER
DOI: 10.1016/j.ipl.2023.106449
关键词
Automata; Trees; Deterministic top-down
It is well known that the existence of an equivalent deterministic top-down tree automaton can be determined for a given bottom-up tree automaton. However, a recent claim of polynomial time decision-making for this has been proven wrong. In this paper, we address this mistake and present a correct property that allows for the determination of whether or not a given tree language can be recognized by a deterministic top-down tree automaton in polynomial time. Furthermore, our new property is applicable to arbitrary deterministic bottom-up tree automata, not just minimal ones as previously believed.
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).(c) 2023 Published by Elsevier B.V.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据