Visibly Pushdown Automata and Transducers with Counters

Abstract

We generalize the models of visibly pushdown automata (VPDAs) and visibly pushdown transducers (VPDTs) by equipping them with reversal-bounded counters. We show that some of the results for VPDAs and VPDTs (e.g., closure under intersection and decidability of emptiness for VPDA languages) carry over to the generalized models, but other results (e.g., determinization and closure under complementation) do not carry over, in general. We define a model that combines the desirable features of a VPDA and reversal-bounded counters, called 2-phase VPCM, and show that the deterministic and nondeterministic versions are equivalent and that the family of languages they define is closed under Boolean operations and has decidable emptiness, infiniteness, disjointness, containment, and equivalence problems. We also investigate the finite-ambiguity and finite-valuedness problems concerning these devices.