Wyniki wyszukiwania - BazTech

1

Reversible Limited Automata

Kutrib M., Wendlandt M.

Fundamenta Informaticae

|

2017

|

Vol. 155, nr 1/2

31--58

EN

A k-limited automaton is a linear bounded automaton that may rewrite each tape square only in the first k visits, where k≥ 0 is a fixed constant. It is known that these automata accept context-free languages only. We investigate deterministic k-limited automata towards their ability to perform reversible computations, that is, computations in which every configuration has at most one predecessor. A first result is that, for all k≥ 0, sweeping k-limited automata accept regular languages only. In contrast to reversible finite automata, all regular languages are accepted by sweeping 0-limited automata. Then we study the computational power gained in the number k of possible rewrite operations. It is shown that the reversible 2-limited automata accept regular languages only and, thus, are strictly weaker than general 2-limited automata. Furthermore, a proper inclusion between reversible 3-limited and 4-limited automata languages is obtained. The next levels of the hierarchy are separated between every k and k + 3 rewrite operations. We investigate closure properties of the family of languages accepted by reversible k-limited automata. It turns out that these families are not closed under intersection, but are closed under complementation. They are closed under intersection with regular languages, which leads to the non-closure under concatenation, iteration, and homomorphisms. Finally, it turns out that all k-limited automata accept Church-Rosser languages only, that is, the intersection between context-free and Church-Rosser languages contains an infinite hierarchy of language families beyond the deterministic context-free languages.

2

Nominal Groups and Their Homomorphism Theorems

Alexandru A., Ciobanu G.

Fundamenta Informaticae

|

2014

|

Vol. 131, nr 3-4

279--298

EN

We introduce and study the nominal groups, providing some algebraic properties of this new structure. We focus on the properties of nominal homomorphisms, and study the correspondence between some results obtained in the Fraenkel-Mostowski framework (where only finitely supported objects are allowed) and those obtained in the classical Zermelo-Fraenkel framework.

3

On some subsemigroups of the groups L1/s and L1/nieskończoność

Jabłoński W.

Demonstratio Mathematica

|

2006

|

Vol. 39, nr 2

305-316

EN

The problem of determination of some class of geometric objects has been reduced about forty years ago to consideration of some subsemigroups of the differential group L1/s (cf. [1] and [6]). Over the last years many papers has been devoted the problem of determining of subsemigroups and subgroups of the group L/s (see among others (2], (3] and (5]-[15]). In this paper we are going to generalize the results from [5], [9] and (13] concerning determination of some form subsemigroups of the group L1/s.

4

Abelian groups with the direct summand sum property

Vălcan D.

Demonstratio Mathematica

|

2002

|

Vol. 35, nr 3

477-491

EN

If R is an associative ring, with unity, the R- module (the abelian group) M is said to have the direct summand sum property (in short D.S.S.P.) if the sum (that is the submodule (the subgroup) of M generated by the union) of any two direct summands ofM is again a direct summand in M. The present work gives descriptions of some classes of abelian groups with this property.

5

Homomorphisms of the group L1/2 into L1/2 and L1/3

Chudziak J., Drygaś P., Jabłoński W., Midura S.

Demonstratio Mathematica

|

1998

|

Vol. 31, nr 1

143-152

6

A categorial characterization of the mixed extension of a noncooperative game

Wiweger A.

Demonstratio Mathematica

|

1998

|

Vol. 31, nr 3

689-700

EN

Some variants of the notion of a homomorphism between noncooperative games are discussed and the respective categories of noncooperative games are introduced. It is shown that the mixed extension of a noncooperative game can be viewed as a value of the functor which is a left adjoint to the forgetful functor from some category of convex games to suitable category of noncooperative games.