×

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].

MSC:

68Q45 Formal languages and automata
68R15 Combinatorics on words
11B85 Automata sequences
PDFBibTeX XMLCite