View Related Documents

Abstract

We study congruences on words in order to characterize the class of visibly pushdown languages (Vpl), a subclass of context-free languages. For any language L, we define a natural congruence on words that resembles the syntactic congruence for regular languages, such that this congruence is of finite index if, and only if, L is a Vpl. We then study the problem of finding canonical minimal deterministic automata for Vpls. Though Vpls in general do not have unique minimal automata, we consider a subclass of VPAs called k-module single-entry VPAs that correspond to programs with recursive procedures without input parameters, and show that the class of well-matched Vpls do indeed have unique minimal k-module single-entry automata. We also give a polynomial time algorithm that minimizes such k-module single-entry VPAs.
This research was partially supported by ARO URI award DAAD19-01-1-0473, NSF awards CCR-0306382 and CCF 04-29639, and DARPA/AFOSR MURI award F49620-02-1-0325.

Fulltext Preview

Image of the first page of the fulltext document