Decision problems for parameterized top-down tree transducers
Получена: 20.10.2026 Доработана: 23.10.2026 Принята: 23.10.2026
Опубликована: 2026 год, том 30, выпуск 4, С. 58–61
Аннотация
This paper presents the results of a study on the complexity of certain decision problems—membership, equivalence, unification, and functionality—for top-down tree transducers (TDTs) with output parameters (PTDTs). Membership problem is \(\mathsf {L}\)-complete for deterministic models DTDTs and PDTDTs, belongs to \(\mathsf {LOGCFL}\) for TDTs, and it is \(\mathsf {NP}\)-complete for PTDTs. Equivalence checking of complete DTDTs and PDTDTs can be performed in cubic time. The same time \(O(n^3)\) is required for computing the most general unifier of a pair of PDTDTs as well as for computing the functional instance of a PTDT. Minimization of complete PDTDTs is \(\mathsf {NP}\)-complete in contrast with polynomial-time complexity of minimization problem for DTDTs.
Ключевые слова: tree transducers, decision problems, output parameters, computational complexity.
BibTeX
@article{IS-Tang2026,
author = {Tang, Tianxiang},
title = {{}},
journal = {Интеллектуальные системы. Теория и приложения},
year = {2026},
volume = {30},
number = {4},
pages = {58--61},
}
AMSBIB
\RBibitem{IS-Tang2026}
\by T.~Tang
\paper
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 58--61
EN