A Note on the Logical Definability of Rational Trace Languages

• Autorzy: Choffrut C.
• Języki publikacji: EN

Abstrakty

EN

The regular languages in the free monoid generated by a finite alphabet A are exactly the languages that are the models of some sentence of the second-order monadic logic of one successor and a unary predicate for each letter. For trace monoids the natural extension obtained by adapting the successor to the partial order underlying the traces is insufficient to capture the family of their rational subsets. We show that these subsets can be expressed by formulas of the form ∃Γφ where φ is a first-order formula over the structure of traces and Γ is an n-ary predicate semantically restricted, where n is the cardinality of the alphabet.

Słowa kluczowe

EN

trace monoid; first-order and second-order logic; rational subsets; finite automata

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 116, nr 1-4
• Strony: 45--50
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Choffrut C.

• Laboratoire LIAFA, Universit´e de Paris 7, 2, pl. Jussieu, 75251 Paris Cedex 05, France,

Bibliografia

• [1] J.R. Büchi. Weak second-order arithmetic and finite automata. In Z. Math. Logik Grundl. Math., volume 6, pages 66-92, 1960.
• [2] C. Choffrut and L. Guerra. Logical Definability of Some Rational Trace Languages. Math. Systems Theory, 28:397-420, 1995.
• [3] V. Diekert. Combinatorics on Traces, volume 454 of Lecture Notes in Computer Science. Springer, 1990.
• [4] S. Eilenberg, C.C. Elgot, and J.C. Shepherdson. Sets recognized by n-tape automata. J. Algebra, 3:447-464, 1969.
• [5] C.C. Elgot. Decision problems of finite automata design and related arithmetics. Trans. Americ. Math. Soc., 98:21-52, 1961.
• [6] H. Läuchli and Christian Savioz. Monadic second order definable relations on the binary tree. J. Symb. Log., 52(1):219-226, 1987.
• [7] C. Lautemann, T. Schwentick, and D. Thérien. Logics for Context-Free languages. In CSL, LNCS, 933: 205-216, 1995.
• [8] D. Perrin. Finite automata, Handbook of Theoretical Computer Science, volume B, Formal Models and Semantics, pages 1-57. Elsevier, 1990.
• [9] W. Thomas. Logical definability of trace languages. Proceedings of the ASMICS-Workshop TUM-I9002, TU München, 1990.