Talk:Semiautomaton

Merge from state transition system

I just got done writing the article on semiautomaton when I found the article on state transition systems, which is exactly the same thing. linas 03:53, 19 April 2007 (UTC)[reply]

Hmm. I defering a merge until I get a good book on this. There are a few subtle points I'll get wrong if I bullishly force this merge. linas 03:09, 25 April 2007 (UTC)[reply]

I agree that they should probably be merged. Although state transition system makes a point of saying that the input alphabets / state spaces can be infinite, certainly the same can be true for automata, semigroups and acts, and the like, as long as the word "finite" is not invoked. Incidentally, do you have any information about abelian semiautomata (i.e., the transformations commute)? Daveagp 20:52, 12 September 2007 (UTC)[reply]

I don't think they should be merged, since there is a significantly different emphasis in the presentation and the usage. Many people I know talk all the time about labelled transition systems, for example in structural operational semantics, but would never talk about semiautomata, group actions etc.. I agree that there should be more linking between the two articles, though. I also propose to include at the head of this article (which redirects from transition system) the phrase saying "if you were looking for state transition systems, see ...". Sam Staton 19:11, 28 October 2007 (UTC)[reply]

I concur. "Labelled transition systems are aguably the most fundamental model within theoretical computer science." Winskel et al. 1993, Models for Concurrency, chapter in Oxford Handbook of Logic and the Foundations of Computer Science. Semiautomata were not even mentioned, which suggests the two traditions had not yet even begun to merge just a little over ten years ago. Can you recommend a good source comparing the two? --Jrgetsin 04:25, 12 November 2007 (UTC)[reply]

Is it OK to close the merge now, and leave the pages as they are for the time being? Sam Staton (talk) 09:52, 18 February 2008 (UTC)[reply]

I removed the tag, for the time being.

A related suggestion: I think transition system should redirect to state transition system. And I'd then put a tag at the top of that page. Any objections? Sam Staton (talk) 07:44, 4 April 2008 (UTC)[reply]

No-one objected, so I've done this. Sam Staton (talk) 12:24, 13 April 2008 (UTC)[reply]

Disambiguation of a multiply wrong article

This article claims that a number of related concepts are equivalent. They aren't. There are so many mistakes that I'm not sure where to begin. I start with a minor issue and move on from there.

Transformation semigroups are indeed more-or-less the same thing as transformation monoids. Problems arise, however, when there is additional structure. Suppose that a transformation semigroup consists of compact operators on a Hilbert space. Then we don't want to add the identity, because it isn't a compact operator.
Transformation semigroups/monoids are not the same thing as semigroup/monoid (S,M,left,right...-)acts/actions because there is no requirement that the action should be faithful/effective. In other words, distinct elements of the monoid M could act in the same way on Q. Instead, if a monoid M acts on Q, there is a homomorphism from M to a transformation monoid of Q. It need not be injective.
There is no equivalence in general between left and right actions of a monoid.
Free monoids and free semigroups are different. For instance if Q has one element, then its transformation group consists only of the identity. This is the free monoid on the empty set, but it isn't a free semigroup (the free semigroup on one element consists of all powers of that element).
The full transformation monoid of a set is not a free monoid. We've already seen this for semigroups using a 1-element set. For monoids, we need a two element set {A,B}. Then the full transformation monoid has four elements, determined by what they do to A and B: the identity e=(A,B), the swap s=(B,A) and the projections a=(A,A) and b=(B,B). The free monoid on the empty set has one element, the identity. The free monoid on any nonempty set has infinitely many elements. The full transformation group is e.g. a quotient of the free monoid on {a,s}: it satisfies relations like aa=a, as=a, ss=e,...
A semiautomaton is not the same thing as a monoid action. It induces a monoid action of the free monoid on its alphabet, and hence also a transformation monoid, but one cannot recover the input alphabet from the transformation monoid (although it can be recovered as the set of free generators of the free monoid). It is also not true that any monoid action is obtained from a semiautomaton.
The notion of an M-homomorphism requires that a monoid M is fixed. Consequently the category should be (and usually is) denoted M-Act, where M is a fixed monoid.

I intend to split this page to resolve the many ambiguities and errors indicated above. Geometry guy 22:56, 13 September 2008 (UTC)[reply]

There are indeed some minor ambiguities, but I don't think you need to split the page for those. Can't you just clarify them on the article page itself? VasileGaburici (talk) 17:22, 14 September 2008 (UTC)[reply]

(ec) Transformation semigroups and M-acts are now covered by semigroup action. I've tried to make as little change to semiautomaton as possible, but I've removed the incorrect assertions and eliminated some of the overlap with the new article. More substantial change is probably needed here (the first section is now largely redundant) but I leave that to a computer science oriented editor. Geometry guy 17:31, 14 September 2008 (UTC)[reply]

I don't recommend remerging. One fundamental distinction is that semiautomata have an input alphabet. General monoid actions don't. Another is that general monoid actions include actions of non-free monoids which are not effective. Semiautomata don't give these, however you interpret them. Sure semiautomaton theory is a great application of monoid actions, but they really are different concepts. Merging the two articles would be like (indeed worse than) merging group (mathematics) and permutation group. Geometry guy 17:45, 14 September 2008 (UTC)[reply]

Not quite the same; there's a difference of notability here. There are many books a about permutation groups, but I don't know any that deal just with semiautomata. Having stub-class entry for semiautomaton is certainly feasible, but what would be the point? VasileGaburici (talk) 18:04, 14 September 2008 (UTC)[reply]

First point agreed, but I hope you are not saying that semiautomata are not notable! Second point, "stub-class" does not mean "short", it means in need of substantial expansion. There is no limit on how short a (for example) good article can be, as long as it is broad, well-written and reliably sourced. Wikipedia articles do not need to have entire books written solely about them! There are not (I hope) whole books on absorbing elements, for example. This article has plenty of things to say about semiautomata that would be a digression in the context of general monoid actions. And despite your clean-up edit summary (I barely removed any content from this article), it says them better now than it did before. Geometry guy 18:46, 14 September 2008 (UTC)[reply]

Difference from semigroup action

I've pastied one of the points raised above by User:Geometry guy to this new section so we can discuss it easily. The point was:

A semiautomaton is not the same thing as a monoid action. It induces a monoid action of the free monoid on its alphabet, and hence also a transformation monoid, but one cannot recover the input alphabet from the transformation monoid (although it can be recovered as the set of free generators of the free monoid). It is also not true that any monoid action is obtained from a semiautomaton. Geometry guy 22:56, 13 September 2008 (UTC)[reply]

Well, I'm pretty confused here. KK&M claim that the two a notions are equivalent in a sense: Proposition 4.5 on page 45 states that "Semiautomata can be considered as S-acts and S-acts can be considered as semiautomata (with a possibly non-free input monoid)". But the proof relies on a different(?) notion of input monoid. They define a semiautomaton (A,X,δ) the usual way (A - states, X - input alphabet, δ - next state function), and immediately after that comes "If X is a generating set of a monoid S and one has δ(a, xx') = δ(δ(a, x), x') for any a ∈ A, x,x' ∈ X then S is called the input monoid of (A,X,δ)." It's not clear no me how δ can involve strings (they don't make the extensions to strings until later), and even if you assume that construction, I don't see how this input monoid can be non-free... VasileGaburici (talk) 02:02, 15 September 2008 (UTC)[reply]

Howie in his 1991 book (Automata and Languages) initially defines an automaton as nothing more than the action of a semigroup (which is the same as this article's notion semiautomaton). But he also goes on to extend the concept to non-deterministic automata. I'm going to update the article to reflect the lack of common terminology. VasileGaburici (talk) 19:13, 15 September 2008 (UTC)[reply]

Don't be confused by what authors want to be true but don't prove. Of course, if one allows non-free input monoids (meaning that there are relations on the alphabet) then anything is possible (any monoid is a quotient of the free monoid on any generating set). Similarly, Lidl and Pilz want the notion of a semiautomaton to be "the same" as a monoid (rather than a monoid action). It isn't quite, but it is close enough for them. Wikipedia should focus on the common ground and describe the relations between the concepts that appear in the literature, without wanting things to be the same, when they are actually different. Geometry guy 20:06, 15 September 2008 (UTC)[reply]

Yeah, the KK&M proof is a bit hand-wavish. The best treatment of the correspondence I found is in Howie (1991), pages 82-86. In a nutshell, denoting TM(A) the transformation monoid corresponding to a (semi)automaton, and Aut(X) the automaton obtained from a transformation monoid X, then Aut(TM(A)) does not equal A, but TM(Aut(X)) is isomorphic with X. Howie also gives an example where picking the right generator set G (which is by no means unique) for TM(A), the automaton Aut(G) is the same as A. I think this is what KK&M want to prove. BTW, Howie's definition of a transformation monoid is a bit unusual. He defines it as a semigroup act which is effective (as the article on transformation monoid defined effective, Howie doesn't use the term effective). VasileGaburici (talk) 20:34, 15 September 2008 (UTC)[reply]

Very good, that makes sense. An effective semigroup action is isomorphic to a transformation semigroup in a canonical way, so Howie is not confusing the issue as much as KK&M and others do. Another term for "effective" is "faithful". Geometry guy 21:08, 15 September 2008 (UTC)[reply]

Why not delete the entire chapter "Transformation semigroups and monoid acts"? It just duplicates Semigroup action. --Beroal (talk) 14:46, 20 August 2011 (UTC)[reply]

A less restrictive definition

It looks like other sources let a semiautomaton be non-deterministic, i.e. δ can be a multi-valued function (basically a relation). See http://planetmath.org/encyclopedia/Semiautomaton.html VasileGaburici (talk) 14:35, 15 September 2008 (UTC)[reply]

Adding this to the article is a step in the right direction. It will help make clear that the notion of a semiautomaton can be formalized in different ways, and that analysis in terms of monoids or monoid actions are just two ways of doing this. Geometry guy 20:08, 15 September 2008 (UTC)[reply]

M-homomorphism

I'm rather confused by the section on M-homorphisms. f is defined as sending elements of right acts to other element of right acts, so I would expect f to be defined as $(Q,M,\mu )\to (Q',M',\mu ')$ , just to be consistent with the notation above. Instead, I just infer the type of f as being $Q\to Q$ , since it can take elements of Q, and has to yield elements of Q so that they can be multiplied by m, or maybe it could be $Q\to M$ , that would work too... But I don't see how q or qm could be seen as elements of a right act...