University of Illinois Urbana-Champaign

Congruences for Visibly Pushdown Languages

Alur, Rajeev; Kumar, Viraj; Madhusudan, P.; Viswanathan, Mahesh

Content Files
Congruences for Visibly Pushdown Languages.pdf

Permalink

https://hdl.handle.net/2142/11214

Description

Title
Congruences for Visibly Pushdown Languages
Author(s)
  • Alur, Rajeev
  • Kumar, Viraj
  • Madhusudan, P.
  • Viswanathan, Mahesh
Issue Date
2005-04
Keyword(s)
computer science
Date of Ingest
2009-04-21T15:38:35Z
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.
Type of Resource
text
Genre of Resource
Technical Report
Permalink
http://hdl.handle.net/2142/11214
Copyright and License 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).

Owning Collections

Research and Tech Reports - Computer Science PRIMARY