An Infinite Hierarchy of Context-Free Languages

DOI10.1145/321495.321503zbMath0182.02002OpenAlexW2092008211MaRDI QIDQ5573387

Sheila A. Greibach

Publication date: 1969

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/321495.321503

zbMATH Keywords

recursion theory, constructive mathematics

Related Items (52)

On pebble automata ⋮ Regulated nondeterminism in pushdown automata ⋮ An analysis of the nonemptiness problem for classes of reversal-bounded multicounter machines ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Quasi-realtime languages ⋮ Hierarchies of one-way multihead automata languages ⋮ Finite turns and the regular closure of linear context-free languages ⋮ On regular realizability problems for context-free languages ⋮ Indexed counter languages ⋮ Chains of full AFL's ⋮ On some decision questions concerning pushdown machines ⋮ Familles de langages fermées par crochet ouvert ⋮ Unnamed Item ⋮ Characterizations of transductions defined by abstract families of transducers ⋮ The equivalence of stack-counter acceptors and quasi-realtime stack- counter acceptors ⋮ HYBRID EXTENDED FINITE AUTOMATA ⋮ Unnamed Item ⋮ Formal grammars for turn-bounded deterministic context-free languages ⋮ Queue Automata: Foundations and Developments ⋮ The complexity of decision problems for finite-turn multicounter machines ⋮ Petri nets and regular languages ⋮ Unnamed Item ⋮ Properties of right one-way jumping finite automata ⋮ On languages with a certain prefix property ⋮ Two iteration theorems for some families of languages ⋮ Undecidability in matrices over Laurent polynomials. ⋮ One counter languages and the IRS condition ⋮ Reversal-bounded multipushdown machines ⋮ On the universe, disjointness, and containment problems for simple machines ⋮ Abstract families of relations ⋮ Uniformly erasable AFL ⋮ Comparing language operations ⋮ Some uniformly erasable families of languages ⋮ Restricted one-counter machines with undecidable universe problems ⋮ Control sets on context-free grammar forms ⋮ Associative language descriptions ⋮ One way finite visit automata ⋮ On equivalence and subclass containment problems for deterministic context-free languages ⋮ Compelled operations and operations of degreeP ⋮ Linear weighted tree automata with storage and inverse linear tree homomorphisms ⋮ Principal AFL ⋮ Syntactic operators on full semiAFLs ⋮ Substitution and bounded languages ⋮ On AFL generators for finitely encoded AFA ⋮ Strict deterministic grammars ⋮ Langages à un compteur ⋮ Regular Realizability Problems and Context-Free Languages ⋮ Theory of formal grammars ⋮ Deterministic input-driven queue automata: finite turns, decidability, and closure properties ⋮ On reducing the number of stack symbols in a PDA ⋮ Every iterated morphism yields a co-CFL

This page was built for publication: An Infinite Hierarchy of Context-Free Languages