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

• Autorzy: Choffrut C. , Grigorieff S.

Identyfikatory

DOI

10.3233/FI-2015-1205

• Języki publikacji: EN

Abstrakty

EN

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 Δ₅ and Δ₇.

Słowa kluczowe

EN

monoids; language; alphabet; set theory; mathematical constants; functions

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 159--177
• Opis fizyczny: Bibliogr. 11 poz.

Twórcy

autor

Choffrut C.

• LIAFA CNRS and Université Paris Diderot Paris 7, Case 7014, France

autor

Grigorieff S.

• 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.