Functionality of compositions of top-down tree transducers is decidable

Sebastian Maneth; Helmut Seidl; Martin Vu

doi:10.1016/j.ic.2023.105131

Functionality of compositions of top-down tree transducers is decidable

Sebastian Maneth, Helmut Seidl, Martin Vu

Informatics 2 - Chair of Formal Languages, Compiler Construction, Software Construction

University of Bremen

Research output: Contribution to journal › Article › peer-review

1 Scopus citations

Abstract

We prove that functionality of compositions of top-down tree transducers is decidable by reducing the problem to the functionality of one top-down tree transducer with look-ahead.

Original language	English
Article number	105131
Journal	Information and Computation
Volume	296
DOIs	https://doi.org/10.1016/j.ic.2023.105131
State	Published - Jan 2024

Keywords

Decidability
Functionality
Top-down tree transducer

Access to Document

10.1016/j.ic.2023.105131

Cite this

@article{158aa49889e64d60afa0e5ec6e2baeac,

title = "Functionality of compositions of top-down tree transducers is decidable",

abstract = "We prove that functionality of compositions of top-down tree transducers is decidable by reducing the problem to the functionality of one top-down tree transducer with look-ahead.",

keywords = "Decidability, Functionality, Top-down tree transducer",

author = "Sebastian Maneth and Helmut Seidl and Martin Vu",

note = "Publisher Copyright: {\textcopyright} 2023 The Author(s)",

year = "2024",

month = jan,

doi = "10.1016/j.ic.2023.105131",

language = "English",

volume = "296",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier Inc.",

}

TY - JOUR

T1 - Functionality of compositions of top-down tree transducers is decidable

AU - Maneth, Sebastian

AU - Seidl, Helmut

AU - Vu, Martin

PY - 2024/1

Y1 - 2024/1

N2 - We prove that functionality of compositions of top-down tree transducers is decidable by reducing the problem to the functionality of one top-down tree transducer with look-ahead.

AB - We prove that functionality of compositions of top-down tree transducers is decidable by reducing the problem to the functionality of one top-down tree transducer with look-ahead.

KW - Decidability

KW - Functionality

KW - Top-down tree transducer

UR - http://www.scopus.com/inward/record.url?scp=85180268899&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2023.105131

DO - 10.1016/j.ic.2023.105131

M3 - Article

AN - SCOPUS:85180268899

SN - 0890-5401

VL - 296

JO - Information and Computation

JF - Information and Computation

M1 - 105131

ER -

Functionality of compositions of top-down tree transducers is decidable

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this