Search

We give an O(n + t) time algorithm to determine whether an NFA with n states and t transitions accepts a language of polynomial or exponential growth. Given an NFA accepting a language of polynomial growth, we can also determine the order of polynomial growth in O(n+t) time. We also give polynomial time algorithms to solve these problems for context-free grammars. [ABSTRACT FROM AUTHOR]

Abstract: We continue our study of stabilizers of infinite words over finite alphabets, begun in [D. Krieger, On stabilizers of infinite words, Theoret. Comput. Sci. 400 (2008), 169–181]. Let be an aperiodic infinite word over a finite alphabet, and let be its stabilizer. We show that can be partitioned into the monoid of morphisms that stabilize by finite fixed points and the ideal of morphisms that stabilize by iteration. We also settle a conjecture given in the paper mentioned above, by showing that in some cases is infinitely generated. If the aforementioned ideal is nonempty, then it contains either polynomially growing morphisms or exponentially growing morphisms, but not both. Moreover, in the polynomial case, the degree of the polynomial is fixed. We also show how to compute the polynomial degree from the dependency graph of a polynomially growing morphism. [Copyright &y& Elsevier]

Abstract: Let the words of a language be arranged in increasing radix order: . We consider transformations that extract terms from in an arithmetic progression. For example, two such transformations are and . Lecomte and Rigo observed that if is regular, then so are , , and analogous transformations of . We find good upper and lower bounds on the state complexity of this transformation. We also give an example of a context-free language such that is not context-free. [Copyright &y& Elsevier]

Abstract: The stabilizer of an infinite word over a finite alphabet is the monoid of morphisms over that fix . In this paper we study various problems related to stabilizers and their generators. We show that over a binary alphabet, there exist stabilizers with at least generators for all . Over a ternary alphabet, the monoid of morphisms generating a given infinite word by iteration can be infinitely generated, even when the word is generated by iterating an invertible primitive morphism. Stabilizers of strict epistandard words are cyclic when non-trivial, while stabilizers of ultimately strict epistandard words are always non-trivial. For this latter family of words, we give a characterization of stabilizer elements. [Copyright &y& Elsevier]

We prove that for every real number there exists an infinite word over a finite alphabet such that is the critical exponent of . [Copyright &y& Elsevier]

Abstract: Let be an alphabet of size , let be a non-erasing morphism, let be an infinite fixed point of , and let be the critical exponent of . We prove that if is finite, then for a uniform it is rational, and for a non-uniform it lies in the field extension , where are the eigenvalues of the incidence matrix of . In particular, is algebraic of degree at most . Under certain conditions, our proof implies an algorithm for computing . [Copyright &y& Elsevier]