Balanced-by-Construction Regular and ω-Regular Languages

Luc Edixhoven; Sung-Shik Jongmans

doi:10.1142/S0129054122440026

Balanced-by-Construction Regular and ω-Regular Languages

Luc Edixhoven^*, Sung-Shik Jongmans

^*Corresponding author for this work

Research output: Contribution to journal › Article › Academic › peer-review

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.

Original language	English
Pages (from-to)	117-144
Number of pages	28
Journal	International Journal of Foundations of Computer Science
Volume	34
Issue number	2&3
DOIs	https://doi.org/10.1142/S0129054122440026
Publication status	Published - Feb 2023
Event	25th International Conference on Developments in Language Theory 2021 - Porto, Portugal Duration: 16 Aug 2021 → 20 Aug 2021 https://easychair.org/smart-program/DLT2021/

Keywords

Dyck language
regular languages
shuffle on trajectories

Access to Document

10.1142/S0129054122440026

Cite this

@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.",

keywords = "Dyck language, regular languages, shuffle on trajectories",

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.; 25th International Conference on Developments in Language Theory 2021, DLT 2021 ; Conference date: 16-08-2021 Through 20-08-2021",

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",

url = "https://easychair.org/smart-program/DLT2021/",

}

TY - JOUR

T1 - Balanced-by-Construction Regular and ω-Regular Languages

AU - Edixhoven, Luc

AU - Jongmans, Sung-Shik

N1 - 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.

PY - 2023/2

Y1 - 2023/2

N2 - 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.

AB - 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.

KW - Dyck language

KW - regular languages

KW - shuffle on trajectories

U2 - 10.1142/S0129054122440026

DO - 10.1142/S0129054122440026

M3 - Article

SN - 0129-0541

VL - 34

SP - 117

EP - 144

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 2&3

T2 - 25th International Conference on Developments in Language Theory 2021

Y2 - 16 August 2021 through 20 August 2021

ER -

Balanced-by-Construction Regular and ω-Regular Languages

Abstract

Keywords

Access to Document

Fingerprint

Cite this