Document Open Access Logo

Visibly Rational Expressions

Authors Laura Bozzelli, César Sánchez

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2012.211.pdf
  • Filesize: 0.6 MB
  • 13 pages

Document Identifiers

Subject Classification

Keywords
  • Visibly Pushdown Languages
  • Context-free specifications
  • Regular expressions
  • Algebraic characterization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Regular Expressions (RE) are an algebraic formalism for expressing  regular languages, widely used in string search and as a specification language in verification.  In this paper we introduce and investigate Visibly Rational Expressions (VRE), an extension of  RE for the well-known class of Visibly Pushdown Languages (VPL). We show that VRE capture the class of VPL. Moreover, we identify an equally expressive fragment of VRE  which admits a quadratic time compositional translation into the automata acceptors of VPL. We also prove that, for this fragment, universality, inclusion and language equivalence are EXPTIME-complete.  Finally, we provide an extension of VRE for VPL over infinite words.

Cite As Get BibTex

Laura Bozzelli and César Sánchez. Visibly Rational Expressions. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 211-223, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012) https://doi.org/10.4230/LIPIcs.FSTTCS.2012.211

Author Details

Laura Bozzelli
César Sánchez
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact