Direction-independent grammars with contexts (Q1094143): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(3 intermediate revisions by 3 users not shown) | |||
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/0020-0255(86)90009-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1978203591 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Direction-independent application of productions on two-dimensional arrays / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3926078 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5656399 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Array grammar normal forms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hierarchical Structures and Complexities of Parallel Isometric Languages / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 13:09, 18 June 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