Hierarchies of hyper-AFLs

DOI10.1016/0022-0000(85)90006-6zbMath0565.68072OpenAlexW2166537922MaRDI QIDQ1058860

Joost Engelfriet

Publication date: 1985

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

Full work available at URL: https://research.utwente.nl/en/publications/hierarchies-of-hyperafls(d8f28368-f85e-4065-9472-1fa21065ec9e).html

zbMATH Keywords

indexed languagesmacro grammarsAFL

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

On the word problem for special monoids, MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS, On the word problem for weakly compressible monoids, On the word problem for free products of semigroups and monoids, Extended macro grammars and stack controlled machines, Algebraic aspects of families of fuzzy languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Syntactic operators on full semiAFLs
• Extended macro grammars and stack controlled machines
• Tree transducers, L systems, and two-way machines
• On incomparable abstract family of languages (AFL)
• Copying theorems
• A relationship between ETOL and EDTOL languages
• One way finite visit automata
• IO and OI. II
• Extended linear macro grammars, iteration grammars, and register programs
• Effective constructions in well-partially-ordered free monoids
• Hierarchy theorems for two-way finite state transducers
• Checking automata and one-way stack languages
• A characterization of two-way deterministic classes of languages
• Stack Machines and Classes of Nonnested Macro Languages
• Bounded nesting in macro grammars
• Space-bounded complexity classes and iterated deterministic substitution
• A note on Lindenmayer systems, Szilard languages, spectra, and equivalence
• Decomposition Theorems for Various Kinds of Languages Parallel in Nature
• Controlled iteration grammars and full hyper-AFL's
• Three hierarchies of transducers
• Indexed Grammars—An Extension of Context-Free Grammars
• Nested Stack Automata
• Full AFLs and nested iterated substitution
• Chains of full AFL's