Decision problems for parameterized top-down tree transducers

Аннотация

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
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover