Intelligent Systems.
Theory and Applications

(Intellektual'nye Sistemy. Teoriya i Prilozheniya)

Decision problems for parameterized top-down tree transducers

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
Published under Creative Commons Attribution 4.0 International (CC BY 4.0)

← Back to issue

× Issue cover