Are Reversal-bounded Multicounter Machines closed under reversal?

Question

This is a problem I have found very difficult to solve, given how the two different uses of "reversal" confuses search engines.

Reversal-bounded multicounter machines are described at length in his paper "Reversal Bounded Multicounter Machines and their Decision Problems". Essentially, the bound on reversals refers to the number of times any of the counter are allowed to switch from incrementing to decrementing.

Let $DCM$ be the family of languages accepted by deterministic reversal-bounded multicounter machines, and $NCM$ the nondeterministic class.

Let $L^R = \{w^R | w \in L \}$ where $w^R$ is $w$ reversed.

I'm wondering, for $L \in DCM$, is $L^R \in DCM$? Are there subclasses of $DCM$ which have this property?

"Formal Modelling of Viral Gene Compression" by Daley and McQuillan tells that $NCM$ is closed under reversal, but I have found no such reference for the deterministic case.

Answer 1

DCM is not closed under reversal. I don't know of a reference, but it is easy to show it using the expressveness lemmata of Chiniforooshan, E., Daley, M., Ibarra, O.H., Kari, L., Seki, S.: One-reversal counter machines and multihead automata: revisited.

In particular, they state that for any DCM language $L$, there is a word $w$ such that $L \cap w\Sigma^*$ is a nontrivial regular language. Now let $D$ be the following hinted version of the complement of the prefixes of the Dyck language: $$D = \{a^nw_1w_2\cdots w_k \mid w_i \in \{[, ]\} \land |w_1w_2\cdots w_n|_] > |w_1w_2\cdots w_n|_[\}.$$ In other words, $D$ is the complement of the Dyck where the number of $a$'s in the prefix gives a position witnessing the unbalancing of the parentheses. Also, $(\{a\}^*)^{-1}D$ is the complement of the prefixes of the Dyck. Note that $D$ is in DCM. Now consider $D^R$ and a word $w \in \Sigma^* = \{a, [,]\}^*$. Then either $D^R \cap w\Sigma^*$ is finite, or it is nonregular, hence $D^R \notin$ DCM.

I don't know of any interesting subclass of DCM closed under reversal. (Ad placement!) However, we studied a model called Unambiguous constrained automata which is close but not comparable to DCM, and which enjoys closure under reversal --- constrained automata, or Parikh automata, themselves are equivalent to NCM in the nondeterministic case, and a strict subset of DCM in the deterministic case.