Direction-independent grammars with contexts (Q1094143): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0020-0255(86)90009-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1978203591 / rank | |||
Normal rank |
Revision as of 01:10, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Direction-independent grammars with contexts |
scientific article |
Statements
Direction-independent grammars with contexts (English)
0 references
1986
0 references
A direction-independent two-dimensional (2D) array grammar introduced by the authors [Inf. Process. Lett. 22, 295-301 (1986; Zbl 0595.68068)] applies its production rule to a subarray equivalent to the left-hand side of the rule regardless of its direction. In this paper, we first define direction-independent monotonic array grammars \((MAG_ i)\). Next, as an intermediate generating system between context-free and monotonic, we define \({}^*\)-context array grammars \((^*AG)\) and their direction- independent version \((^*AG_ i)\). Then, we investigate the generative power of direction-independent grammars with contexts. It is shown that the direction-independent restriction does not affect the generative powers of MAG. It does, however, affect the generative power of a restricted version of \({}^*AG\), i.e. connected \({}^*\)-array grammars.
0 references
array grammar
0 references
generative power
0 references
direction-independent grammars
0 references