Information Technology Reference
In-Depth Information
ETOL-systems and EDTOL-systems are EOL-systems and EDOL-systems, re-
spectively, where instead of a poly-morphism, a set of morphisms is given, which
is called a
table
. In this case, at each rewriting step, one morphism of the table is
chosen.
Example 2.7.
The following EDTOL-system, with a table of two morphisms, gen-
erates the tri-somatic language.
⎛
⎞
⎛
⎞
ABCabc
↓↓↓↓↓↓
aA bB cC a b c
ABCabc
↓↓↓↓↓↓
abcabc
⎝
⎠
μ
2
=
⎝
⎠
.
μ
1
=
2.6.1
String Models and Theories
A string model is a relational structure (see Chap. 5) having a set of strings as do-
main. A powerful way of expressing rewriting rules and generation strategies is by
means of logical formalisms [204].
A
string theory
or a
monoidal theory
, over the alphabet
A
, is a theory in-
cluding, as terms, the
free monoid
generated by the alphabet
A
. This means that the
signature of
T
T
includes the symbols of
A
(as individual constants), a symbol for the
empty string
, and a symbol for concatenation, which we denoted in the usual way
(by juxtaposition), and its axioms include the monoid axioms (x, y, z variables of
strings):
λ
(
xy
)
z
=
x
(
yz
)
x
λ
=
λ
x
=
x
.
In a string theory over the alphabet
A
terms, possibly with variables, include the
symbols of
A
and variables ranging over strings of
A
∗
.
A language
L
is a set of strings, therefore
L
can be defined by means of a formula;
within a string theory
ϕ
(
x
)
(with a free variable
x
):
L
=
{
α
|T |
=
ϕ
(
α
)
}.
In this case
is the logical consequence relation that can be computed by any
logical calculus of predicate logic.
Given a grammar
G
|
=
, the string theory of Table 2.9, over the alphabet
A
, provides the logical deduction of a formula
Generate
=(
A
,
T
,
S
,
R
)
(
ϕ
)
if and only if
ϕ
∈
L(
G
)
(the language generated by the grammar
G
).
The following example is an (equational) monoidal theory that deduces the de-
velopment
R
at stage
n
of a Red Alga, a primitive organism that grows according
to the following law.
(
n
)
