# dyckword: A library for working with binary Dyck words.

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

Warnings:

• Exposed modules use unallocated top-level names: Math

The binary Dyck language consists of all strings of evenly balanced left and right parentheses, brackets, or some other symbols, together with the empty word. Words in this language are known as Dyck words, some examples of which are `()()()`, `(())((()))`, and `((()()))()`.

The counting sequence associated with the Dyck language is the Catalan numbers, who describe properties of a great number of combinatorial objects.

## Properties

Versions 0.1.0.1, 0.1.0.1, 0.1.0.2, 0.1.0.3, 0.1.0.4 None available base (>=4.7 && <5), exact-combinatorics, text [details] BSD-3-Clause 2017 Johannes Hildén Johannes Hildén johannes@isomorphic.co Math https://github.com/johanneshilden/dyckword#readme head: git clone https://github.com/johanneshilden/dyckword by arbelos at 2017-05-01T07:35:04Z

## Modules

[Index]

#### Maintainer's Corner

For package maintainers and hackage trustees

[back to package description]

# dyckword

In formal language theory, the Dyck language consists of all strings of evenly balanced left and right parentheses, brackets, or some other symbols, together with the empty word. Words in this language (named after German mathematician Walther von Dyck) are known as Dyck words, some examples of which are `()()()`, `(())((()))`, and `((()()))()`.

The type of Dyck language considered here is defined over a binary alphabet. We will take this alphabet to be the set Σ = {(, )} in the following examples. The binary Dyck language is the subset of Σ* (the Kleene closure of Σ) of all words that satisfy two conditions:

1. The number of left brackets must be the same as the number of right brackets.
2. Going from left to right, for each character read, the total number of right brackets visited must be less than or equal to the number of left brackets up to the current position.

E.g., `(()(()` and `())(())()` are not Dyck words.

When regarded as a combinatorial class – with the size of a word defined as the number of bracket pairs it contains – the counting sequence associated with the Dyck language is the Catalan numbers.

Size Count Words
0 1 ε
1 1 ⟨⟩
2 2 ⟨⟩⟨⟩ ⟨⟨⟩⟩
3 5 ⟨⟩⟨⟩⟨⟩ ⟨⟩⟨⟨⟩⟩ ⟨⟨⟩⟩⟨⟩ ⟨⟨⟩⟨⟩⟩ ⟨⟨⟨⟩⟩⟩
4 14 ⟨⟩⟨⟩⟨⟩⟨⟩ ⟨⟩⟨⟩⟨⟨⟩⟩ ⟨⟩⟨⟨⟩⟩⟨⟩ ⟨⟩⟨⟨⟩⟨⟩⟩ ⟨⟩⟨⟨⟨⟩⟩⟩ ⟨⟨⟩⟩⟨⟩⟨⟩ ⟨⟨⟩⟩⟨⟨⟩⟩ ⟨⟨⟩⟨⟩⟩⟨⟩ ⟨⟨⟨⟩⟩⟩⟨⟩ ⟨⟨⟩⟨⟩⟨⟩⟩ ⟨⟨⟩⟨⟨⟩⟩⟩ ⟨⟨⟨⟩⟩⟨⟩⟩ ⟨⟨⟨⟩⟨⟩⟩⟩ ⟨⟨⟨⟨⟩⟩⟩⟩
5 42 ⟨⟩⟨⟩⟨⟩⟨⟩⟨⟩ ⟨⟩⟨⟩⟨⟩⟨⟨⟩⟩ ⟨⟩⟨⟩⟨⟨⟩⟩⟨⟩ ⟨⟩⟨⟩⟨⟨⟩⟨⟩⟩ ⟨⟩⟨⟩⟨⟨⟨⟩⟩⟩ …
6 132