Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
A Survey on Decidable Equivalence Problems for Tree Transducers
View through CrossRef
The decidability of equivalence for three important classes of tree transducers is discussed. Each class can be obtained as a natural restriction of deterministic macro tree transducers (MTTs): (1) no context parameters, i.e., top-down tree transducers, (2) linear size increase, i.e., MSO definable tree transducers, and (3) monadic input and output ranked alphabets. For the full class of mtts, decidability of equivalence remains a long-standing open problem.
World Scientific Pub Co Pte Lt
Title: A Survey on Decidable Equivalence Problems for Tree Transducers
Description:
The decidability of equivalence for three important classes of tree transducers is discussed.
Each class can be obtained as a natural restriction of deterministic macro tree transducers (MTTs): (1) no context parameters, i.
e.
, top-down tree transducers, (2) linear size increase, i.
e.
, MSO definable tree transducers, and (3) monadic input and output ranked alphabets.
For the full class of mtts, decidability of equivalence remains a long-standing open problem.
Related Results
Equivalence of Deterministic Top-Down Tree-to-String Transducers Is Decidable
Equivalence of Deterministic Top-Down Tree-to-String Transducers Is Decidable
We prove that equivalence of deterministic top-down tree-to-string transducers is decidable, thus solving a long-standing open problem in formal language theory. We also present ef...
Translation Equivalence in Horror Movie
Translation Equivalence in Horror Movie
This study aims to analyze how subtitling in Pamali: The Corpse Village preserves elements of fear and cultural meaning through various types of equivalence and pragmatic strategie...
Likvärdighet i idrott och hälsa?
Likvärdighet i idrott och hälsa?
This thesis is about equivalence in the school subject of sports and health. More precisely, the purpose of this thesis is to contribute with new knowledge on how equivalence in sp...
Universality and Almost Decidability
Universality and Almost Decidability
We present and study new definitions of universal and programmable universal unary functions and consider a new simplicity criterion: almost decidability of the halting set. A set ...
Pebble Macro Tree Transducers with Strong Pebble Handling
Pebble Macro Tree Transducers with Strong Pebble Handling
We consider pebble macro tree transducers with call-by-name semantics and strong pebble handling. The latter means that the last dropped pebble can be lifted regardless of the posi...
High Temperature Ultrasonic Transducers: A Review
High Temperature Ultrasonic Transducers: A Review
There are many fields such as online monitoring of manufacturing processes, non-destructive testing in nuclear plants, or corrosion rate monitoring techniques of steel pipes in whi...
Definability Results for Top-Down Tree Transducers
Definability Results for Top-Down Tree Transducers
Top-down tree transducers are well established formalism for describing tree translations. Such transducers can be further enhanced with look-ahead allowing them to inspect input s...
Surface and defect controlled high power piezoelectric ultrasonic transducers
Surface and defect controlled high power piezoelectric ultrasonic transducers
<sec>Researches have shown that a reasonably designed phononic crystal defect structure in high-power piezoelectric ultrasonic transducers can effectively suppress stray vibr...