Hardware Reference
In-Depth Information
Part I
Theory of Equations Over Languages and
Automata
In this part we present the basics of equations over languages and automata, and
specialize the theory to finite and
-regular languages.
In Chap. 2 we define and study
abstract equations over languages
, to obtain
results valid for any language equation. We investigate two composition operators
for abstract languages: synchronous composition,
!
, and parallel composition,
˘
,
and we check conformity by language containment.
A key contribution is the
computation of the most general solutions
of the
language eq
uation
s
A X C
and
A ˘ X C
, found respectively as
S D A C
,
and
. The derivation sheds lights on the properties required of a
composition operator to yield such a closed formula as the largest solution, and
explains when different equations give rise to that same type of solution formula.
These formulas turn out to subsume a panoply of specialized solutions derived in
the past for specific composition operators and topologies. Some common network
topologies are shown in Fig.
1.1
.
Then in Chap. 3 we specialize language equations to languages associated with
classes of automata used for modeling hardware and software systems, namely,
regular languages as counterparts of finite automata, FSM languages as counterparts
of FSMs. Thus we can operate algorithmically on those languages through their
automata and study how to solve effectively their related language equations.
It is important to find solutions within the same language class of the equation,
e.g., when studying FSM language equations we look for solutions that are FSM
languages. Moreover, we are interested in subsets of solutions characterized by
further properties of practical interest, e.g., FSM languages that satisfy the Moore
property; thus the solutions are restricted further.
In Chap. 4 we study the extensions to equations over
S D A ˘ C
!
-automata of the results
obtained in the finite regular case.
Various contributions, investigating partial aspects of the topic of this research,
have been published. A complete survey is provided in Chap. 5.
