PrefixSet 2006-08-25 06:07:18 2006-08-25 06:08:45 Definition prefix prefix set free semigroup word % this is the default PlanetMath preamble. as your knowledge % of TeX increases, you will probably want to edit this, but % it should be fine as is for beginners. % almost certainly you want these \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsfonts} % used for TeXing text within eps files %\usepackage{psfrag} % need this for including graphics (\includegraphics) %\usepackage{graphicx} % for neatly defining theorems and propositions %\usepackage{amsthm} % making logically defined graphics %\usepackage{xypic} % there are many more packages, add them here as you need them % define commands here \newcommand{\prefi}{\mathrm{pref}} Let $X$ be a set, and $w\in X^*$ be a word, i.e. an element of the free monoid on $X$. A word $v\in X^*$ is called \emph{prefix} of $w$ when a second word $z\in X^*$ exists such that $x=vz$. Note that the empty word $\varepsilon$ and $w$ are prefix of $w$. The \emph{prefix set} of $w$ is the set $\prefi(w)$ of prefixes of $w$, i.e. if $w=w_1w_2...w_n$ with $w_j\in X$ for each $j\in\{1,...,n\}$ we have $$\prefi(w)=\{\varepsilon,\ w_1,\ w_1w_2,\ ... ,\ w_1w_2...w_{n-1},\ w\}.$$