AFL with the semilinear property

DOI10.1016/S0022-0000(71)80024-7zbMath0235.68029OpenAlexW2007835340MaRDI QIDQ2552027

Seymour Ginsburg, Edwin H. Spanier

Publication date: 1971

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

Full work available at URL: https://doi.org/10.1016/s0022-0000(71)80024-7

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (31)

Single-tape reset machines ⋮ Unnamed Item ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ On the spectrum of a nonlinear operator ⋮ Loops in automata and HDTOL relations ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Shuffle on trajectories: Syntactic constraints ⋮ Tree transducers, L systems, and two-way machines ⋮ Controlled pushdown automata ⋮ Hairpin completions and reductions: semilinearity properties ⋮ Deque automata, languages, and planar graph representations ⋮ Independance forte de certaines opérations ⋮ The equivalence of deterministic gsm replications onQ-rational languages is decidable ⋮ 2DST mappings of languages and related problems ⋮ Continuous operations on languages ⋮ Uniformly erasable AFL ⋮ Control sets on context-free grammar forms ⋮ Ogden's lemma, multiple context-free grammars, and the control language hierarchy ⋮ A simplified proof of Parikh's theorem ⋮ One way finite visit automata ⋮ Classes of formal grammars ⋮ On two-way sequential transductions of full semi-AFL's ⋮ The complexity of the membership problem for some extensions of context-free languagest† ⋮ Intersections de langages algébriques bornes ⋮ Syntactic operators on full semiAFLs ⋮ Substitution in families of languages ⋮ Semi-discrete context-free languages^† ⋮ Semilinearity of Families of Languages ⋮ MIX is a 2-MCFL and the word problem in \(\mathbb{Z}^2\) is captured by the IO and the OI hierarchies ⋮ Characterization and complexity results on jumping finite automata

Uses Software

• ALGOL 60

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Semigroups, Presburger formulas, and languages
• Principal AFL
• Substitution in families of languages
• A hierarchy between context-free and context-sensitive languages
• Decision Problems of Finite Automata Design and Related Arithmetics
• Bounded Algol-Like Languages
• Bounded Regular Sets
• On Context-Free Languages
• Control sets on grammars
• Counter machines and counter languages
• On equal matrix languages
• Simple matrix languages

This page was built for publication: AFL with the semilinear property