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.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
4
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
PL
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.
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ć.