Decision problems for parameterized top-down tree transducers
Received: 20 Oct 2026 Revised: 23 Oct 2026 Accepted: 23 Oct 2026
Published: 2026, vol. 30, issue 4, pp. 58–61
Abstract
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.
Keywords: tree transducers, decision problems, output parameters, computational complexity.
BibTeX
@article{IS-Tang2026,
author = {Tang, Tianxiang},
title = {{Decision problems for parameterized top-down tree transducers}},
journal = {Intelligent Systems. Theory and Applications},
year = {2026},
volume = {30},
number = {4},
pages = {58--61},
}
AMSBIB
\Bibitem{IS-Tang2026}
\by T.~Tang
\paper Decision problems for parameterized top-down tree transducers
\jour Intelligent Systems. Theory and Applications
\yr 2026
\vol 30
\issue 4
\pages 58--61
RU