Visibly rational expressions |
| |
Authors: | Laura Bozzelli César Sánchez |
| |
Affiliation: | 1. Technical University of Madrid (UPM), Madrid, Spain 2. IMDEA Software Institute, Madrid, Spain 3. Institute for Applied Physics, CSIC, Madrid, Spain
|
| |
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 class of visibly pushdown languages (VPL). We show that VRE capture precisely 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|