Context-free complexity of finite languages (Q792097): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 3 users not shown) | |||
Property / author | |||
Property / author: Hermann Maurer / rank | |||
Property / author | |||
Property / author: Karel II Culik / rank | |||
Property / author | |||
Property / author: Hermann Maurer / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Karel II Culik / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0304-3975(83)90024-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2023738367 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on a problem in the theory of grammatical complexity / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Concise description of finite languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198075 / rank | |||
Normal rank |
Latest revision as of 12:31, 14 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Context-free complexity of finite languages |
scientific article |
Statements
Context-free complexity of finite languages (English)
0 references
1984
0 references
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. \]
0 references
infinite language
0 references
sublinear complexity
0 references
number of productions
0 references
finite languages
0 references