Context-free complexity of finite languages. (English) Zbl 0536.68065

Necessary conditions are given for an infinite language to have a sublinear complexity. To achieve the main result, characterizations for the number of productions of finite languages are derived. The main result: Let L be an infinite language over \(\Sigma\) with sublinear complexity. Then for all k there is an n(k) and there are words \(x_ i\), \(y_ i\), \(z_ i\), \(i=1,...,k,\) such that for all \(n>n(k)\) one of the following two cases holds: \[ (1)\quad(x_ i,z_ i)\neq(x_ j,z_ j),\quad y_ i\neq y_ j\quad for\quad i\neq j\quad and\quad \cup^{k}_{i=1}x_ i\{y_ 1,...,y_ k\}z_ i\subseteq L_ n, \]
\[ (2)\quad x_ i\neq y_ i\quad for\quad i=1,...,k\quad and\quad \{x_ 1,y_ 1\}...\{x_ k,y_ k\}\subseteq L_ n. \]


68Q45 Formal languages and automata
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Bucher, W., A note on a problem in the theory of grammatical complexity, Theoret. comput. sci., 14, 337-344, (1981) · Zbl 0469.68082
[2] Bucher, W.; Culik, K.; Maurer, H.; Wotschke, D., Concise description of finite languages, Theoret. comput. sci., 14, 227-246, (1981) · Zbl 0469.68081
[3] Harrison, M.A., Introduction to formal language theory, (1978), Addison-Wesley Reading, MA · Zbl 0411.68058
[4] Wegner, L., Analysis of two-level grammars, Hochschulverlag, informatik I, (1978), Stuttgart
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.