Crosswords of formal languages

Speaker: Stefano Crespi Reghizzi
Post thumbnail

The definition of crosswords as row-column combinations of words over an alphabet is applied to regular and context-free (CF) languages, thus producing picture (2D) languages. The letter-to-letter projection of regular crosswords coincides with the well-known family of (tiling system) recognizable pictures. Recent results for the CF case, and especially for the Dyck languages, are presented, that culminate in a generalized Chomsky-Schützenberger Theorem (CST) for CF crosswords. CST represents the family of pictures defined by projection of context-free crosswords, while it fully characterizes the more general family where the crossword is applied to CF languages over two alphabets, whose Cartesian product becomes the picture alphabet. Dyck crosswords exhibit a rich spectrum of 2D patterns that combine the syntax trees of their CF components. Simpler Dyck subfamilies generalize in 2D the well-nesting property of Dyck words.