๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

A geometric hierarchy of languages

โœ Scribed by Nabil A. Khabbaz

Publisher
Elsevier Science
Year
1974
Tongue
English
Weight
543 KB
Volume
8
Category
Article
ISSN
0022-0000

No coin nor oath required. For personal study only.

โœฆ Synopsis

This paper proves the existence of a hierarchy of languages which is properly contained in the context sensitive languages and which starts with the context-free family. The hierarchy is defined inductively by controlling labeled linear grammars with languages in one family to yield languages in the next larger family. The families of the hierarchy have properties analogous to those of the context-free family, in particular decidability properties are the same and on one symbol alphabets, member languages are regular. The geometric pumping lemma within the context-free languages generalizes to yield analogous results for the other families. In fact, this latter property is responsible for the existence of the hierarchy.

๐Ÿ“œ SIMILAR VOLUMES

A hierarchy of deterministic languages
A hierarchy of deterministic languages
โœ Michael A. Harrison; Amiram Yehudai ๐Ÿ“‚ Article ๐Ÿ“… 1979 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 957 KB
A hierarchy of eNCE families of graph la
A hierarchy of eNCE families of graph languages
โœ Changwook Kim ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 846 KB

Even though eNCE and its subclasses have been studied intensively, their inclusion relations are not completely known. This paper proves some unknown relations among eNCE families of graph languages which yield, together with other known relations, a solid hierarchy of graph languages that completel

A chomsky hierarchy of isotonic array gr
A chomsky hierarchy of isotonic array grammars and languages
โœ Curtis R. Cook; Patrick Shen-Pei Wang ๐Ÿ“‚ Article ๐Ÿ“… 1978 ๐Ÿ› Elsevier Science โš– 484 KB

An array is a two-dimensional generalization of a string. Both sides of each rewriting rule of an isotonic array grammar have the same shape. In this paper we complete the Chomsky hierarchy of isotonic array grammars by introducing isotonic context-free array grammars. We obtain Chomsky and Greibach