Context-free complexity of finite languages

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

Recommendations

Cites work

Cited in

(23)

This page was built for publication: Context-free complexity of finite languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q792097)