Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 4

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
w słowach kluczowych:  monoids
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
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.
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.
Content available remote Submonoids of generalized hypersubstitutions
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.
Content available remote The generalized residue classes and integral monoids with minimal sets
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.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.