UNAVOIDABLE LANGUAGES, CUTS AND INNOCENT SETS OF WORDS

摘要

A language X on an alphabet A is unavoidable iff all but finitely many words in A~* have a factor in X. In this paper, cuts (which are basically simplifications of languages in terms of avoidability) and innocent language (those which cannot be cut) are defined. Their properties, moat of which are related to unavoidable languages, are studied.