The derivational complexity of string-rewriting systems (Algebras, Languages, Algorithms in Algebraic Systems and Computations)
Yuji Kobayashi · Institutional Repositories DataBase (IRDB) · 2010
Derivational complexityLet $\Sigma$ be a (finite) alphabet and let $\Sigma^{*}=\bigcup_{n\geq 0^{\Sigma^{n}}}$ be the free monoid generated by $\Sigma$ .A (string)-rewriting system $R$ is a nonempty subset of $\Sigma^{*}\cross\Sigma^{*}$ .An element $r=(u, v)$ in $R$ is called a rule of $R$ and written $uarrow v$ .Suppose that a word $x\in\Sigma^{*}$ contains $u$ as a subword, that is, $x=x_{1}ux_{2}$ with $x_{1},$ $x_{2}\in\Sigma^{*}$ , then we can apply the rule $r$ to $x$ and $x$ is rewritten to the word $y=x_{1}vx_{2}$ .In this situation we write as $xarrow_{r}y$ .If there is some rule $r\in R$ such that $xarrow_{r}y$ , we write $xarrow Ry$ , and we call the relation $arrow R$ the one-step derivation on $\Sigma^{*}$ by $R$ .A rewriting system $R$ is teminating on $x\in\Sigma^{*}$ if there is no infinite sequence of derivation: $xarrow R^{X}1arrow R\ldotsarrow R^{X}narrow R\ldots$ starting with $x$ .$R$ is teminating (or noetherian), if it is terminating on every $x\in\Sigma^{*}$ .