Cheap and Secure Web Hosting Provider : See Now

Arden's rule expressed as matrix algebra

, , No Comments
Problem Detail: 

The following theorem is (in the context of languages) known as Arden's Lemma: Given a linear system $X = B+AX$ and the matrix A is quasiregular, then we have a solution which is unique and which preserves rationality. In the next lemma we show the converse: For every rational series we can find a linear system such that the first component of its solution vector is exactly the given series. With these two results we have already done most of the work for proving the Theorem of Schutzenberger, which teaches us that the families of rational and recognizable series coincide.

Theorem 2.2.1

Let $B \in \mathbb{K}\langle\langle\Sigma^*\rangle\rangle^{n,1}$ and $A \in \mathbb{K}\langle\langle\Sigma^*\rangle\rangle^{n,n}$ a quasiregular matrix. The linear system

$$ X = B + AX $$

has the unique solution $X = A^∗B$. Moreover, if $A$ and $B$ are $\mathbb{K}-rational$ then the solution $X$ is $\mathbb{K}-rational$.

Proof:

First we show that $X = A^∗B$ is a solution:

$$ B + AX = B + AA^∗ B = (I + AA^∗)B = A^∗B = X. $$

My question is as follows: what does asterisk mean in this context (when it is used with matrices)? I know what Arden's Lemma is, but I don't understand the proof given here.

To credit the author of this paper: Regular Languages And Their Generating Functions: The Inverse Problem by Christoph Koutschan.

Asked By : wvxvw

Answered By : Yuval Filmus

The notation is probably defined in the paper or in some standard reference, but one can guess that $$ A^* = (I - A)^{-1}. $$ This definition satisfies the identity $A^* = I+AA^*$, since $$ I+AA^* = I-((I-A)-I)A^* = I-(I-A)A^*+A^* = I-I+A^* = A^*. $$ Presumably a quasiregular matrix $A$ is one for which $I-A$ is invertible, perhaps with some additional assumptions.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47551

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback