Complete Characterization of Zero-expressible Functions

Article type: Research Article

Authors: Dąbrowski, Robert | Plandowski, Wojciech

Affiliations: Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland. [email protected], [email protected]

Note: [] Address for correspondence: Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warszawa, Poland.

Abstract: 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.

Keywords: combinatorics on words, word equations, expressible relations

DOI: 10.3233/FI-2015-1215

Journal: Fundamenta Informaticae, vol. 138, no. 3, pp. 339-350, 2015