On a hierarchy of slender languages based on control sets

Takeshi Koshiba

doi:10.3233/fi-1997-3114

On a hierarchy of slender languages based on control sets

Takeshi Koshiba^*

^*Corresponding author for this work

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

Abstract

We study slender context-sensitive languages, i.e., those containing at most a constant number of words of each length. Recently, it was proved that every slender regular language can be described by a finite union of terms of the form uvⁱw [9] and every slender context-free language can be described by a finite union of terms of the form uvⁱwxⁱ y [4, 10]. We show a hierarchy of slender languages which is properly contained in the family of context-sensitive languages and which starts with the family of slender context-free languages, or slender regular languages. Each slender context-sensitive language in the hierarchy can be described by a finite union of terms of the form x₁y₁ⁱx₂y₂ ⁱ⋯x_ny_nⁱx_n+1.

Original language	English
Pages (from-to)	41-47
Number of pages	7
Journal	Fundamenta Informaticae
Volume	31
Issue number	1
DOIs	https://doi.org/10.3233/fi-1997-3114
Publication status	Published - 1997 Jul
Externally published	Yes

Keywords

Control sets
Cryptosystems
Slender languages

ASJC Scopus subject areas

Theoretical Computer Science
Algebra and Number Theory
Information Systems
Computational Theory and Mathematics

Access to Document

10.3233/fi-1997-3114

Cite this

@article{b0b8f6da2fe544138712508e66b182e3,

title = "On a hierarchy of slender languages based on control sets",

abstract = "We study slender context-sensitive languages, i.e., those containing at most a constant number of words of each length. Recently, it was proved that every slender regular language can be described by a finite union of terms of the form uviw [9] and every slender context-free language can be described by a finite union of terms of the form uviwxi y [4, 10]. We show a hierarchy of slender languages which is properly contained in the family of context-sensitive languages and which starts with the family of slender context-free languages, or slender regular languages. Each slender context-sensitive language in the hierarchy can be described by a finite union of terms of the form x1y1ix2y2 i⋯xnynixn+1.",

keywords = "Control sets, Cryptosystems, Slender languages",

author = "Takeshi Koshiba",

year = "1997",

month = jul,

doi = "10.3233/fi-1997-3114",

language = "English",

volume = "31",

pages = "41--47",

journal = "Fundamenta Informaticae",

issn = "0169-2968",

publisher = "IOS Press",

number = "1",

}

TY - JOUR

T1 - On a hierarchy of slender languages based on control sets

AU - Koshiba, Takeshi

PY - 1997/7

Y1 - 1997/7

N2 - We study slender context-sensitive languages, i.e., those containing at most a constant number of words of each length. Recently, it was proved that every slender regular language can be described by a finite union of terms of the form uviw [9] and every slender context-free language can be described by a finite union of terms of the form uviwxi y [4, 10]. We show a hierarchy of slender languages which is properly contained in the family of context-sensitive languages and which starts with the family of slender context-free languages, or slender regular languages. Each slender context-sensitive language in the hierarchy can be described by a finite union of terms of the form x1y1ix2y2 i⋯xnynixn+1.

AB - We study slender context-sensitive languages, i.e., those containing at most a constant number of words of each length. Recently, it was proved that every slender regular language can be described by a finite union of terms of the form uviw [9] and every slender context-free language can be described by a finite union of terms of the form uviwxi y [4, 10]. We show a hierarchy of slender languages which is properly contained in the family of context-sensitive languages and which starts with the family of slender context-free languages, or slender regular languages. Each slender context-sensitive language in the hierarchy can be described by a finite union of terms of the form x1y1ix2y2 i⋯xnynixn+1.

KW - Control sets

KW - Cryptosystems

KW - Slender languages

UR - http://www.scopus.com/inward/record.url?scp=0031189427&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0031189427&partnerID=8YFLogxK

U2 - 10.3233/fi-1997-3114

DO - 10.3233/fi-1997-3114

M3 - Article

AN - SCOPUS:0031189427

SN - 0169-2968

VL - 31

SP - 41

EP - 47

JO - Fundamenta Informaticae

JF - Fundamenta Informaticae

IS - 1

ER -

On a hierarchy of slender languages based on control sets

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this