Kudryavtsev V.B., Rosenberg I.G. Structural Theory of Automata, Semigroups, and Universal Algebra

Подождите немного. Документ загружается.

236 V. B. Kudryavtsev

V. A. Buyevich proved the following assertion.

7.2 Theorem For any l from N

there exists an algorithm which establishes for a ﬁnite set

of f.a. functions in P

a,l,k

whether it is a Slupecki system.

A precomplete class of the main P.s.a.f. is called a Slupecki class if it contains all homoge-

neous functions from the carrier of P.s.a.f. It is interesting to compare Theorems 7.1 and 7.2

with the following assertion.

7.3 Theorem The cardinality of the set of Slupecki classes is equal to the continuum in the

f.s.’s P

a,l,k

and P

∗

a,l,k

, and is equal to the hypercontinuum in the f.s.’s P

a,l

and P

∗

a,l

, for any

l from N

This assertion indicates a very important diﬀerence in completeness conditions in the

general case and in the case of Slupecki systems. Note that the hypercontinuum property

in this theorem remains valid also for f.s. functions which are obtained from a. functions by

extending the value of the parameter l to countable. The second approach was ﬁrst realized

in the form of the following assertion.

7.4 Theorem [5] For any l in N

, there exists an algorithm which establishes for any ﬁnite

set M ⊆ P

a,l,k

whether the set M ∪ P

a,l,k,t

is complete in P

∗

a,l,k

Later on this approach was developed for l = 2 in the following way. Let Q be a closed

Post class of Boolean functions. We interpret these functions as truth f.a. functions. Denote

by K

the class of all ﬁnite sets M of f.a. functions from P

a,2,k

such that M ⊇ Q.Our

primary interest here is the existence of an algorithm which establishes for any M from K

whether the set is complete in P

∗

a,2,k

(to be more exact, for which Q this algorithm exists).

It is clear that if such an algorithm exists for some Q, then it also exists for any Post class



such that Q



⊇ Q. On the contrary, if such an algorithm does not exist, then it does

not exist for any Post class Q



⊆ Q. Thus, the separation of algorithmically decidable cases

from algorithmically undecidable ones is achieved by indicating such a family Φ of the Post

classes Q for which the completeness property is not algorithmically decidable. However for

any Post class such that Q



⊃ Q it is decidable.

7.5 Theorem [6] The family Φ is equal to

Φ={F

∞

A special case of this assertion is Theorem 7.4 for l = 2. As is shown in [6], the assertion

of Theorem 7.5 holds also for the case of A-completeness with the proper interpretation of

the set Φ.

8 Linear a. functions

An a. function from P

a,l,k

is linear (l.a.f.) if in its system (5.1) the vector-functions φ and

ψ are linear modulo l with respect to their variables. Denote by L

a,l,k

the class of all linear

a. functions. It is not diﬃcult to see that I

Ω

es,F

a,l,k

)=L

a,l,k

. Let us consider the f.s.

a,l,k

=(L

a,l,k

, Ω

)andL

∗

a,l,k

=(L

a,l,k

, Ω

es,F

On the automata functional systems 237

8.1 Theorem Among the f.s. L

a,l,k

and L

∗

a,l,k

,onlyL

∗

a,l,k

is ﬁnitely-generated.

A solution of the completeness problem for L

∗

a,l,k

is obtained for l = 2, and we present it [9]

using the notation L

instead of L

a,l,k

and the notation L

instead of L

a,l,k

.LetΓ

, a ∈ E

,be

the class of all B.f. f(x

,...,x

)=(y

,...,y

) such that f (a,a,...,a)=(a,a,...,a).

It is said that a B.f. f (x

,...,x

) depends on x

with a shift, if in its system (5.1), x

absent in the equations for ψ;otherwisex

, is called an immediate variable.LetV

be the

class of all B.f. having no more than one immediate variable. Let V

be the class of all B.f.

having an odd number of immediate variables. Denote by R

the class of all B.f. having

exactly one essential variable, and by R

, the class of all B.f. with exactly one immediate

variable. The class of all B.f. without immediate variables is denoted by C.Letα

[0] be the

word of length s of the form 00 ...0. Denote by L

the class of all B.f. f(x

,...,x

)such

that

f(α

[0],α

[0],...,α

[0]) = (α

[0],α

[0],...,α

[0])

for any s in N.LetL

be the class of all B.f.’s of one variable and L

= L

∩L

.Denoteby

[z] the ring of polynomials in z over the ﬁeld E

with the usual operations of addition and

multiplication of polynomials. For {u, v, u



}⊂E

[z] we consider the fractions u/v, u



which we assume equal if uu

= u



and vu

= v



for some u

, u

in E

[z] \{0}.The

degree of a polynomial u is denoted by deg u.LetQ

(z) be the set of all fractions u/v, u/v is

incontractible, v ∈ E

[z] \{0},thenv is not divided by z. It is possible to show that L

and

(z) are isomorphic (we write ∼) and retain the operations of addition and multiplication;

therefore they are identical in a sense.

Let u/v ∈ Q

(z), f ∈ L

and u/v ∼ f.Itissaidthatf possesses the O-property if either

u/v ∈ R

and deg u =degv,oru/v /∈ R

and deg u<deg v. We consider polynomials

from Q

(z) ordered according to ascending degree, i.e., deg p

≤ deg p

i+i

for i ∈ N ,and

let p

= ξ.Ifu + v or u is divisible by ξp

,thenwesaythatf possesses the i-property.

If deg u<deg v,thenf possesses the O



-property;ifdegu ≤ deg v,thenf possesses the



-property.Ifu is divided by p

then f possesses i



-property;ifv is not divisible by p

,then

it possesses i



-property.

Let M

(1)

consist of all B.f. f having i-property, i ∈ N

,andletR

(1)

consist of all B.f. f

with the i



-property.

For a B.f. f(x

,...,x

) there exist functions f

),f

),...,f

)fromL

and γ

from C such that

f(x

,...,x



i=1

)+γ (mod 2).

Denote the set of functions f

,...,f

by µ(f ). Let M

consist of all B.f.’s f such that

µ(F ) ⊂ M

(1)

.LetaB.f.f satisfy the following property: if x

is the only essential variable,

then f

in µ(f) possesses the i



-property; and if the indicated property is absent in x

,then

possesses the i



-property. The class of such f is denoted by R

Let a B.f. f satisfy the following property: if x

is the only immediate variable, then f

in µ(f ) possesses the i



-property; otherwise f possesses the i



-property. The class of such f

is denoted by R

Denote by J the family consisting of all classes Γ

, Γ

for i ∈ N

j ∈ N.

238 V. B. Kudryavtsev

8.2 Theorem [9] The relation Σ

∗

)=J holds.

Thus in the f.s. L

∗

there is only a countable set of precomplete classes and by virtue of

the fact that L

∗

is ﬁnitely generated they form a criterial system. By analogy with the case

of functions with delays the following assertion holds.

8.3 Theorem [9] There is an algorithm establishing whether any ﬁnite system of B.f.’s in

∗

is complete.

References

[1] S. V. Aleshin, On the absence of bases in some classes of initial automata, Probl. Cybern.

22 (1970), 67–75 (Russian).

[2] S. V. Aleshin, Finite automata and the Burnside problem for torsion groups, Math.

Notes 29 (1972), 319–328 (Russian).

[3] D. N. Babin, On superpositions of bounded-determined functions, Math. Notes 47

(1990), 3–10 (Russian).

[4] D. N. Babin, On completeness of the binary boundedly determined functions with respect

to superposition, Discrete Math. Appl. 1 (1991), 423–431.

[5] D. N. Babin, A decidable case of the completeness problem for automata functions,

Diskretnaya Matematika 4 (4) (1992), 41–55 (Russian).

[6] D. N. Babin, Undecidability of the completeness and A-completeness problems for some

systems of automaton functions, Discrete Math. Appl. 5 (1995), 31–42.

[7] V. A. Buyevich, On algorithmic unsolvability of A-completeness recognition for bounded-

determined functions, Math. Notes 29 (1972), 687–697 (Russian).

[8] V. A. Buyevich, On r-completeness in the class of determined functions, Soviet Acad.

Sci. Dokl. 326 (1992), 399–404 (Russian).

[9] A. A. Chasovskikh, On completeness in the linear automata class, Math.Probl.Cybern.

3 (1995), 140–166 (Russian).

[10] L. Chzhu-Kai, Precomplete classes determined by the k-nary relations in k-valued logic,

Acta Sci. Natur. Univ. Jilinensis 3 (1964).

[11] L. Chzhu-Kai and Lu.Sui-Khua, Precomplete classes determined by the binary relations

in many-valued logic, Acta Sci. Natur. Univ. Jilinensis 4 (1964).

[12] P. Cohn, Universal Algebra, Wiley, New York, 1965.

[13] J. Dassow, Ein modiﬁzierter Vollst¨andigkeitsbergiﬀ in einen Algebra von Automatenab-

bildungen, Dissertation fur Doctor B, Uni Rostock, 1978.

[14] K. B. Kolyada, On completeness of regular transformations, Ph.D. thesis, Moscow State

University, 1987 (Russian).

On the automata functional systems 239

[15] M. I. Kratko, Algoritmic undecidability of the completeness recognition problem for

ﬁnite automata, Soviet Acad. Sci. Dokl. 155 (1964), 35–37 (Russian).

[16] V. B. Kudryavtsev, A completeness theorem for one class of automata without feedback,

Probl. Cybern. 8 (1962), 91–115 (Russian).

[17] V. B. Kudryavtsev, On the cardinality of the sets of precomplete sets of some functional

systems connected with automata, Probl. Cybern. 13 (1965), 45–74 (Russian).

[18] V. B. Kudryavtsev, Functional Systems, Moscow Univ. Press, Moscow, 1982 (Russian).

[19] V. B. Kudryavtsev, S. V. Aleshin, and A. S. Podkolzin, An Introduction to Automata

Theory, Nauka, Moscow, 1985 (Russian).

[20] A. I. Maltsev, Iterative algebras and the Post’s varieties, Algebra and Logic 5 (2) (1966),

5–24 (Russian).

[21] V. V. Martynyuk, An investigation of some classes of functions in many-valued logic,

Probl. Cybern. 3 (1960), 49–60 (Russian).

[22] J. McCarthy and C. A. Shannon, eds., Automata Studies, Princeton Univ. Press, Prince-

ton, 1956.

[23] A. S. Strogalov, On ε-modelling of ﬁnite automata behavior, Ph.D. thesis, Moscow State

University, 1985 (Russian).

[24] E. Post, Two-valued Iterative Systems of Mathematical Logic, Princeton Univ. Press,

Princeton, 1941.

[25] I. G. Rosenberg and T. Hikita, Completeness for uniformly delayed circuits, in: Proc.

13th Intern. Symposium on Multiple-Valued Logic, Kyoto, 1983, 1–9.

[26] I. Rosenberg, La structure des functions de plusieurs variables sur un ensemble ﬁni,

Comptes Rendus Acad. Sci. Paris 260 (1965), 3817–3819.

[27] J. Slupecki, Kriterium pelnosci wielowartosciowych systemow logiki zdan, Comptes ren-

dus des sc´eances de la Soci´et´e des Sciences et des Lettres de Varsovie 32 (1939), 102–109.

[28] E. V. Vetrennikova, A simple example of the universal b.d. function, Discrete Analysis

(1983), 5–11 (Russian).

[29] S. V. Yablonskii, Functional constructions in the k-valued logic, Proc. Steklov Institute

Math., 51 (1958), 5–142 (Russian).

[30] S. V. Yablonskii, O. P. Gavrilov, and V. B. Kudryavtsev, Boolean Functions and the

Post Classes, Nauka, Moscow, 1966 (Russian).

[31] Yu. I. Yanov and A. A. Muchnik, On the existence of k-valued closed classes that do not

have a basis, Soviet Acad. Sci. Dokl. 127 (1959), 144–146 (Russian).

[32] P. Yun-Tse, A method of discovering all precomplete classes in many-valued logic, Acta

Sci. Natur. Univ. Jilinensis 2 (1964).

240 V. B. Kudryavtsev

[33] E. Yu. Zakharova, Completeness criteria of a system of functions from P

, Probl. Cybern.

18 (1967), 5–10 (Russian).

[34] E. Yu. Zakharova, V. B. Kudryavtsev, and S. V. Yablonskii, On precomplete classes in

k-valued logics, Soviet Acad. Sci. Dokl. 186 (1969), 509–512 (Russian).

Algebra of behavior transformations

and its applications

Alexander LETICHEVSKY

Glushkov Institute of Cybernetics

National Academy of Sciences of Ukraine

Ukraine

Abstract

The model of interaction of agents and environments is considered. Both agents

and environments are characterized by their behaviors represented as the elements of

continuous behavior algebra, a kind of the ACP with approximation relation, but in

addition each environment is supplied by an insertion function, which takes the behavior

of an agent and the behavior of an environment as arguments and return a new behavior

of this environment. Each agent can be considered as a transformer of environment

behaviors and a new kind of equivalence of agents weaker than bisimulation is deﬁned

in terms of the algebra of behavior transformations. Arbitrary continuous functions can

be used as insertion functions and rewriting logic is used to deﬁne computable ones. The

theory has applications for studying distributed computations, multi agent systems and

semantics of speciﬁcation languages.

1 Introduction

The topic of these lectures belongs to an intensively developing area of computer science:

the mathematical theory of communication and interaction. The paradigm shift from com-

putation to interaction and the wide-spread occurrence of distributed computations attract

a great deal of interest among researchers in this area.

Concurrent processes or agents are the main objects of the theory of interaction. Agents

are objects, which can be recognized as separate from the rest of a world or an environ-

ment. They exist in time and space, change their internal state, and can interact with other

agents and environments, performing observable actions and changing their place among

other agents (mobility). Agents can be objects in real life or models of components of an in-

formation environment in a computerized world. The notion of agent formalizes such objects

as software components, programs, users, clients, servers, active components of distributed

knowledge bases and so on. A more speciﬁc and rich notion of agent is also used in so called

agent programming, an engineering discipline devoted to the design of intelligent interactive

systems.

Theories of communication, interaction, and concurrency have a long history, that starts

from the structural theory of automata (50-th years of the last century). Petri Nets is an-

other very popular general model of concurrency. However Petri Nets is very speciﬁc, and

structural automata theory requires too many details to represent interaction in a suﬃciently

241

V. B. Kudryavtsev and I. G. Rosenberg (eds.),

Structural Theory of Automata, Semigroups, and Universal Algebra, 241–272.

242 A. Letichevsky

abstract form. Theories of communication and interaction which appeared in 70-th captured

the fundamental properties of the notion of interaction and constitute the basis of modern

research in this ﬁeld. They include CCS (Calculus of Communicated Processes) [19, 20] and

the π-calculus [21] of R. Milner, CSP (Communicated Sequential Processes) of T. Hoar [13],

ACP (Algebra of Communicated Processes) [5] and many branches of these basic theories.

The current state-of-the-art is well represented in recently edited Handbook of Process Alge-

bra [6]. A new look at the area appeared recently in connection with the coalgebraic approach

to interaction [24, 4].

The main notion of the theory of interaction is the behavior of agents or processes in-

teracting with each other within some environment. At the same time traditional theories

of interaction do not formalize the notion of an environment where agents are interacting

or consider very special cases of it. The usual point of view is that an environment for a

given agent is the set of all other agents surrounding it. In the theory of interaction of agents

and environments developed in [15] and presented in the lectures, the notion of environment

is formalized as an agent supplied by an insertion function, which describes the change of

behavior of an environment after the agent is inserted. After inserting one agent an environ-

ment is ready to accept another one and, considered as an agent, it can itself be inserted into

another environment of higher level. Therefore multi-agent and multilevel environments can

be created using insertion functions.

Both agents and environments are characterized by their behaviors represented as the

elements of a continuous behavior algebra, a kind of ACP with approximation relation [14].

The insertion function takes the behavior of an agent and the behavior of environment as

arguments and returns a new behavior of this environment. Each agent therefore can be con-

sidered as a transformer of environment behaviors and a new equivalence of agents is deﬁned

in terms of the algebra of behavior transformations. This idea comes from Glushkov discrete

transformers (processors) [9, 10], an approach considering programs and microprograms as

the elements of the algebra of state space transformations. In the theory of agents and envi-

ronments the transformations of a behavior space is considered instead, so this transition is

similar to the transition from point spaces to functional spaces in mathematical analysis.

Arbitrary continuous functions can be used as insertion functions and rewriting logic is

applied to deﬁne computable ones. The theory has applications for the study of distributed

computations and multi agent systems. It is used for the development speciﬁcation languages

and tools for the design of concurrent and distributed software systems. Three lectures

correspond to the three main sections of the paper and contain the following.

The ﬁrst section gives an introduction to the algebraic theory of processes considered as

agent behaviors. Agents are represented by means of labeled transition systems with diver-

gence and termination, and considered up to bisimilarity or other (weaker) equivalences. The

theorem characterizing bisimilarity in terms of a complete behavior algebra (cpo with alge-

braic structure) is proved and the enrichment of a behavior algebra by sequential and parallel

compositions is considered. The second section introduces algebras of behavior transforma-

tions. These algebras are classiﬁed by the properties of insertion functions and in many cases

can be considered as behavior algebras as well. The enrichment of a transformation algebra

by parallel and sequential composition can be done only in very special cases. Two aspects

of studying transformation algebras can be distinguished.

Algebra of behavior transformations 243

Mathematical aspect The study of algebras of environments and behavior transforma-

tions as mathematical objects, classifying insertion functions and algebras of behavior trans-

formations generated by them, developing speciﬁc methods of proving properties of systems

represented as environments with inserted agents.

Application aspect The insertion programming, that is a programming based on agents

and environments. This is an answer to the paradigm shift from computation to interaction

and consists of developing a methodology of insertion programming (design environment and

agents inserted in it) as well as the development of tools supporting insertion programming.

The application of the insertion programming approach to the development of proof systems

is considered in the last section.

2 Behavior algebras

2.1 Transition systems

Transition systems are used to describe the dynamics of systems. There are several kinds

of transition systems which are obtained by the enrichment of an ordinary transition system

with additional structures.

An ordinary transition system is deﬁned as a couple

S, T ,T⊆ S

where S is the set of states and T is a transition relation denoted also as s → s



.Ifthereare

no additional structures, perhaps the only useful construction is the transitive closure of the

transition relation denoted as s

∗

−→ s



and expressing the reachability in the state space S.

A labeled transition system is deﬁned as a triple

S, A, T ,T⊆ S × A × S

where S is again a set of states, A is a set of actions (alternative terminology: labels or

events), and T is a set of labeled transitions. Belonging to a transition relation is denoted by

−→ s



. This is the main notion in the theory of interaction. We can consider the external

behavior of a system and its internal functioning using the notion of labeled transitions. As in

automata theory two states are considered to be equivalent if we cannot distinguish them by

observing only external behavior, that is actions produced by a system during its functioning.

This equivalence is captured by the notion of bisimilarity discussed below. Both the notion

of transition system and bisimilarity go back to R. Milner and, in its modern form, were

introduced by D. Park [22] who studied inﬁnite behavior of automata.

The mixed version

S, A, T ,T⊆ S × A × S ∪ S

combines unlabeled transitions s → s



with labeled ones s

−→ s



.Inthiscasewediscuss

unobservable or hidden and observable transitions. However as it will be demonstrated later,

the mixed version can be reduced to labeled systems. Technically sometime it is easier to

deﬁne a mixed system and then reduce it to labeled one.

244 A. Letichevsky

The attributed transition systems:

S, A, U, T, ϕ,ϕ: S → U.

This kind of transition system is used when not only transitions but also states should be

labeled. The function ϕ is called a state label function. Usually a set of state labels is

structured as U = D

,wherethesetR is called the set of attributes and the set D is a set

of attribute values. These sets can also be typed and in this case U =(D

)

ξ∈Ξ

(Ξ is the set

of type symbols).

Adjusted transition systems are obtained distinguishing three kinds of subsets,

∆

⊥

⊆ S

in a set S of system states. They are initial states, states of successful termination and

undeﬁned (divergent) states, respectively. The supposed meaning of these adjustments is the

following: from initial states a system can start in an initial state and terminate in a state

of successful termination, undeﬁned states are used to deﬁne an approximation relation on

the set of states; the behavior of a system can be reﬁned (extended) in undeﬁned states.

The states of successful termination must be distinguished from the dead lock states,that

is the states from which there are no transitions but which are neither states of successful

termination nor undeﬁned states. The property of a state having no transitions is denoted

as s →.

Other important classes of transition systems are stochastic, fuzzy, and real time transition

systems. All of them are obtained by introducing some additional numeric structure to

diﬀerent kinds of transition systems and will not be considered here. Attributed transition

systems as well as mixed systems can be reduced to labeled ones, so the main kind of system

will be labeled an adjusted transition system (usually with S

= S) and other kinds will be

used only in examples.

Let us consider some useful examples (without details which the reader is encouraged to

supply himself/herself).

Automata The set A of actions is identiﬁed with an input (output) alphabet or with the

set of pairs input/output.

Programs The set A of actions is an instruction set or only input/output instructions

according to what should be considered as observable actions. The set S is the set of states

of a program (including memory states). If we want some variables to be observable, a system

can be deﬁned with a state label function mapping the variable symbols to their values in a

given state.

Program schemata Symbolic (allowing multiple interpretations) instructions and states

are considered. The set of actions are the same as in the model of a program.

Algebra of behavior transformations 245

Parallel or distributed programs and program schemata The set A of actions is

a set of observable actions performed in parallel or sequentially (in this case parallelism is

modelled by interleaving) in diﬀerent components; communications are usually represented

by hidden transitions (as in CCS). The states are composed with the states of components

by parallel composition. This example will be considered below in more details.

Calculi States are formulas; actions are the names of inference rules.

Data and knowledge bases Actions are queries.

There are two kinds of non-determinism inherent in transition systems. The ﬁrst one

is the existence of two transitions s

−→ s



and s

−→ s



for some state s with s



= s



This non-determinism means that, after performing an action a, a system can choose the

next state non-deterministically. The second kind of non-determinism is the possibility of

diﬀerent adjustments of the same state, that is a state can be at the same time a state of

successful termination as well as undeﬁned or initial.

A labeled transition system (without hidden transitions) is called deterministic if for

arbitrary transitions from s

−→ s



∧s

−→ s



it follows that s



= s



and S

∆

∩ S

⊥

= ∅.

2.2 Trace equivalence

A history of system performance is deﬁned as a sequence of transitions starting from some

initial state s

and continuing at each step by application of transition relation, to a state

obtained at this step:

−→ s

−→···

A history can be ﬁnite or inﬁnite. It is called ﬁnal if it is inﬁnite or cannot be continued. A

trace corresponding to a given history is a sequence of actions performed along this history:

...a

...

For an attributed transition system the trace includes the state labels:

ϕ(s

)

−→ ϕ(s

)

−→···

Diﬀerent sets of traces can be used as invariants of system behavior. They are called trace

invariants. Examples of trace invariants of a system S are the following sets: L(S)—the set

of all traces of a system S; L

(s)—the set of all traces starting at the state s; L

∆

(S)—the set

of all traces ﬁnishing at a terminal state, L

∆

(S)—the set of all traces starting at an initial

state and ﬁnishing at a terminal state, etc. All these invariants can be easily computed for

ﬁnite state systems as regular languages.

We obtain the notion of trace equivalence considering L

∆

(S) as the main trace invariant:

systems S and S



are trace equivalent (S ∼



)ifL

∆

(S)=L

∆



). Unfortunately trace

equivalence is too weak to capture the notion of transition system behavior. Consider the

two systems presented in Fig. 1.

Both systems in the ﬁgure start their activity by performing an action a.Buttheﬁrstof

the two systems has a choice at the second step. It can perform action b or c.Atthesame