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, On Boolean closed full trios and rational Kripke frames, Permuting operations on strings and the distribution of their prime numbers

Cites Work

• 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
• 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