Congruences for Visibly Pushdown Languages

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

Permalink

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

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