Substitution and bounded languages

DOI10.1016/S0022-0000(72)80038-2zbMath0232.68030MaRDI QIDQ2550965

Jonathan Goldstine

Publication date: 1972

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Rational languages and the Burnside problem ⋮ Sur la structure des langages algébriques ⋮ Unnamed Item ⋮ Iterated GSMs and CO-CFL ⋮ On the usefulness of bifaithful rational cones ⋮ Unnamed Item ⋮ Unnamed Item ⋮ A model for ergodic automorphisms on groups ⋮ On the Degree of Extension of Some Models Defining Non-Regular Languages ⋮ On the degrees of non-regularity and non-context-freeness ⋮ Some independent families of one-letter languages ⋮ Familles de langages translatables et fermées par crochet ⋮ Bounded AFLs ⋮ Comparing language operations ⋮ Proving containment of bounded AFL ⋮ String and graph grammar characterizations of bounded regular languages ⋮ A TREE-HEIGHT HIERARCHY OF CONTEXT-FREE LANGUAGES

Uses Software

• ALGOL 60

Cites Work

• Syntactic operators on full semiAFLs
• Bounded AFLs
• Checking automata and one-way stack languages
• What makes some language theory problems undecidable
• Principal AFL
• Bounded Algol-Like Languages
• Bounded Regular Sets
• Finite-Turn Pushdown Automata
• An Infinite Hierarchy of Context-Free Languages
• Studies in abstract families of languages
• Chains of full AFL's