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

shuffle; linear algebra; intersection-closed semi-AFL; blind multicounter languages; hierarchy of semi-AFLs; multipushdown acceptors; reversal-bounded multicounter automata; twist-closed semi-AFLs

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Permuting operations on strings and their relation to 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