Row-Column Combination of Dyck Words

We lift the notion of Dyck language from words to 2-dimensional arrays of symbols, i.e., pictures. We define the Dyck crossword language \(DC_k\) as the row-column combination of Dyck word languages, which prescribes that each column and row is a Dyck word over an alphabet of size 4k. The standard relation between matching parentheses is represented in \(DC_k\) by an edge of the matching graph situated on the picture array. Such edges form a circuit, of path length multiple of four, where row and column matches alternate. Length-four circuits are rectangular patterns, while longer ones exhibit a large variety of patterns. \(DC_k\) languages are not recognizable by the Tiling Systems of Giammarresi and Restivo. \(DC_k\) contains pictures where circuits of unbounded length occur, and where any Dyck word occurs in a row or in a column. We prove that the only Hamiltonian circuits of the matching graph of \(DC_k\) have length four. A proper subset of \(DC_k\) , called quaternate, includes only the rectangular patterns; we define a proper subset of quaternate pictures that (unlike the general ones) preserves a characteristic property of Dyck words: availability of a cancellation rule based on a geometrical partial order relation between rectangular circuits. Open problems are mentioned.