Computing forbidden words of regular languages

Issue title: Computing Patterns in Strings

Article type: Research Article

Authors: Béal, Marie-Pierre | Crochemore, Maxime | Mignosi, Filippo | Restivo, Antonio | Sciortino, Marinella

Affiliations: Institut Gaspard-Monge, Université de Marne-la-Vallée, 77454 Marne-la-Vallée Cedex 2, France | Dipartimento di Matematica ed Applicazioni, Università di Palermo, Via Archirafi 34, 90123 Palermo, Italy

Abstract: We give a quadratic-time algorithm to compute the set of minimal forbidden words of a factorial regular language. We give a linear-time algorithm to compute the minimal forbidden words of a finite set of words. This extends a previous result given for the case of a single word only. We also give quadratic-time algorithms to check whether a regular language is factorial or anti-factorial.

Keywords: Anti-factorial language, factor automaton, factorial language, failure function, forbidden word, formal languages, sofic shift, symbolic dynamics

Journal: Fundamenta Informaticae, vol. 56, no. 1-2, pp. 121-135, 2003