|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
24 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
The Dissecting Power of Regular Languages | | Tomoyuki Yamakami
; Yuichi Kato
; | | Date: |
22 Feb 2012 | | Abstract: | A study on structural properties of regular and context-free languages has
promoted our basic understandings of the complex behaviors of those languages.
We continue the study to examine how regular languages behave when they are
"almost halving" numerous infinite languages. In particular, we are focused on
a situation in which a regular language "dissects" a target infinite language
into two infinite subsets. Every context-free language and its complement can
be dissected by carefully chosen regular languages. By expanding the scope of
our study, we show that constantly-growing languages and semi-linear languages
are also dissectable; however, their complements as well as intersections are
not. Under certain natural conditions, the complements and finite intersections
of semi-linear languages become dissectable. Similarly, restricted to bounded
languages, the intersections of finitely many bounded context-free languages
and, more surprisingly, the entire Boolean hierarchy over bounded context-free
languages are dissectable. As an immediate application, we show a structural
property in which an appropriate bounded context-free language can separate,
with infinite margins, two given infinite bounded context-free languages, one
of which contains the other with an infinite margin. This property is closely
related to a notion and result of Demaratzki, Shallit, and Yu (2001). | | Source: | arXiv, 1202.4883 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER