2
$\begingroup$

Reading through Jean-Eric Pin's "Mathematical Foundations of Automata Theory". Love this book. However, I am confused by the following section, and am hoping for some clarity and more examples if possible. I need this for my research.

Syntactic order definition

I am not sure exactly how it is used to create the syntactic order in the following example:

Example

Putting the above example into this automaton:

  • $Q = \{1,2,3\}$
  • $I = \{1\}$
  • $F = \{3\}$
  • $A = \{a,b\}$
  • $E = \{(1,a,2),(2,a,2),(2,b,3),(3,b,3),(3,a,2)\}$

For the above statements $u \le v $ and $s, t \in A*$, $$ sut \in L \implies svt \in L $$ Would this look like the following from the example above?

$(1,a,2) \implies (1,aa,2)$

Does this define the relations from the example above? That is, are the relations from the example above (i.e. '$aa = a$', etc.) syntactic congruence?

And, how are they used to define the syntactic order?

Improve this question
$\endgroup$
5
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    Commented Apr 19 at 2:18
  • $\begingroup$ I guess you are mixing things up here. Instead of $(1,a,2) \Rightarrow (1,aa,2)$ it should be $\forall u,v \in A^* \colon uav \Rightarrow uaav$. You also seem to confuse the order on the states of an automaton and the syntactic order. The difference is similar to the difference of the Nerode right-congruence to the syntactic equivalence. $\endgroup$
    – StefanH
    Commented Apr 19 at 13:32
  • $\begingroup$ Yes, I think I am starting to see. But, one example in the book I still find confusing is in '7 Summary: a complete example', in "Chapter V. Green's Relations and Local Theory", in Jean-Eric Pin's book. It shows these orders: 'aabb -> aa', 'abbb -> abaa', and 'bbb -> baa'. These are state 4 ordered before state 1, why is that? $\endgroup$
    – Jason Berry
    Commented Apr 19 at 14:38
  • $\begingroup$ The order between words is w.r.t. syntactic order, the order on the states is defined differently (see section"ordered automata" in the book). The former can be constructed from the latter. In the mentioned example the automaton has five states, whereas the syntactic monoid has 27 elements, so surely you cannot have the same order on both. $\endgroup$
    – StefanH
    Commented Apr 19 at 15:26
  • $\begingroup$ That makes sense, but from the 27 elements, I see how they are all ordered, except the ones I mentioned above. How are those elements ordered? They are 0040 to 0010, 0400 to 0100, and 4000 to 1000. State order is used to order the 27 elements, how is the final state (4) ordered before the init state (1)? $\endgroup$
    – Jason Berry
    Commented Apr 19 at 16:06

1 Answer 1

Reset to default
5
$\begingroup$

If you have the minimal automaton, then two words are syntactically equivalent iff from any give state they lead to the same state. Therefore the syntactic monoid is the monoid generated by the transformations of the state space given by reading a letter (where functions act on the right) and two words are syntactically equivalent if they represent the same element of this monoid of transformations. They syntactic order can be understood on these transformations the following way. The transformation $u\leq v$ if the for any state $q$ the words leading from $qu$ to a final state are a subset of the words leading from $qv$ to a final state.

Alternatively you can order the states of the minimal automaton by saying $q<q’$ if every word that can reach a final state from $q$ can reach one from $q’$. Then the order on the syntactic monoid is the pointwise ordering. That is $u\leq v$ iff for each state $q$, $qu\leq qv$.

It is not difficult to see that the states in your example are indeed ordered by 0<1<2<3 and then the ordering on elements of the syntactic monoid can be checked directly. One can algorithmically compute the order on states because you are basically comparing the languages obtained by moving around the start state and standard algorithms tell you how to check if one regular language is contained in another. Alternatively I think you can modify the standard dynamical programming method to compute the minimal automaton to instead compute the order.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thank you for your response. Sorry if this is obvious, but to clarify with some examples (for preliminary understanding I work better with examples and cannot find many online). I think of congruence I think of mod (I.e. $16 \equiv 9 \equiv 2 ( mod7)$, always results in 2). But, with finite automata, the results that are the same are states and not the sequence of chars. For example, the following equivalence relations match on state but not char sequence, this is the syntactic congruence? Example: (3,ab,3), (3,aab,3), (3,aaab,3), ..., (3,aabb,3), (3,aaabbb,3), ... $\endgroup$
    – Jason Berry
    Commented Apr 19 at 13:54
  • $\begingroup$ I’m not sure I understand your comment. $\endgroup$
    – Benjamin Steinberg
    Commented Apr 19 at 15:02
  • $\begingroup$ Ok, I think I understand now. $\endgroup$
    – Jason Berry
    Commented Apr 19 at 16:01
  • $\begingroup$ Thanks Ben for your answer ! $\endgroup$
    – J.-E. Pin
    Commented Sep 4 at 17:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .