Timeline for Understanding Syntactic Congruence & Order
Current License: CC BY-SA 4.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 20 at 1:57 | vote | accept | Jason Berry | ||
| Apr 19 at 16:06 | comment | added | Jason Berry | 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)? | |
| Apr 19 at 15:26 | comment | added | StefanH | 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. | |
| Apr 19 at 14:38 | comment | added | Jason Berry | 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? | |
| Apr 19 at 13:32 | comment | added | StefanH | 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. | |
| Apr 19 at 9:21 | history | became hot network question | |||
| Apr 19 at 6:54 | history | edited | Daniele Tampieri | CC BY-SA 4.0 |
Fully Math Jaxed
|
| Apr 19 at 3:08 | answer | added | Benjamin Steinberg | timeline score: 5 | |
| Apr 19 at 2:18 | comment | added | CommunityBot | 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. | |
| Apr 19 at 1:48 | review | Close votes | |||
| Apr 26 at 3:01 | |||||
| S Apr 19 at 1:17 | review | First questions | |||
| Apr 19 at 2:18 | |||||
| S Apr 19 at 1:17 | history | asked | Jason Berry | CC BY-SA 4.0 |