Two-variable word equations
Two-variable word equations
We consider languages expressed by word equations in two variables and give a complete characterization for their complexity functions, that is, the functions that give the number of words of the same length. Specifically, we prove that there are only five types of complexities: constant, linear, exponential, and two in between constant and linear. For the latter two, we give precise characterizations in terms of the number of solutions of Diophantine equations of certain types. In particular,...
A characterization of poly-slender context-free languages
A characterization of poly-slender context-free languages
For a non-negative integer , we say that a language is if the number of words of length in is of order . We give a precise characterization of the -poly-slender context-free languages. The well-known characterization of the -poly-slender regular languages is an immediate consequence of ours.
Page 1