Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Formal language theory has a deep connection with such areas as static code analysis, graph database querying, formal verification, and compressed data processing. Many application problems can be formulated in terms of languages intersection. The Bar-Hillel theorem states that context-free languages are closed under intersection with a regular set. This theorem has a constructive proof and thus provides a formal justification of correctness of the algorithms for applications mentioned above. Mechanization of the Bar-Hillel theorem, therefore, is both a fundamental result of formal language theory and a basis for the certified implementation of the algorithms for applications. In this work, we present the mechanized proof of the Bar-Hillel theorem in Coq.
Язык оригинала | английский |
---|---|
Название основной публикации | Logic, Language, Information, and Computation |
Подзаголовок основной публикации | 26th International Workshop, Proceedings |
Редакторы | Rosalie Iemhoff, Michael Moortgat, Ruy de Queiroz |
Место публикации | Berlin, Heidelberg |
Издатель | Springer Nature |
Страницы | 264-281 |
ISBN (печатное издание) | 9783662595329 |
DOI | |
Состояние | Опубликовано - 2019 |
Событие | 26th International Workshop on Logic, Language, Information and Communication, WoLLIC 2019 - Utrecht, Нидерланды Продолжительность: 2 июл 2019 → 5 июл 2019 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 11541 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 26th International Workshop on Logic, Language, Information and Communication, WoLLIC 2019 |
---|---|
Страна/Tерритория | Нидерланды |
Город | Utrecht |
Период | 2/07/19 → 5/07/19 |
ID: 48534595