Zuckerman functor - Revision history

en>Wavelength: inserting 1 hyphen—wikt:finite-dimensional

2014-03-11T19:25:30Z

inserting 1 hyphen—wikt:finite-dimensional

← Older revision		Revision as of 21:25, 11 March 2014
Line 1:		Line 1:
	In [[mathematics]] and [[computer science]], a '''history monoid''' is a way of representing the histories of concurrently running computer [[process (computer science)\|processes]] as a collection of [[string (computer science)\|strings]], each string representing the individual history of a process. The history monoid provides a set of [[synchronization primitive]]s (such as [[lock (computer science)\|locks]], [[mutex]]es or [[thread join]]s) for providing rendezvous points between a set of independently executing processes or threads.		I would like to introduce myself to you, I am Jayson Simcox but I don't like when individuals use my complete name. Doing ballet is something she would never give up. Invoicing is what I do. My spouse and I live in Mississippi and I love each working day living here.<br><br>Feel free to surf to my web-site ... [http://www.youronlinepublishers.com/authWiki/AdolphvhBladenqq psychic readings]

	History monoids occur in the theory of [[concurrent computation]], and provide a low-level mathematical foundation for [[process calculi]], such as CSP the language of [[communicating sequential processes]], or CCS, the [[calculus of communicating systems]]. History monoids were first presented by M.W. Shields.<ref>M.W. Shields "Concurrent Machines", ''Computer Journal'', (1985) '''28''' pp. 449–465.</ref>

	~~History monoids are isomorphic~~ to ~~[[trace monoid]]s (free partially commutative monoids) and~~ to ~~the [[monoid]] of [[dependency graph]]s. As such~~, ~~they are [[free object]]s and are [[universal property\|universal]]. The history monoid is a type of semi-abelian [[categorical product]] in the [[category (mathematics)\|category]] of monoids.~~

	~~==Product monoids and projection==~~
	~~Let~~
	~~:<math>A=(\Sigma_1,\Sigma_2,\ldots,\Sigma_n)</math>~~

	~~denote an ''n~~'~~'-tuple of [[alphabet (computer science)\|alphabets]] <math>\Sigma_k</math>. Let <math>P(A)</math> denote all possible combinations of finite-length strings from the alphabets:~~

	~~:<math>P(A)=\Sigma_1^* \times \Sigma_2^* \times \cdots \times \Sigma_n^*</math>~~

	(In more formal language, <math>P(A)</math> is the [[Cartesian product]] of the [[free monoid]]s of the <math>\Sigma_k</math>. The superscript star is the [[Kleene star]].) Composition in the product monoid is component-wise, so that, for

	~~:<math>\bold{u}=(u_1,u_2,\ldots,u_n) \, </math>~~

	~~and~~

	~~:<math>\bold{v}=(v_1,v_2,\ldots,v_n) \, </math>~~

	~~then~~

	~~:<math>\bold{uv}=(u_1v_1,u_2v_2,\ldots,u_nv_n) \, </math>~~

	~~for all <math>\bold{u}, \bold{v}</math> in <math>P(A)</math>. Define the union alphabet to be~~

	~~:<math>\Sigma=\Sigma_1 \cup \Sigma_2 \cup \cdots \cup \Sigma_n. \,</math>~~

	(The union here is the [[set union]], not the [[disjoint union]].) Given any string <math>w\in \Sigma^</math>, we can pick out just the letters in some <math>\Sigma_k^</math> using the corresponding [[string projection]] <math>\pi_k:\Sigma^\to\Sigma_k^</math>. A '''distribution''' <math>\pi:\Sigma^\to P(A)</math> is the mapping that operates on <math>w\in \Sigma^</math> with all of the <math>\pi_k</math>, separating it into components in each free monoid:

	~~:<math>\pi(w)\mapsto (\pi_1(w), \pi_2(w), \ldots , \pi_n(w)). \,</math>~~

	~~==Histories==~~
	For every <math>a\in\Sigma</math>, the tuple <math>\pi(a)</math> is called the '''elementary history''' of ''a''. It serves as an [[indicator function]] for the inclusion of a letter ''a'' in an alphabet <math>\Sigma_k</math>. That is,

	~~:<math>\pi(a)=(a_1,a_2,\ldots,a_n)</math>~~

	~~where~~

	~~:<math>a_i=\begin{cases}~~
	~~a \mbox{ if } a\in \Sigma_k \\~~
	~~\varepsilon \mbox { otherwise }.~~
	~~\end{cases}</math>~~

	Here, <math>\varepsilon</math> denotes the [[empty string]]. The '''history monoid''' <math>H(A)</math> is the [[free monoid]] generated by elementary histories. It is clearly a submonoid of the product monoid <math>P(A)</math>. The elements of <math>H(A)</math> are called '''global histories''', and the projections of a global history are called '''individual histories'''.

	~~==Connection to computer science==~~
	~~The~~ use ~~of the word ''history'' in this context, and the connection to concurrent computing, can be understood as follows~~. An individual history is a record of the sequence of [[state (computer science)\|states]] of a process (or [[thread (computer science)\|thread]] or [[Turing machine\|machine]]); the alphabet <math>\Sigma_k</math> is ~~the set of states of the process.~~

	~~A letter that occurs in two or more alphabets serves as a [[synchronization primitive]] between the various individual histories~~. ~~That~~ is~~, if such a letter occurs in one individual history, it must also occur in another history, and serves to "tie" or "rendezvous" them together.~~

	Consider, for example, <math>\Sigma_1=\{a,b,c\}</math> and <math>\Sigma_2=\{a,d,e\}</math>. The union alphabet is of course <math>\Sigma=\{a,b,c,d,e\}</math>. The elementary histories are <math>(a,a)</math>, <math>(b,\varepsilon)</math>, <math>(c,\varepsilon)</math>, <math>(\varepsilon,d)</math> and <math>(\varepsilon,e)</math>. In this example, an individual history of the first process might be <math>bcbcc</math> while the individual history of the second machine might be <math>ddded</math>. Both of these individual histories are represented by the global history <math>bcbdddcced</math>, since the projection of this string onto the individual alphabets yields the individual histories. ~~In the global history, the letter <math>b</math> can be considered to commute with the letters <math>d</math>~~ and ~~<math>e</math>,~~ in ~~that these can be rearranged without changing the individual histories. Such commutation is simply a statement that the first and second processes are running concurrently,~~ and ~~are unordered with respect to~~ each ~~other; they have not (yet) exchanged any messages or performed any synchronization~~.

	~~The letter~~ <~~math~~>a<~~/math~~> serves as a synchronization primitive, as its occurrence marks a spot in both the global and individual histories, that cannot be commuted across. Thus, while the letters <math>b</math> and <math>c</math> can be re-ordered past <math>d</math> and <math>e</math>, they cannot be reordered past <math>a</math>. Thus, the global history <math>bcdabe</math> and the global history <math>bdcaeb</math> both have as individual histories <math>bcab</math> and <math>dae</math>, indicating that the execution of <math>d</math> may happen before or after <math>c</math>. However, the letter <math>a</math> is synchronizing, so that <math>e</math> is guaranteed to ~~happen after <math>c</math>, even though <math>e</math> is in a different [[process (computer science)\|process]] than <math>c</math>.~~

	~~==Properties==~~
	~~The history monoid is isomorphic~~ to the [[trace monoid]], and as such, is a type of semi-abelian [[categorical product]] in the [[category (mathematics)\|category]] of monoids. In particular, the history monoid <math>H(\Sigma_1,\Sigma_2,\ldots,\Sigma_n)</math> is isomorphic to the trace monoid <math>\mathbb{M}(D)</math> with the [[dependency relation]] given by

	~~:<math>D=\left(\Sigma_1\times\Sigma_1\right)\cup~~
	~~\left(\Sigma_2\times\Sigma_2\right)\cup \cdots \cup~~
	~~\left(\Sigma_n\times\Sigma_n\right).</math>~~

	In simple terms, this is just the formal statement of the informal discussion given above: the letters in an alphabet <math>\Sigma_k</math> can be commutatively re-ordered past the letters in an alphabet <math>\Sigma_j</math>, unless they are letters that occur in both alphabets. Thus, traces are exactly global histories, and vice-~~versa.~~

	~~==Notes==~~
	~~<references/>~~

	~~==References==~~
	* Antoni Mazurkiewicz, "Introduction to Trace Theory", pp 3–41, in ''The Book of Traces'', V. ~~Diekert, G~~. ~~Rozenberg, eds~~. ~~(1995) World Scientific, Singapore ISBN 981-02-2058-8~~
	* Volker Diekert, Yves Métivier, "[http://~~citeseer~~.~~ist~~.~~psu.edu~~/diekert97partial.html Partial Commutation and Traces]", In G. Rozenberg and A. Salomaa, editors, ''Handbook of Formal Languages'', Vol. '''3''', Beyond Words, pages 457–534. Springer-Verlag, Berlin, 1997.

	~~[[Category:Concurrency (computer science)]]~~
	~~[[Category:Semigroup theory]]~~
	~~[[Category:Formal languages]]~~
	~~[[Category:Free algebraic structures]~~]

en>John: Reverted edits by Sol1 (talk) to last version by Helpful Pixie Bot

2013-05-13T19:45:29Z

Reverted edits by Sol1 (talk) to last version by Helpful Pixie Bot

← Older revision		Revision as of 21:45, 13 May 2013
Line 1:		Line 1:
	~~Hello~~, ~~my title~~ is ~~Andrew~~ and ~~my wife doesn~~'~~t like~~ it ~~at all~~. ~~She works~~ as a ~~journey agent but soon she~~'~~ll be on her own~~. As a ~~lady what she really likes~~ is ~~fashion~~ and ~~she~~'~~s been doing~~ it for ~~quite~~ a ~~whilst~~. ~~For~~ a while ~~I've been~~ in ~~Mississippi but now I'm considering~~ other ~~options~~.<br><br>~~Also visit my blog post :: phone psychic~~ - [~~http:~~//~~myfusionprofits~~.~~com~~/~~groups~~/~~find~~-~~out~~-~~about~~-~~self~~-~~improvement~~-~~tips-here~~/ ~~Highly recommended Reading~~],		In [[mathematics]] and [[computer science]], a '''history monoid''' is a way of representing the histories of concurrently running computer [[process (computer science)\|processes]] as a collection of [[string (computer science)\|strings]], each string representing the individual history of a process. The history monoid provides a set of [[synchronization primitive]]s (such as [[lock (computer science)\|locks]], [[mutex]]es or [[thread join]]s) for providing rendezvous points between a set of independently executing processes or threads.

			History monoids occur in the theory of [[concurrent computation]], and provide a low-level mathematical foundation for [[process calculi]], such as CSP the language of [[communicating sequential processes]], or CCS, the [[calculus of communicating systems]]. History monoids were first presented by M.W. Shields.<ref>M.W. Shields "Concurrent Machines", ''Computer Journal'', (1985) '''28''' pp. 449–465.</ref>

			History monoids are isomorphic to [[trace monoid]]s (free partially commutative monoids) and to the [[monoid]] of [[dependency graph]]s. As such, they are [[free object]]s and are [[universal property\|universal]]. The history monoid is a type of semi-abelian [[categorical product]] in the [[category (mathematics)\|category]] of monoids.

			==Product monoids and projection==
			Let
			:<math>A=(\Sigma_1,\Sigma_2,\ldots,\Sigma_n)</math>

			denote an ''n''-tuple of [[alphabet (computer science)\|alphabets]] <math>\Sigma_k</math>. Let <math>P(A)</math> denote all possible combinations of finite-length strings from the alphabets:

			:<math>P(A)=\Sigma_1^* \times \Sigma_2^* \times \cdots \times \Sigma_n^*</math>

			(In more formal language, <math>P(A)</math> is the [[Cartesian product]] of the [[free monoid]]s of the <math>\Sigma_k</math>. The superscript star is the [[Kleene star]].) Composition in the product monoid is component-wise, so that, for

			:<math>\bold{u}=(u_1,u_2,\ldots,u_n) \, </math>

			and

			:<math>\bold{v}=(v_1,v_2,\ldots,v_n) \, </math>

			then

			:<math>\bold{uv}=(u_1v_1,u_2v_2,\ldots,u_nv_n) \, </math>

			for all <math>\bold{u}, \bold{v}</math> in <math>P(A)</math>. Define the union alphabet to be

			:<math>\Sigma=\Sigma_1 \cup \Sigma_2 \cup \cdots \cup \Sigma_n. \,</math>

			(The union here is the [[set union]], not the [[disjoint union]].) Given any string <math>w\in \Sigma^</math>, we can pick out just the letters in some <math>\Sigma_k^</math> using the corresponding [[string projection]] <math>\pi_k:\Sigma^\to\Sigma_k^</math>. A '''distribution''' <math>\pi:\Sigma^\to P(A)</math> is the mapping that operates on <math>w\in \Sigma^</math> with all of the <math>\pi_k</math>, separating it into components in each free monoid:

			:<math>\pi(w)\mapsto (\pi_1(w), \pi_2(w), \ldots , \pi_n(w)). \,</math>

			==Histories==
			For every <math>a\in\Sigma</math>, the tuple <math>\pi(a)</math> is called the '''elementary history''' of ''a''. It serves as an [[indicator function]] for the inclusion of a letter ''a'' in an alphabet <math>\Sigma_k</math>. That is,

			:<math>\pi(a)=(a_1,a_2,\ldots,a_n)</math>

			where

			:<math>a_i=\begin{cases}
			a \mbox{ if } a\in \Sigma_k \\
			\varepsilon \mbox { otherwise }.
			\end{cases}</math>

			Here, <math>\varepsilon</math> denotes the [[empty string]]. The '''history monoid''' <math>H(A)</math> is the [[free monoid]] generated by elementary histories. It is clearly a submonoid of the product monoid <math>P(A)</math>. The elements of <math>H(A)</math> are called '''global histories''', and the projections of a global history are called '''individual histories'''.

			==Connection to computer science==
			The use of the word ''history'' in this context, and the connection to concurrent computing, can be understood as follows. An individual history is a record of the sequence of [[state (computer science)\|states]] of a process (or [[thread (computer science)\|thread]] or [[Turing machine\|machine]]); the alphabet <math>\Sigma_k</math> is the set of states of the process.

			A letter that occurs in two or more alphabets serves as a [[synchronization primitive]] between the various individual histories. That is, if such a letter occurs in one individual history, it must also occur in another history, and serves to "tie" or "rendezvous" them together.

			Consider, for example, <math>\Sigma_1=\{a,b,c\}</math> and <math>\Sigma_2=\{a,d,e\}</math>. The union alphabet is of course <math>\Sigma=\{a,b,c,d,e\}</math>. The elementary histories are <math>(a,a)</math>, <math>(b,\varepsilon)</math>, <math>(c,\varepsilon)</math>, <math>(\varepsilon,d)</math> and <math>(\varepsilon,e)</math>. In this example, an individual history of the first process might be <math>bcbcc</math> while the individual history of the second machine might be <math>ddded</math>. Both of these individual histories are represented by the global history <math>bcbdddcced</math>, since the projection of this string onto the individual alphabets yields the individual histories. In the global history, the letter <math>b</math> can be considered to commute with the letters <math>d</math> and <math>e</math>, in that these can be rearranged without changing the individual histories. Such commutation is simply a statement that the first and second processes are running concurrently, and are unordered with respect to each other; they have not (yet) exchanged any messages or performed any synchronization.

			The letter <math>a</math> serves as a synchronization primitive, as its occurrence marks a spot in both the global and individual histories, that cannot be commuted across. Thus, while the letters <math>b</math> and <math>c</math> can be re-ordered past <math>d</math> and <math>e</math>, they cannot be reordered past <math>a</math>. Thus, the global history <math>bcdabe</math> and the global history <math>bdcaeb</math> both have as individual histories <math>bcab</math> and <math>dae</math>, indicating that the execution of <math>d</math> may happen before or after <math>c</math>. However, the letter <math>a</math> is synchronizing, so that <math>e</math> is guaranteed to happen after <math>c</math>, even though <math>e</math> is in a different [[process (computer science)\|process]] than <math>c</math>.

			==Properties==
			The history monoid is isomorphic to the [[trace monoid]], and as such, is a type of semi-abelian [[categorical product]] in the [[category (mathematics)\|category]] of monoids. In particular, the history monoid <math>H(\Sigma_1,\Sigma_2,\ldots,\Sigma_n)</math> is isomorphic to the trace monoid <math>\mathbb{M}(D)</math> with the [[dependency relation]] given by

			:<math>D=\left(\Sigma_1\times\Sigma_1\right)\cup
			\left(\Sigma_2\times\Sigma_2\right)\cup \cdots \cup
			\left(\Sigma_n\times\Sigma_n\right).</math>

			In simple terms, this is just the formal statement of the informal discussion given above: the letters in an alphabet <math>\Sigma_k</math> can be commutatively re-ordered past the letters in an alphabet <math>\Sigma_j</math>, unless they are letters that occur in both alphabets. Thus, traces are exactly global histories, and vice-versa.

			==Notes==
			<references/>

			==References==
			* Antoni Mazurkiewicz, "Introduction to Trace Theory", pp 3–41, in ''The Book of Traces'', V. Diekert, G. Rozenberg, eds. (1995) World Scientific, Singapore ISBN 981-02-2058-8
			* Volker Diekert, Yves Métivier, "[http://citeseer.ist.psu.edu/diekert97partial.html Partial Commutation and Traces]", In G. Rozenberg and A. Salomaa, editors, ''Handbook of Formal Languages'', Vol. '''3''', Beyond Words, pages 457–534. Springer-Verlag, Berlin, 1997.

			[[Category:Concurrency (computer science)]]
			[[Category:Semigroup theory]]
			[[Category:Formal languages]]
			[[Category:Free algebraic structures]]

en>Helpful Pixie Bot: ISBNs (Build KC)

2012-05-05T23:15:02Z

ISBNs (Build KC)

New page

Hello, my title is Andrew and my wife doesn't like it at all. She works as a journey agent but soon she'll be on her own. As a lady what she really likes is fashion and she's been doing it for quite a whilst. For a while I've been in Mississippi but now I'm considering other options.<br><br>Also visit my blog post :: phone psychic - [http://myfusionprofits.com/groups/find-out-about-self-improvement-tips-here/ Highly recommended Reading],