Superlinear deterministic top-down tree transducers

Autor:	G. Dányi, Zoltán Fülöp
Rok vydání:	1996
Předmět:	Discrete mathematics Class (set theory) Hierarchy (mathematics) General Mathematics Exponential tree Composition (combinatorics) Theoretical Computer Science Combinatorics Tree (descriptive set theory) Computational Theory and Mathematics Closure (mathematics) Theory of computation Homomorphism Mathematics
Zdroj:	Mathematical Systems Theory. 29:507-534
ISSN:	1433-0490 0025-5661
DOI:	10.1007/bf01184813
Popis:	Denote byDT, l-DT, andnd-HOM the class of tree transformations induced by deterministic top-down tree transducers, linear deterministic top-down tree transducers, and nondeleting homomorphism tree transducers, respectively. In this paper the classsl-DT of tree transformations induced by superlinear deterministic top-down tree transducers is considered. Some basic properties ofsl-DT are shown. Among others, it is proved thatsl-DT is not closed under composition; thatl-DT—sl-DT + ≠ O withsl-DT + being the closure ofsl-DT under composition; and thatDT = nd-HOM o sl-DT, where o denotes the operation composition of two classes. Then the hierarchy {sl-DT n n> 1} is shown to be proper, meaning thatsl-DT n ⊂sl-DT n+1, forn≥ 1. Moreover, the same is proved for the hierarchy {t-sl-DT n n ≥ 1}, wheret-sl-DT is the subclass ofsl-DT induced by total deterministic superlinear top-down tree transducers.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d2e804d928518d13751a1dfd578c19a2 https://doi.org/10.1007/bf01184813 Zobrazit plný text záznamu Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.