concatenation of lists and streams from an alphabet A: - formally given by the unique arrow to a terminal coalgebra - heuristically it is supposed to be thought of as erasing the comma between a pair of streams (a,b) But how is this to be understood computationally? eg. write down all the +ve odd integers and then all the even ones in reverse order to get a stream (1, 3, 5, ., 6, 4, 2) can this be made into a stream specification? ie. what is the behaviour of the dots in the middle? or even more interesting, a countable concatenation (limit ?) as in the so called Sarkovskii sequence uses in symbolic dynamics - Ref: http://hades.ph.tn.tudelft.nl/Internal/PHServices/Documentation/MathWorld/ma... It does not appear conceivable for a Turing machine to produce such a tape! (??) Then in what way can such streams be seen as arrows N --> N ?? Examining the details (Ref: J.J.M.M. Rutten) for the construction of the structure map A*xA* --> 1+AxA*xA* that gives rise to concatenation (for the functor 1+Ax_ ), it does not appear to arise out of universal properties (being an arrow from a product to a coproduct), as do the structure maps for various other operations. Is it distinguished in some particular way? I think of juxtaposition as THE fundamental syntactic operation I hope someone can help me please with formal concatenation. Thank you. .. Al Vilcius
Al Vilcius asks:
concatenation of lists and streams from an alphabet A: - formally given by the unique arrow to a terminal coalgebra - heuristically it is supposed to be thought of as "erasing the comma" between a pair of streams (a,b)
But how is this to be understood computationally? eg. write down all the +ve odd integers and then all the even ones in reverse order to get a stream (1, 3, 5, .........., 6, 4, 2) can this be made into a stream specification? ie. what is the behaviour of the "dots" in the middle?
I don't have the Rutten paper. However, if it says what I expect then the idea is this. A coalgebra X -> 1 + AxX says how an element of X is either empty or can have an atom (from A) pulled off it on the left - in other words, it is a "cons" of a head atom and a tail sequence. Hence an element of X can either have just finitely many atoms pulled off it before it's exhausted, or it can supply infinitely many atoms. This gives the map from X to a final coalgebra A* comprising the finite and countably infinite sequences. The infinite sequences are infinite on the right, not the left, so 1, 3, 5, ... is one, but not ..., 6, 4, 2. The map A*xA* -> 1 + Ax(A*xA*) shows how to pull a head off a pair (s,t) of sequences. If s is non-empty, then take its head. If s is empty, take the head of t. If both are empty then there is no head (so map to the element of 1). The concatenation map A*xA* -> A* therefore acts as follows: if s is finite, then (s,t) maps to (elements of s followed by elements of t) - you pull all the elements of s off, and then when you've finished you start on t. if s is infinite, then (s,t) maps to s. You never finish taking the elements off s. Thus the concatenation question has a simple but boring answer. 1, 3, 5, ... concatenated with anything is just 1, 3, 5, ... again. And this is exactly what will happen if you compute the answer in a lazy programming language with lists, such as Haskell. Steve Vickers Department of Pure Maths Faculty of Maths and Computing The Open University ----------- Tel: 01908-653144 Fax: 01908-652140 Web: http://mcs.open.ac.uk/sjv22 10-Dec-2002 20:57:12 -0400,1055;000000000000-00000000
From: "Al Vilcius" <al.r@vilcius.com> concatenation of lists and streams from an alphabet A: - formally given by the unique arrow to a terminal coalgebra - heuristically it is supposed to be thought of as erasing the comma between a pair of streams (a,b)
But how is this to be understood computationally?
I'm unclear as to the benefits if any of addressing Al's concern in the context of coalgebras, or of anything to do with categories for that matter. Forgetting for the moment any effectiveness that might be implicit in the notion of "stream", the underlying structures here become accessible to a broader audience when presented as labeled chains (linear orders), call these lists, with the list members being the labels. The concatenation of a linearly ordered family of lists is their marked union (with the family's index set providing the marks), augmented to a linear order in the evident way (formally, dependent lexicographic product). With regard to effectiveness, I would expect Al's intuitions to be satisfied by defining the effective part eff(L) (or fin(L) for finite) of a list L as the sublist consisting of those elements having only finitely many predecessors, necessarily a prefix of L. So for example eff(N) = eff(N @ L) = N eff(Z) = eff(R) = eff(Z @ [3,1,4]) = [] eff(R+) = [0] eff([3,1,4] @ Z) = [3,1,4] eff(eff(L)) = eff(L) eff(L @ M) = L @ eff(M) if eff(L) = L = eff(L) otherwise eff(L @ M) = eff(L @ eff(M)) but not eff(L @ M) = eff(eff(L) @ eff(M)) where L,M are any lists, N,Z,R,R+ are the lists of natural numbers, integers, reals, and nonnegative reals standardly ordered, @ (McCarthy's MLISP notation c.1959 for APPEND) is binary concatenation, and [a,b,c] parallels set theory's {a,b,c}. The n-th element (n in N) of L is defined for L iff it is defined for eff(L). The head of a list is its first element, the tail is the sublist that omits just the head, and the domain of both head and tail consists of those lists with nonempty effective part. Al's example of the concatenation of the list of positive odd integers with the reverse of the list of even such then has as its effective part just the positive odd integers. Let me hasten to add that I am not here raising any objection to coalgebraic notions of concatenation in the context of an overall coalgebraic framework, where considerations of uniformity fully justify the use of coalgebraic definitions throughout. For the purposes of answering Al's question however, uniformity merely for its own sake has the potential to become an obstacle to understanding such an elementary issue, at least for those not already thoroughly steeped in the coalgebraic method. Vaughan Pratt
participants (3)
-
Al Vilcius -
S.J.Vickers -
Vaughan Pratt