3 papers
cs.FL2017
A Polynomial Time Match Test for Large Classes of Extended Regular Expressions
Daniel Reidenbach, Markus L. Schmid
In the present paper, we study the match test for extended regular expressions. We approach this NP-complete problem by introducing a novel variant of two-way multihead automata, w…
cs.FL2017
Two-Dimensional Pattern Languages
Henning Fernau, Markus L. Schmid, K. G. Subramanian
We introduce several classes of array languages obtained by generalising Angluin's pattern languages to the two-dimensional case. These classes of two-dimensional pattern languages…
cs.CG2017
Combinatorial Properties and Recognition of Unit Square Visibility Graphs
Katrin Casel, Henning Fernau, Alexander Grigoriev +2
Unit square (grid) visibility graphs (USV and USGV, resp.) are described by axis-parallel visibility between unit squares placed (on integer grid coordinates) in the plane. We inve…