UNRESTRICTED AND DISJOINT OPERATIONS OVER MULTI-STACK VISIBLY PUSHDOWN LANGUAGES

Stefan D. Bruda, Tawhid Bin Waez

2011

Abstract

Visibly pushdown languages (VPL) were proposed as a formalism for specifying and verifying complex, recursive systems such as application software. However, VPL are unsuitable for compositional specification, as they are not closed under shuffle. Multi-stack visibly pushdown languages (MVPL) express naturally concurrent constructions. Concurrency cannot be expressed compositionally however, for MVPL are not closed under shuffle either. MVPL operations also restrict rigidly the input alphabets, which hinders the specification of dynamic threads; if we remove these restrictions MVPL loose almost all their closure properties. We find however a natural renaming process that yields disjoint MVPL operations. These operations eliminate the mentioned restrictions and creates closure under shuffle. This effort opens the area of MVPL-based compositional specification and verification.

Paper Citation

in Harvard Style

D. Bruda S. and Bin Waez T. (2011). UNRESTRICTED AND DISJOINT OPERATIONS OVER MULTI-STACK VISIBLY PUSHDOWN LANGUAGES . In Proceedings of the 6th International Conference on Software and Database Technologies - Volume 2: ICSOFT, ISBN 978-989-8425-77-5, pages 156-161. DOI: 10.5220/0003494101560161

in Bibtex Style

@conference{icsoft11,
author={Stefan D. Bruda and Tawhid Bin Waez},
title={UNRESTRICTED AND DISJOINT OPERATIONS OVER MULTI-STACK VISIBLY PUSHDOWN LANGUAGES},
booktitle={Proceedings of the 6th International Conference on Software and Database Technologies - Volume 2: ICSOFT,},
year={2011},
pages={156-161},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003494101560161},
isbn={978-989-8425-77-5},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 6th International Conference on Software and Database Technologies - Volume 2: ICSOFT,
TI - UNRESTRICTED AND DISJOINT OPERATIONS OVER MULTI-STACK VISIBLY PUSHDOWN LANGUAGES
SN - 978-989-8425-77-5
AU - D. Bruda S.
AU - Bin Waez T.
PY - 2011
SP - 156
EP - 161
DO - 10.5220/0003494101560161