Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Powiadomienia systemowe

Sesja wygasła!

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: monoids

Sortuj według:

Ogranicz wyniki do:

Logical Theory of the Monoid of Languages over a Non Tally Alphabet

Choffrut C., Grigorieff S.

Fundamenta Informaticae

2015

Vol. 138, nr 1/2

159--177

We consider the first-order theory of the monoid P(A*) of languages over a finite or infinite alphabet A (with at least two letters) endowed solely with concatenation lifted to sets: no set theoretical predicate or function, no constant. Coding a word u by the submonoid u* it generates, we prove that the operation (u*, v*) → (uv)* and the predicate {(u*,X) | ε ∈ X, u ∈ X} are definable in P(A*); •,=i. This allows to interpret the second-order theory of A*; •,=i in the first-order theory of P(A*); •,=i and prove the undecidability of the Π8 fragment of this last theory. These results involve technical difficulties witnessed by the logical complexity of the obtained definitions: the above mentioned predicates are respectively Δ5 and Δ7.

Deciding Whether or Not a Synchronous Relation is Regular Prefix

Choffrut C.

Fundamenta Informaticae

2014

Vol. 132, nr 4

439--459

Eilenberg and al. introduced and studied in the late sixties the family of n-ary relations over the free monoid recognized by finite n-tape automata where the where the n reading heads tapes move simultaneously from left to right. We call these relations synchronous. In the eighties Angluin and Hoover and then L¨auchli and Savioz introduced a proper subfamily which the first authors called regular prefix. Our main result shows that given a synchronous relation it is decidable whether or not it is regular prefix. Incidentallywe also show that the family of regular prefix relations is uniformizable in the sense that all such relations contain a partial function with the same domain whose graph is a regular prefix relation.

Submonoids of generalized hypersubstitutions

Leeratanavalee S.

Demonstratio Mathematica

2007

Vol. 40, nr 1

13-22

In this paper we define the operation G on the set of all generalized hypersubstitutions and investigate some algebraic-structural properties of the set of all generalized hypersubstitutions and of some submonoids M of the set of all generalized hypersubstitutions, respectively.

The generalized residue classes and integral monoids with minimal sets

Rycerz A.

Opuscula Mathematica

2000

Vol. 20

65-69

In this note we consider the integral monoids mon(A) = {Ax : x ∈ Zn+}, where A ∈ Zmxn, with the swelling points. Such monoids appear in the natural way in the generalized Frobenius problem in Zm. An integral element g ∈ mon(A) is called the swelling point if (g + cone(A)) ∩ Zm ⊆ mon(A), where cone(A) = {Ax : x ∈ Rn+}. The aim of this note is to characterize the structure of the set of swelling points in terms of the generalized residue classes.

W pracy rozważane są całkowite monoidy mon(A) = {Ax : x ∈ Zn+}, gdzie A ∈ Zmxn, z punktami źródłowymi, które w naturalny spo sób pojawiają się przy próbach uogólniania jednowymiarowego problemu Frobeniusa na przypadek wielowymiarowy. Punkt g ∈ mon(A) jest punktem źródłowym, jeśli (g + cone(A)) ∩ Zm ⊆ mon(A), gdzie cone(A) = {Ax : x ∈ Rn+}. Głównym rezultatem pracy jest charakteryzacja struktury zbioru punktów źródłowych za pomocą uogólnionych klas reszt.