2 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.FL2015
Factorization in Formal Languages
Paul Bell, Daniel Reidenbach, Jeffrey Shallit
We consider several novel aspects of unique factorization in formal languages. We reprove the familiar fact that the set uf(L) of words having unique factorization into elements of…