On language inequalities XK ⊆ LX
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14310%2F05%3A00025512" target="_blank" >RIV/00216224:14310/05:00025512 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
On language inequalities XK ⊆ LX
Original language description
It is known that for a regular language L and an arbitrary language K the largest solution of the inequality XK subset LX is regular. Here we show that there exist finite languages K and P and star-free languages L, M and R such that the largest solutions of the systems {XK subset LX, X subset M} and {XK subset LX, XP subset RX} are not recursively enumerable.
Czech name
O jazykových nerovnicích XK ⊆ LX
Czech description
Je známo, že pro regulární jazyk L a libovolný jazyk K je největší řešení nerovnice XK subset LX regulární. V práci ukazujeme, že existují konečné jazyky K a P a star-free jazyky L, M a R takové, že největší řešení systémů {XK subset LX, X subset M} a {XK subset LX, XP subset RX} nejsou rekurzívně vyčíslitelná.
Classification
Type
D - Article in proceedings
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
—
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2005
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
Developments in Language Theory: 9th International Conference, DLT 2005, Palermo, Italy, July 4-8, 2005. Proceedings
ISBN
3-540-26546-5
ISSN
—
e-ISSN
—
Number of pages
11
Pages from-to
—
Publisher name
Springer-Verlag
Place of publication
Berlin
Event location
Palermo, Italy
Event date
Jan 1, 2005
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—