Glaister, Ian; Shallit, Jeffrey Polynomial automaticity, context-free languages, and fixed points of morphisms. (Extended abstract). (English) Zbl 0889.68093 Penczek, Wojciech (ed.) et al., Mathematical foundations of computer science 1996. 21st international symposium, MFCS ’96, Cracow, Poland, September 2-6, 1996. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1113, 382-393 (1996). Summary: If \(L\) is a formal language, we define \(A_L(n)\) to be the number of states in the smallest deterministic finite automaton that accepts a language that agrees with \(L\) on all inputs of length \(\leq n\). This measure is called automaticity. In this paper, we first study the closure properties of the class DPA of languages of deterministic polynomial automaticity, i.e., those languages \(L\) for which there exists \(k\) such that \(A_L(n)= O(n^k)\). Next, we discuss similar results for a nondeterministic analogue of automaticity, introducing the classes NPA (languages of nondeterministic polynomial automaticity) and NPLA (languages of nondeterministic poly-log automaticity). We then show how to construct a context-free language with automaticity arbitrarily close to the maximum possible. Finally, we conclude with some remarks about the automaticity of sequences, focusing on fixed points of homomorphisms.For the entire collection see [Zbl 0852.00041]. Cited in 2 Documents MSC: 68Q45 Formal languages and automata 68R15 Combinatorics on words 11B85 Automata sequences Keywords:automaticity; context-free language PDFBibTeX XMLCite \textit{I. Glaister} and \textit{J. Shallit}, Lect. Notes Comput. Sci. 1113, 382--393 (1996; Zbl 0889.68093)