Grammatical Characterizations of NPDAs and VPDAs with Counters

ABSTRACT:
We give a characterization of NPDAs with reversal-bounded counters (NPCMs) in terms of context-free grammars with monotonic counters. We show that the grammar characterization can be used to give simple proofs of previously known results such as the semilinearity of the Parikh map of any language accepted by an NPCM. We prove a Chomsky-Schutzenberger-like theorem: A language $L$ is accepted by an NPCM if and only if there is a $k \ge 1$ and an alphabet $\Sigma$ containing at least $k$ distinguished symbols, $p_1, ..., p_k$, such that $L = h(D \cap E_k(R))$ for some homomorphism $h$, Dyck language $D \subseteq \Sigma^*$, and regular set $R \subseteq \Sigma^*$, where $E_k(R) = \{w ~|~ w \in R, |w|_{p_1} = \cdots = |w|_{p_k} \}$. We also give characterizations of other restricted machine models, such as visibly pushdown automata with reversal-bounded counters (VPCMs). Finally, we investigate the complexity of some decision problems for these grammatical models.

BIOGRAPHY:
Oscar H. Ibarra is Professor Emeritus and Research Professor in the Department of Computer Science at the University of California-Santa Barbara. He is a Fellow of the American Association for the Advancement of Science, a Fellow of the Institute of Electrical and Electronics Engineers, and a Fellow the Association for Computing Machinery. He is a past recipient of the John Simon Guggenheim Memorial Foundation Fellowship, the IEEE Computer Society's Harry H. Goode Memorial Award, the European Academy of Science Blaise Pascal Medal in Computer Science, the Japan Society for the Promotion of Science Fellowship, the Nokia Visiting Fellowship in Finland, and the UK Royal Academy of Engineering Distinguished Visiting Fellowship. He is a foreign member of Academia Europaea. He is the Editor-in-Chief of the International Journal of Foundations of Computer Science. In July 2015, during the 40th anniversary of the journal, Theoretical Computer Science, Ibarra was named the most prolific author in its 40-year history. His research interests include automata theory, formal languages, design and analysis of algorithms, and computational complexity.