KUNC, Michal. On language inequalities XK ⊆ LX. In Developments in Language Theory: 9th International Conference, DLT 2005, Palermo, Italy, July 4-8, 2005. Proceedings. Berlin: Springer-Verlag, 2005, p. 327-337. ISBN 3-540-26546-5.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name On language inequalities XK ⊆ LX
Name in Czech O jazykových nerovnicích XK ⊆ LX
Authors KUNC, Michal (203 Czech Republic, guarantor).
Edition Berlin, Developments in Language Theory: 9th International Conference, DLT 2005, Palermo, Italy, July 4-8, 2005. Proceedings, p. 327-337, 2005.
Publisher Springer-Verlag
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10101 Pure mathematics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
WWW URL
RIV identification code RIV/00216224:14310/05:00025512
Organization unit Faculty of Science
ISBN 3-540-26546-5
Keywords in English Language inequality; Regular language; Recursively enumerable language; Minsky machine
Tags Language inequality, Minsky machine, Recursively enumerable language, Regular language
Changed by Changed by: doc. Mgr. Michal Kunc, Ph.D., učo 2906. Changed: 24/6/2009 14:50.
Abstract
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.
Abstract (in Czech)
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á.
Links
MSM0021622409, plan (intention)Name: Matematické struktury a jejich fyzikální aplikace
Investor: Ministry of Education, Youth and Sports of the CR, Mathematical structures and their physical applications
PrintDisplayed: 3/5/2024 07:51