Balanced-by-Construction Regular and ω-Regular Languages

Luc Edixhoven*, Sung-Shik Jongmans

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review


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.
Original languageEnglish
Pages (from-to)117-144
Number of pages28
JournalInternational Journal of Foundations of Computer Science
Issue number2&3
Publication statusPublished - Feb 2023
Event25th International Conference on Developments in Language Theory 2021 - Porto, Portugal
Duration: 16 Aug 202120 Aug 2021


  • Dyck language
  • regular languages
  • shuffle on trajectories


Dive into the research topics of 'Balanced-by-Construction Regular and ω-Regular Languages'. Together they form a unique fingerprint.

Cite this