Congruences for visibly pushdown languages

Rajeev Alur, Viraj Kumar, Madhusudan Parthasarathy, Mahesh Viswanathan

Research output: Contribution to journalConference article

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.

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

Fingerprint

Context free languages
Formal languages
Syntactics
Congruence
Polynomials
Automata
Module
Context-free Languages
Regular Languages
Polynomial-time Algorithm
If and only if
Minimise
Language
Class

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Congruences for visibly pushdown languages. / Alur, Rajeev; Kumar, Viraj; Parthasarathy, Madhusudan; Viswanathan, Mahesh.

In: Lecture Notes in Computer Science, Vol. 3580, 19.10.2005, p. 1102-1114.

Research output: Contribution to journalConference article

@article{38a6fad6b8054ab3986edc9bdc2b0efd,
title = "Congruences for visibly pushdown languages",
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.",
author = "Rajeev Alur and Viraj Kumar and Madhusudan Parthasarathy and Mahesh Viswanathan",
year = "2005",
month = "10",
day = "19",
language = "English (US)",
volume = "3580",
pages = "1102--1114",
journal = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
issn = "0302-9743",
publisher = "Springer Verlag",

}

TY - JOUR

T1 - Congruences for visibly pushdown languages

AU - Alur, Rajeev

AU - Kumar, Viraj

AU - Parthasarathy, Madhusudan

AU - Viswanathan, Mahesh

PY - 2005/10/19

Y1 - 2005/10/19

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=26444446962&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=26444446962&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:26444446962

VL - 3580

SP - 1102

EP - 1114

JO - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

JF - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SN - 0302-9743

ER -