The dissecting power of regular languages
From MaRDI portal
Publication:1943627
DOI10.1016/J.IPL.2012.12.006zbMATH Open1259.68116arXiv1202.4883OpenAlexW2963124310MaRDI QIDQ1943627
Yuichi Kato, Tomoyuki Yamakami
Publication date: 20 March 2013
Published in: Information Processing Letters (Search for Journal in Brave)
Abstract: A recent study on structural properties of regular and context-free languages has greatly promoted our basic understandings of the complex behaviors of those languages. We continue the study to examine how regular languages behave when they need to cut numerous infinite languages. A particular interest rests on a situation in which a regular language needs to "dissect" a given infinite language into two subsets of infinite size. Every context-free language is dissected by carefully chosen regular languages (or it is REG-dissectible). In a larger picture, we show that constantly-growing languages and semi-linear languages are REG-dissectible. Under certain natural conditions, complements and finite intersections of semi-linear languages also become REG-dissectible. Restricted to bounded languages, the intersections of finitely many context-free languages and, more surprisingly, the entire Boolean hierarchy over bounded context-free languages are REG-dissectible. As an immediate application of the REG-dissectibility, we show another structural property, in which an appropriate bounded context-free language can "separate with infinite margins" two given nested infinite bounded context-free languages.
Full work available at URL: https://arxiv.org/abs/1202.4883
context-free languageregular languageformal languagessemi-linearbounded languageconstantly growingdissectiblei-separate
Related Items (5)
Three New Algorithms for Regular Language Enumeration ⋮ Unnamed Item ⋮ Dissecting power of intersection of two context-free languages ⋮ Classifying regular languages by a split game ⋮ Unnamed Item
This page was built for publication: The dissecting power of regular languages
