Powiadomienia systemowe
- Sesja wygasła!
Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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.
Słowa kluczowe
Wydawca
Czasopismo
Rocznik
Tom
Strony
159--177
Opis fizyczny
Bibliogr. 11 poz.
Twórcy
autor
- LIAFA CNRS and Université Paris Diderot Paris 7, Case 7014, France
autor
- LIAFA CNRS and Université Paris Diderot Paris 7, Case 7014, France
Bibliografia
- [1] Christian Choffrut and Serge Grigorieff. Logical theory of the additive monoid of subsets of the set of integers. In Automata, Universality, Computation. Tribute to Maurice Margenstern (Andrew Adamatsky editor), p. 39–74. Emergence, Complexity and Computation, vol. 12, Springer, 2014.
- [2] Hans Hermes. Semiotik. Eine Theorie der Zeichengestalten als Grundlage fur Untersuchungen von formalisierten Sprachen. Forschungen zur Logik und zur Grundlegung der exakten Wissenschaften, new series, n.5, 22 pp., Leipzig, 1938.
- [3] John M. Howie. Fundamentals of Semigroup Theory. Clarendon Press, 1995.
- [4] Artur Jez and Alexander Okhotin. Equations over sets of natural numbers with addition only. In STACS, 577–588, 2009.
- [5] Michal Kunc. The power of commuting with finite sets of words, in 22nd Annu. Symp. Theoretical Aspects of Computer Science, STACS 2005, LNCS 3404, 569-580, Springer, 2005.
- [6] M. Lothaire. Combinatorics on Words. Addison-Wesley, 1983.
- [7] S.S.Marchenkov. Undecidability of the ∀∃-positive theory of a free semigroup (in Russian). SibirskiiMatematicheskii Zhurnal, 23:196–198, 1982.
- [8] Piergiorgio Odifreddi. Classical recursion theory. Vol. 1: The theory of functions and sets of natural integers. North Holland, 1989.
- [9] Willard V. Quine. Concatenation as a basis of arithmetic, Journal of Symbolic Logic, 11(4):105–114, 1946
- [10] Hartley Rogers. Theory of recursive functions and effective computability. McGraw Hill, 1967.
- [11] Alfred Tarski. Der Wahrheitebegriff in den formalisierten Sprachen, Studia philosophica (Lwow), 1:261–405, 1935. English translation: The concept of truth in formalized languages, in: Alfred Tarski, Logic, Semantics, Metamathematics, p. 152-278. Clarendon Press, 1956.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-8df19b9d-8ebd-41e8-9b34-df58e1268361