Congruences for visibly pushdown languages

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

Research output: Contribution to journalConference articlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)1102-1114
Number of pages13
JournalLecture Notes in Computer Science
StatePublished - 2005
Event32nd International Colloquium on Automata, Languages and Programming, ICALP 2005 - Lisbon, Portugal
Duration: Jul 11 2005Jul 15 2005

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Congruences for visibly pushdown languages'. Together they form a unique fingerprint.

Cite this