|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
A Structural Lemma for Deterministic Context-Free Languagesстатья
Информация о цитировании статьи получена из
Scopus
Дата последнего поиска статьи во внешних источниках: 20 мая 2019 г.
- Автор: Rubtsov A.A.
- Сборник: Developments in Language Theory 22nd International Conference, DLT 2018, Tokyo, Japan, September 10-14, 2018, Proceedings
- Серия: Theoretical Computer Science and General Issues
- Том: 11088
- Год издания: 2018
- Издательство: SPRINGER HEIDELBERG
- Местоположение издательства: TIERGARTENSTRASSE 17, HEIDELBERG, GERMANY,D-69121
- Первая страница: 553
- Последняя страница: 565
- DOI: 10.1007/978-3-319-98654-8_45
- Аннотация: Мы представляем новую структурную лемму для детерминированных контекстно-свободных языков. На первый взгляд, она выглядит как лемма о накачке, потому что она также основана на итеративных свойствах, но она имеет значительные отличия, которые сильно упрощают её применение. Структурная лемма является комбинаторным аналогом KC-DCF-леммы (основанной на колмогоровской сложности), представленной М. Ли и П. Витаньи в 1995 г. и исправленной О. Глиером в 2003 г. Структурная лемма позволяет не только доказать, что КС-язык не является детерминированным КС-языком, но и раскрывает структуру классов Майхилла-Нероуда.
- Добавил в систему: Верещагин Николай Константинович