Balanced-By-Construction Regular and ω-Regular Languages

Luc Edixhoven; Sung-Shik Jongmans

doi:10.1007/978-3-030-81508-0_11

Balanced-By-Construction Regular and ω-Regular Languages

Luc Edixhoven, Sung-Shik Jongmans

Research output: Contribution to conference › Paper › Academic

Abstract

Parenn is the typical generalisation of the Dyck language to multiple types of parentheses. We generalise its notion of balancedness to allow parentheses of different types to freely commute. We show that balanced regular and ω -regular languages can be characterised 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	130-142
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-030-81508-0_11
Publication status	Published - 6 Aug 2021
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/

Conference

Conference	25th International Conference on Developments in Language Theory 2021
Abbreviated title	DLT 2021
Country/Territory	Portugal
City	Porto
Period	16/08/21 → 20/08/21
Internet address	https://easychair.org/smart-program/DLT2021/

Keywords

Dyck language
Regular languages
Shuffle on trajectories

Access to Document

10.1007/978-3-030-81508-0_11

https://dblp.org/rec/conf/dlt/EdixhovenJ21

Cite this

@conference{35c7407fb16c4c4c8eac65cd7594b502,

title = "Balanced-By-Construction Regular and ω-Regular Languages",

abstract = "Parenn is the typical generalisation of the Dyck language to multiple types of parentheses. We generalise its notion of balancedness to allow parentheses of different types to freely commute. We show that balanced regular and ω -regular languages can be characterised 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's bibliographic metadata records provided through http://dblp.org/search/publ/api 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 = "2021",

month = aug,

day = "6",

doi = "10.1007/978-3-030-81508-0_11",

language = "English",

pages = "130--142",

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

}

TY - CONF

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

AU - Edixhoven, Luc

AU - Jongmans, Sung-Shik

N1 - DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api 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 - 2021/8/6

Y1 - 2021/8/6

N2 - Parenn is the typical generalisation of the Dyck language to multiple types of parentheses. We generalise its notion of balancedness to allow parentheses of different types to freely commute. We show that balanced regular and ω -regular languages can be characterised 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 generalisation of the Dyck language to multiple types of parentheses. We generalise its notion of balancedness to allow parentheses of different types to freely commute. We show that balanced regular and ω -regular languages can be characterised 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.1007/978-3-030-81508-0_11

DO - 10.1007/978-3-030-81508-0_11

M3 - Paper

SP - 130

EP - 142

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

Conference

Keywords

Access to Document

Fingerprint

Cite this