Refining the hierarchy of blind multicounter languages and twist-closed trios.
type: Item
instance of: scholarly article
title: Refining the hierarchy of blind multicounter languages and twist-closed trios.
zbMATH Open document ID: 1082.68053
DOI: 10.1016/S0890-5401(03)00087-7
author: Matthias Jantzen
author: Alexy Kurganskyy
published in: Information and Computation
publication date: 2004-03-14T00:00:00Z
review text: We introduce the new families \((k,r)\)-RBC of languages accepted in quasi-realtime by one-way counter automata having \(k\) blind counters, of which at least \(r\) are reversal-bounded. It is proved that these families form a strict and linear hierarchy of semi-AFLs within the the family \(\text{BLIND}={\mathcal M}_\cap(C_1)\) of blind multicounter languages with generator \(C_1= \{w\in \{a_1,b_1\}^*\mid |w|_{a_1}= |w|_{b_1}\}\). This thereby combines the families BLIND and RBC of \textit{S. Greibach} [Theor. Comput. Sci. 7, 311--324 (1978; Zbl 0389.68030)] to one strict hierarchy and generalizes and sharpens Greibach's results. The strict inclusions between the \(k\)-counter families \((k,r)\)-RBC are proved using linear algebra techniques. We also study the language theoretic monadic operation `twist' [see \textit{M. Jantzen} and \textit{H. Petersen}, in: K. Voss et al. (eds.), Concurrency and nets. Advances in Petri nets, 245--252 (1987; Zbl 0629.68075); Theor. Comput. Sci. 127, 149--170 (1994; Zbl 0805.68076)], in connection with the semi-AFLs of languages accepted by multicounter and multipushdown acceptors, all restricted to reversal-bounded behavior. It is verified that the family \((k,r)\)-RBC is twist-closed if and only if \(r=0\), in which case \((k,0)\text{-RBC}={\mathcal M}(C_k)\), \(C_k\) being the \(k\)-fold shuffle of disjoint copies of \(C_1\). We characterize the family \({\mathcal M}_\cap(\text{PAL})\) of languages accepted in quasi-realtime by nondeterministic one-way reversal-bounded multipushdown acceptors as the least twist-closed trio \({\mathcal M}_{\text{twist}}(\text{PAL})\) generated by the set of palindromes \(\text{PAL}= \{w\in \{a,b\}^*\mid w=w^{\text{rev}}\}\).
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 2056064
zbMATH Keywords: reversal-bounded multicounter automata
zbMATH Keywords: shuffle
zbMATH Keywords: intersection-closed semi-AFL
zbMATH Keywords: twist-closed semi-AFLs
zbMATH Keywords: hierarchy of semi-AFLs
zbMATH Keywords: blind multicounter languages
zbMATH Keywords: linear algebra
zbMATH Keywords: multipushdown acceptors
MaRDI profile type: Publication
cites work: Reversal-bounded multipushdown machines
cites work: Q3859267
cites work: Quasi-realtime languages
cites work: Q4170259
cites work: Reversal-Bounded Acceptors and Intersections of Linear Languages
cites work: Representations of language families by homomorphic equality operations and generalized equality sets
cites work: Q3129299
cites work: Fixed Point Languages, Equality Languages, and Representation of Recursively Enumerable Languages
cites work: Counter machines and counter languages
cites work: Q4089754
cites work: Principal AFL
cites work: Remarks on the complexity of nondeterministic counter languages
cites work: Remarks on blind and partially blind one-way multicounter machines
cites work: Q4190159
cites work: Q4371016
cites work: Q4381393
cites work: Q3766878
cites work: Cancellation in context-free languages: enrichment by reduction
cites work: Q2762519
cites work: Q5652762
cites work: Q4125808
cites work: Q4168082
cites work: Cônes rationnels commutatifs
cites work: An Algorithm for the General Petri Net Reachability Problem
cites work: Q3948608
Recommended article: Q2762519
Recommended article: On families of full trios containing counter machine languages
Recommended article: On Families of Full Trios Containing Counter Machine Languages
Recommended article: Q4783319
Recommended article: Q3606478
Recommended article: Q3505884
Recommended article: Geometrical closure of binary \(V_{3/2}\) languages
Recommended article: Q4654642
Recommended article: Visibly Counter Languages and the Structure of $$\mathrm {NC}^{1}$$
Recommended article: Classifying rotationally-closed languages having greedy universal cycles
description: scientific article; zbMATH DE number 2056064