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.

Original languageEnglish
Title of host publicationLogic, Language, Information, and Computation
Subtitle of host publication26th International Workshop, Proceedings
EditorsRosalie Iemhoff, Michael Moortgat, Ruy de Queiroz
Place of PublicationBerlin, Heidelberg
PublisherSpringer Nature
Pages264-281
ISBN (Print)9783662595329
DOIs
StatePublished - 2019
Event26th International Workshop on Logic, Language, Information and Communication, WoLLIC 2019 - Utrecht, Netherlands
Duration: 2 Jul 20195 Jul 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11541 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference26th International Workshop on Logic, Language, Information and Communication, WoLLIC 2019
Country/TerritoryNetherlands
CityUtrecht
Period2/07/195/07/19

    Research areas

  • Bar-Hillel theorem, Closure, Context-free language, Coq, Formal languages, Intersection, Regular language

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 48534595