AUTOMATA AND FORBIDDEN WORDS

Authors
CROCHEMORE M MIGNOSI F RESTIVO A
Citation
M. Crochemore et al., AUTOMATA AND FORBIDDEN WORDS, Information processing letters, 67(3), 1998, pp. 111-117
Citations number
9
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
67
Issue
3
Year of publication
1998
Pages
111 - 117
Database
ISI
SICI code
0020-0190(1998)67:3<111:>2.0.ZU;2-F
Abstract
Let L(M) be the (factorial) language avoiding a given anti-factorial l anguage M. We design an automaton accepting L(M) and built from the la nguage M. The construction is effective if M is finite. If M is the se t of minimal forbidden words of a single word nu, the automaton turns out to be the factor automaton of nu (the minimal automaton accepting the set of factors of nu). We also give an algorithm that builds the t rie of M from the factor automaton of a single word. It yields a nontr ivial upper bound on the number of minimal forbidden words of a word. (C) 1998 Published by Elsevier Science B.V. All rights reserved.