Idioma:

Node Query Preservation for Deterministic Linear Top-Down Tree Transducers

Miyahara, Kazuki ; Hashimoto, Kenji ; Seki, Hiroyuki

IEICE transactions on information and systems, 2015-05, Vol.E98.D (3), p.512-523 [Periódico revisado por pares]

Texto completo disponível

Citações Citado por

Título:
Node Query Preservation for Deterministic Linear Top-Down Tree Transducers
Autor: Miyahara, Kazuki ; Hashimoto, Kenji ; Seki, Hiroyuki
Assuntos: Automation ; Preservation ; Preserves ; Query processing ; Transducers ; Transformations ; Trees
É parte de: IEICE transactions on information and systems, 2015-05, Vol.E98.D (3), p.512-523
Notas: ObjectType-Article-1
SourceType-Scholarly Journals-1
ObjectType-Feature-2
content type line 23
Descrição: This paper discusses the decidability of node query preservation problems for tree transducers. We assume a transformation given by a deterministic linear top-down data tree transducer (abbreviated as DLT super(V)) and an n-ary query based on runs of a tree automaton. We say that a DLT super(V) Tr strongly preserves a query Q if there is a query Q' such that for every tree t, the answer set of Q' for Tr(t) is equal to the answer set of Q for t. We also say that Tr weakly preserves Q if there is a query Q' such that for every t, the answer set of Q' for Tr(t) includes the answer set of Q for t. We show that the weak preservation problem is coNP-complete and the strong preservation problem is in 2-EXPTIME. We also show that the problems are decidable when a given transducer is a functional extended linear top-down data tree transducer with regular look-ahead, which is a more expressive transducer than DLT super(V).
Idioma: Japonês

Voltar para lista de resultados