Files in this item



application/pdfCongruences for Visibly Pushdown Languages.pdf (263kB)
(no description provided)PDF


Title:Congruences for Visibly Pushdown Languages
Author(s):Alur, Rajeev; Kumar, Viraj; Madhusudan, P.; Viswanathan, Mahesh
Subject(s):computer science
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 a unique minimal automata, we show that the class of well-matched VPLs does have unique minimal k-module automata. We then present a minimization algorithm, which takes a k-module visibly pushdown automaton and constructs the minimal k-module machine for it in polynomial time.
Issue Date:2005-04
Genre:Technical Report
Other Identifier(s):UIUCDCS-R-2005-2565
Rights Information:You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).
Date Available in IDEALS:2009-04-21

This item appears in the following Collection(s)

Item Statistics