Refining the hierarchy of blind multicounter languages and twist-closed trios.

DOI10.1016/S0890-5401(03)00087-7zbMath1082.68053MaRDI QIDQ1427852

Matthias Jantzen, Alexy Kurganskyy

Publication date: 14 March 2004

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

shufflelinear algebraintersection-closed semi-AFLblind multicounter languageshierarchy of semi-AFLsmultipushdown acceptorsreversal-bounded multicounter automatatwist-closed semi-AFLs

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (4)

On Boolean closed full trios and rational Kripke frames ⋮ Unboundedness problems for machines with reversal-bounded counters ⋮ Permuting operations on strings and their relation to prime numbers ⋮ Permuting operations on strings and the distribution of their prime numbers

Cites Work

• Representations of language families by homomorphic equality operations and generalized equality sets
• Cônes rationnels commutatifs
• Reversal-bounded multipushdown machines
• Remarks on the complexity of nondeterministic counter languages
• Remarks on blind and partially blind one-way multicounter machines
• Cancellation in context-free languages: enrichment by reduction
• Principal AFL
• An Algorithm for the General Petri Net Reachability Problem
• Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
• Reversal-Bounded Acceptors and Intersections of Linear Languages
• Counter machines and counter languages
• Quasi-realtime languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Refining the hierarchy of blind multicounter languages and twist-closed trios.