Dyck Language

Tobias Nipkow 📧 and Moritz Roos 📧

June 2, 2025

Abstract

The Dyck language over a pair of brackets, e.g. ( and ), is the set of balanced strings/words/lists of brackets. That is, the set of words with the same number of ( and ), where every prefix of the word contains no more ) than (. In general, a Dyck language is defined over a whole set of matching pairs of brackets.

License

BSD License

Topics

Related publications

  • https://en.wikipedia.org/wiki/Dyck_language

Session Dyck_Language

Used by

Cite

× 
@article{Dyck_Language-AFP,
  author  = {Tobias Nipkow and Moritz Roos},
  title   = {Dyck Language},
  journal = {Archive of Formal Proofs},
  month   = {June},
  year    = {2025},
  note    = {\url{https://isa-afp.org/entries/Dyck_Language.html},
             Formal proof development},
  ISSN    = {2150-914x},
}
Download