Logic Matrices - automata theory

[Omega0]

Hi,

First let's say you have an input vector and an output vector describing states. Let us use a binary number system, it doesn't really matter for mathematics.
Say, I have an input vector V, components v_i. Now I would like to have an output vector W which can be of other dimension. The allowed mathematical relations between the input components are AND, OR, XOR, NOT for example.
Let me write one example:

w_2 = 1 if ((v_1 AND NOT v_2) OR (NOT v_1 AND v_3) else 0

I thought about some simple transition matrix

W = A1 * V

but as it seems to me the OR (or XOR) is the killer, it makes the system of equations nonlinear, right?
The question finally is: How can I write down code with not that many logical implications but using logical matrices... not sure... thanks for a hint!

 

[Stephen Tashi]

it makes the system of equations nonlinear, right?

You haven't defined any system of equations. What are the unknowns in the problem?

Suppose we are dealing with vectors, each of whose components is either 0 or 1.
Let v be the a vector. Let w be a vector. Suppose each component w of w is formed by performing a fixed set of boolean operations on the components of V. The set of operations may be different for each different component of w.

You seem to be wondering about how the above situation could be represented by an expression that uses matrix multiplication. Suppose I have a single matrix M, each of whose entries can be only one of the following three values {0, 1, -1}. If the dimensions of M are appropriate so that the equation w = M v makes sense. Then each entry w can be interpreted as an OR of terms and each term can be interpreted as v[j] or NOT v[j] for some component v[j] of v. There won't be any terms that can be interpreted as the AND of two different components of v.

So I don't see why you say that the OR-operation is the killer.

 

[Omega0]

You haven't defined any system of equations. What are the unknowns in the problem?

Suppose we are dealing with vectors, each of whose components is either 0 or 1.
Let v be the a vector. Let w be a vector. Suppose each component w of w is formed by performing a fixed set of boolean operations on the components of V. The set of operations may be different for each different component of w.

You seem to be wondering about how the above situation could be represented by an expression that uses matrix multiplication. Suppose I have a single matrix M, each of whose entries can be only one of the following three values {0, 1, -1}. If the dimensions of M are appropriate so that the equation w = M v makes sense. Then each entry w can be interpreted as an OR of terms and each term can be interpreted as v[j] or NOT v[j] for some component v[j] of v. There won't be any terms that can be interpreted as the AND of two different components of v.

So I don't see why you say that the OR-operation is the killer.

There are no unknowns. It is just a transformation, I can ask for every component of the input vector and I get a value. Now I logically combine them to an output. There is no equation to be solved. The combination of the mathematical operations of the input vector can be pretty complex. Say, we have just AND and OR and NOT.

Let us say the operation is the following, an easy case:

y_i = TRUE if ( (all x_k for k < i = TRUE) AND NOT ( OR (all x_k for k >= i) = TRUE))) ELSE FALSE

I simply check, if the entries in the vector before are TRUE and if so I check if any other element of the input vector is true.

As it seems this is a matrix product, isn't it? I just decouple the logical elements into different matrices? Is it that simple? Damn...

 

[Stephen Tashi]

There is no equation to be solved.

Then why did your original post speak of "the system of equations"?

As it seems this is a matrix product, isn't it?

You still haven't said what the elements of the matrix, (or matrices) would be.

I find the following question interesting and it be what you're trying to ask.

Suppose we have a column vector of boolean functions <w[1],w[2]...,w[m]>. Each function W is given by a known boolean expressoin of a column vector of N input boolean variables < v[1],v[2],..,v[n]. >

Is it always possible to represent the vector w (using boolean arithmetic) as w = C v where C is an m by n matix and C itself is a finite product of matrices C = C[1]C[2]...C[k] where each matrix C[k] is a matrix whose elements are either constants (0 or 1) or single elements of v?

For example, a matrix $C[j]$ might have the form

$$C[j] = \begin{pmatrix} 1 & v[3] & v[2] \\ v[1] & 0 & 1 \\ v[2]& v[1] & 1 \\ 0 & 0 & v[2] \end{pmatrix}$$

 

[Omega0]

Then why did your original post speak of "the system of equations"?

As far as I know an equation is nothing else but a binary correlation between two terms (sorry about wrong terms and my English) where the assumption is that both sides are equal. A system of equations means nothing else but to write down equations which you would like to unify. A coupled system of equations are more than one equation but they depend from each other.
On the left side of the "=" you write the image set, to the right you place the input.
This are equat
ions to me, I am physicist, so shame on me if I got it wrong :)

You still haven't said what the elements of the matrix, (or matrices) would be.

I find the following question interesting and it be what you're trying to ask.

Suppose we have a column vector of boolean functions <w[1],w[2]...,w[m]>. Each function W is given by a known boolean expressoin of a column vector of N input boolean variables < v[1],v[2],..,v[n]. >

Is it always possible to represent the vector w (using boolean arithmetic) as w = C v where C is an m by n matix and C itself is a finite product of matrices C = C[1]C[2]...C[k] where each matrix C[k] is a matrix whose elements are either constants (0 or 1) or single elements of v?

For example, a matrix $C[j]$ might have the form

$$C[j] = \begin{pmatrix} 1 & v[3] & v[2] \\ v[1] & 0 & 1 \\ v[2]& v[1] & 1 \\ 0 & 0 & v[2] \end{pmatrix}$$

I believe I understand what you say - but I am not sure if precisely asked the question.
It is about a state machine. Actually I have a design where every state is in a table.
In this table I have a transition function. This transition function has a bundle of logical statements. The return value is the next state.

I hope this is mathematical enough:

I have a set of states {s_1, ...,s_N} and I have set of inputs {i_1..., i_M}. I have a set of transitions {t_1, ... t_N}. For every state the following needs to be valid: s_i(t_i)=s_j. You may say, okay this is one to one, why not combine them to {c_1,... c_N}. It is because I can give the states a new thing, let us call it timer {w_1,... w_N}. Meaning: Jump from state s_e to state s_f via the transition t_e but wait for the time of w_e. You will get a set of outputs {o_1,...,o_K}
And now I run into the "problem": The definition of the transition. This depends from the set of inputs and can depend on the output (example: you go from s_1 (o_1 is set) to s_2 when t_1 is given. If you have t_2 and o_1 then t_3 ).
The point is: What about those transitions?
The transition is a function of the inputs. If I try now to define a new set of logical operators L = {l_1,... l_h} and I try now to manage this t_i(L,I) = s_(i+1) then I I am an my current position: I would like to have readable logic stuff.
I am not sure if this transition in matrix style makes sense, no clue..

 

[Stephen Tashi]

It is about a state machine.

I have a set of states {s_1, ...,s_N} and I have set of inputs {i_1..., i_M}. I have a set of transitions {t_1, ... t_N}. [QUOTE[

OK, that is clear.

For every state the following needs to be valid: s_i(t_i)=s_j.

I don't understand which state the quantifier "For every state" refers to. The statement mentions two states s_i and s_j.

You may say, okay this is one to one, why not combine them to {c_1,... c_N}.

I don't know what "them" refers to. Does it refer to the transisitions {t_1,t_2,...} ?

It is because I can give the states a new thing, let us call it timer {w_1,... w_N}. Meaning: Jump from state s_e to state s_f via the transition t_e but wait for the time of w_e.

For a state s_i, is the timer w_i a constant time? Is it the time to transition to any other state? For example, does the transition from s_3 to s_2 take the same time as the transition from s_3 to s_9 ?

You will get a set of outputs {o_1,...,o_K}

What do the outputs depend upon?

And now I run into the "problem": The definition of the transition. This depends from the set of inputs and can depend on the output (example: you go from s_1 (o_1 is set) to s_2 when t_1 is given. If you have t_2 and o_1 then t_3 ).

If you want to have a true state machine then your definition of "state" must include enough information so that the current state and the current input determine the next state. if the next state also depends on a set of "outputs", you don't have a state machine unless you redefine the meaning of "input" so that it includes the "outputs" as a subset.

I don't yet understand how this relates to the original topic of using matrices to compute logical expressions.

 

[Omega0]

I don't understand which state the quantifier "For every state" refers to. The statement mentions two states s_i and s_j.

I just want to say that every state does depend from a transition and the following state s_j in the set of states is given by a state depending from the transition... this may be not correct in a mathematical way but s_i(t_i)=s_j means nothing else but that s_j is the following state if s_i is reached and t_i is applied.

I don't know what "them" refers to. Does it refer to the transisitions {t_1,t_2,...} ?

Every state s_i has a transition function t_i, so one could say: Call it c_i. It is as you would have the function s:N -> N, s(n)=n.

For a state s_i, is the timer w_i a constant time? Is it the time to transition to any other state? For example, does the transition from s_3 to s_2 take the same time as the transition from s_3 to s_9 ?

It is just some freedom in "coloring" the transition. If it would be the same time, I surely wouldn't think about it. Like a traffic light: Yellow is short but green and red can take more time. Every state has a timer to be able to get into another state.

What do the outputs depend upon?

The output is defined in every state and depends from the input. For example switch on the yellow light after the light was green.

If you want to have a true state machine then your definition of "state" must include enough information so that the current state and the current input determine the next state. if the next state also depends on a set of "outputs", you don't have a state machine unless you redefine the meaning of "input" so that it includes the "outputs" as a subset.

You are absolutely right. Say I switch to the state yellow. I want to be sure here that green is on. I get a signal from the traffic light, green is working. Now, that's the idea: Is the "out" still working, that's a microcontroller issue. I want to have the best possible reliability. It is just a lot of "AND" more.

I don't yet understand how this relates to the original topic of using matrices to compute logical expressions.

In this state machine I have those transition functions and call me lazy but I search for a way to implement these not in a way like if(A AND B AND C OR) whatever. I search for a way (this is pure software) to not write all that logical implications. I would love it to have an understandable logic matrix (if possible) for this transition functions. I guess this is not possible.

 

[Stephen Tashi]

I guess this is not possible.

I think it is possible, but I would need understand a specific example of your automata before forming a definite opinion.

Since this problem sounds like an electrical engineering problem, you could also ask about it in the sections of the forum related to engineering and the sections related to programming. Are you coding this in a general purpose programming language like C? Or are you using a language like VHDL?

 

[Omega0]

Thanks, it is C. Here a snippet. The automata

struct t_state_table state_table[16] = {
{ 12000 , &tS_NULL },
{ 12000 , &tS_EINS },
{ 12000 , &tS_ZWEI },
{ 12000 , &tS_DREI },
{ 12000 , &tS_VIER },
{ 12000 , &tS_FUENF },
{ 12000 , &tS_SECHS },
{ 12000 , &tS_SIEBEN },
{ 12000 , &tS_ACHT },
{ 12000 , &tS_NEUN },
{ 12000 , &tS_A },
{ 12000 , &tS_B },
{ 12000 , &tS_C },
{ 12000 , &tS_D },
{ 12000 , &tS_E },
{ 12000 , &tS_F }

};


extern volatile state_t state;
extern volatile uint16_t zaehler;
state_t newstate;void stateMachine()
{
if (zaehler > 0) {
zaehler--;
}
else {

newstate = (*((state_table[state].fkt)))();
state = newstate;
zaehler = state_table[state].counter;
}

}

The automata is using transition functions:

state_t tS_NULL() {
siebensegment(S_NULL);
if (PA0_Ein L_ANDNOT PA1_Ein L_ANDNOT PA2_Ein L_ANDNOT PA3_Ein L_ANDNOT PA4_Ein L_ANDNOT PA5_Ein L_ANDNOT PA6_Ein L_AND PA7_Ein L_ANDNOT Taste1) {
return S_EINS;
}
else if Taste1 return S_NULL;
else return S_NULL;

};

I think it is nice idea to use transitions with a matrix. As you can see the transition function in this easy example uses some logical expressions. Now I think about something like logical vectors - but I am not sure if this really helps. If you think about reliability it might be that this is not readable any more. You are right, this might be more for an engineering forum but thanks for your help.

 

[Stephen Tashi]

I browsed the web and noticed "binary decision diagrams" (http://en.wikipedia.org/wiki/Binary_decision_diagram). That may have nothing to do with matrices, but it just seems "the right way" to organize the evaluation of boolean expressions. I suppose the data structure would be a tree instead of a matrix.