Wyniki wyszukiwania - BazTech

Ograniczanie wyników

1 Fundamenta Informaticae

1 2015

Znaleziono wyników: 1

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: mathematical constants

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.