In
theoretical computer science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory.
It is difficult to circumsc ...
and
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
, a tree transducer (TT) is an
abstract machine
An abstract machine is a computer science theoretical model that allows for a detailed and precise analysis of how a computer system functions. It is analogous to a mathematical function in that it receives inputs and produces outputs based on pre ...
taking as input a
tree
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants with secondary growth, plants that are ...
, and generating output – generally other trees, but models producing
words
A word is a basic element of language that carries an objective or practical meaning, can be used on its own, and is uninterruptible. Despite the fact that language speakers often have an intuitive grasp of what a word is, there is no consen ...
or other structures exist. Roughly speaking, tree transducers extend
tree automata
A tree automaton is a type of state machine. Tree automata deal with tree structures, rather than the strings of more conventional state machines.
The following article deals with branching tree automata, which correspond to regular languages ...
in the same way that
word transducers extend
word automata.
Manipulating tree structures instead of words enable TT to model syntax-directed transformations of formal or natural languages. However, TT are not as well-behaved as their word counterparts in terms of
algorithmic complexity
Algorithmic may refer to:
*Algorithm, step-by-step instructions for a calculation
**Algorithmic art, art made by an algorithm
**Algorithmic composition, music made by an algorithm
** Algorithmic trading, trading decisions made by an algorithm
**Alg ...
,
closure properties, etcetera. In particular, most of the main classes are not closed under
composition
Composition or Compositions may refer to:
Arts and literature
*Composition (dance), practice and teaching of choreography
*Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include v ...
.
The main classes of tree transducers are:
Top-Down Tree Transducers (TOP)
A TOP ''T'' is a tuple (''Q'', Σ, Γ, ''I'', δ) such that:
* ''Q'' is a
finite set
In mathematics, particularly set theory, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,
:\
is a finite set with five elements. Th ...
, the set of ''states'';
* Σ is a finite
ranked alphabet In theoretical computer science and formal language theory, a ranked alphabet is a pair of an Alphabet (computer science), ordinary alphabet ''F'' and a function ''Arity'': ''F''→\mathbb. Each letter in ''F'' has its arity so it can be used to bui ...
, called the ''input alphabet'';
* Γ is a finite ranked alphabet, called the ''output alphabet'';
* ''I'' is a
subset
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
of ''Q'', the set of ''initial states''; and
*
is a set of ''rules'' of the form
, where ''f'' is a symbol of Σ, ''n'' is the arity of ''f'', ''q'' is a state, and ''u'' is a tree on Γ and
, such pairs being
nullary
Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. ...
.
Examples of rules and intuitions on semantics
For instance,
:
is a rule – one customarily writes
instead of the pair
– and its intuitive semantics is that, under the action of ''q'', a tree with ''f'' at the root and three children is transformed into
:
where, recursively,
and
are replaced, respectively, with the application of
on the first child and
with the application of
on the third.
Semantics as
term rewriting
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or reduc ...
The
semantics
Semantics (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy
Philosophy (f ...
of each state of the transducer ''T'', and of ''T'' itself, is a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
between input trees (on Σ) and output trees (on Γ).
A way of defining the semantics formally is to see
as a
term rewriting system
In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known as rewrite systems, rewrite engines, or red ...
, provided that in the right-hand sides the calls are written in the form
, where states ''q'' are unary symbols. Then the semantics