@article{b39c1f33c87f4bf5ac50c8ec8603038a,
title = "Balanced-by-Construction Regular and ω-Regular Languages",
abstract = "Parenn is the typical generalization of the Dyck language to multiple types of parentheses. We generalize its notion of balancedness to allow parentheses of different types to freely commute. We show that balanced regular and ω-regular languages can be characterized by syntactic constraints on regular and ω-regular expressions and, using the shuffle on trajectories operator, we define grammars for balanced-by-construction expressions with which one can express every balanced regular and ω-regular language.",
author = "Luc Edixhoven and Sung-Shik Jongmans",
note = "DBLP License: DBLP's bibliographic metadata records provided through http://dblp.org/ are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.",
year = "2023",
month = feb,
doi = "10.1142/S0129054122440026",
language = "English",
volume = "34",
pages = "117--144",
journal = "International Journal of Foundations of Computer Science",
issn = "0129-0541",
publisher = "World Scientific Publishing Co. Pte Ltd",
number = "2&3",
}