Complete Characterization of Zero-expressible Functions

• Autorzy: Dąbrowski R. , Plandowski W.

Identyfikatory

DOI

10.3233/FI-2015-1215

• Języki publikacji: EN

Abstrakty

EN

We describe an intersection of the family of expressible relations and another natural family of relations. This is the first result of this kind existing in the literature. To obtain it we extend a tool for proving nonexpressibility of languages to a tool for proving nonexpressibility of relations.

Słowa kluczowe

EN

combinatorics on words; word equation; expressible relations

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 3
• Strony: 339--350
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Dąbrowski R.

• Institute of Informatics University of Warsaw Banacha 2, 02-097 Warszawa, Poland

autor

Plandowski W.

• Institute of Informatics University of Warsaw Banacha 2, 02-097 Warszawa, Poland

Bibliografia

• [1] J. R. Buchi and S. Senger. Coding in the existential theory of concatenation. Archiv fur Mathematiche Logik und Grundlagenforschung, 26:101–106, 1986/1987.
• [2] J. R. Buchi and S. Senger. Definability in the existential theory of concatenation and undecidable extensions of this theory. Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, 22:337–342, 1987.
• [3] A. Gleibman. Knowledge representation via verbal description generalization: alternative programming in sampletalk language. In Proceedings of Workshop on Inference for Textual Question Answering, Pittsburgh, Pennsylvania. AAAI-05 - the Twentieth National Conference on Artificial Inteligence., pages 59–68, 2005. See also www.sampletalk.com.
• [4] J. Jaffar. Minimal and complete word unification. Journal of the ACM, 37(1):47–85, 1990.
• [5] J. Karhumaeki, F. Mignosi, and W. Plandowski. The expressibility of languages and relations by word equations. Journal of the ACM, 47(5):483–505, 2000.
• [6] J. Karhumaeki, F. Mignosi, and W. Plandowski. On the expressibility of languages by word equations with a bounded number of variables. Bulletin of the Belgian Mathematical Society, 8(2), 2001.
• [7] W. Plandowski. An efficient algorithm for solving word equations. In Proceedings of the 38th Annual Symposium on Theory of Computing STOC’06, pages 467–476. ACM Press, 2006.
• [8] A. Rajasekar. Applications in constraint logic programming with strings. In Proceedings of the Principles and Practice of Constraint Programming, Second International Workshop, PPCP’94, Lecture Notes in Computer Science 874, pages 109–122. Springer, 1994.
• [9] A. A. Razborov. On systems of equations in a free group. Izv. Akad. Nauk SSR Ser. Mat., 48:779–832, 1984. In Russian; English transl. in Math. USSR Izv., 25, 115-162, 1985.
• [10] M. Schaefer, E. Sedgwick, and D. Stefankovic. Recognizing string graphs is in np. Journal of Computer and System Sciences, 67(2):365–380, 2003.