Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Free monoid
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==Morphisms== A [[monoid morphism]] ''f'' from a free monoid ''B''<sup>∗</sup> to a monoid ''M'' is a map such that ''f''(''xy'') = ''f''(''x'')⋅''f''(''y'') for words ''x'',''y'' and ''f''(ε) = ι, where ε and ι denote the identity elements of ''B''<sup>∗</sup> and ''M'', respectively. The morphism ''f'' is determined by its values on the letters of ''B'' and conversely any map from ''B'' to ''M'' extends to a morphism. A morphism is '''non-erasing'''<ref name=Lot7>{{harvtxt|Lothaire|1997|p=7}}</ref> or '''continuous'''<ref name=Sak25>{{harvtxt|Sakarovitch|2009|p=25}}</ref> if no letter of ''B'' maps to ι and '''trivial''' if every letter of ''B'' maps to ι.<ref name=Lot164>{{harvtxt|Lothaire|1997|p=164}}</ref> A morphism ''f'' from a free monoid ''B''<sup>∗</sup> to a free monoid ''A''<sup>∗</sup> is '''total''' if every letter of ''A'' occurs in some word in the image of ''f''; '''cyclic'''<ref name=Lot164/> or '''periodic'''<ref name=Sal77>{{harvtxt|Salomaa|1981|p=77}}</ref> if the image of ''f'' is contained in {''w''}<sup>∗</sup> for some word ''w'' of ''A''<sup>∗</sup>. A morphism ''f'' is '''''k''-uniform''' if the length |''f''(''a'')| is constant and equal to ''k'' for all ''a'' in ''A''.<ref name=ApCoW522>{{harvtxt|Lothaire|2005|p=522}}</ref><ref name=BR103>{{cite book | last1=Berstel | first1=Jean | last2=Reutenauer | first2=Christophe | title=Noncommutative rational series with applications | series=Encyclopedia of Mathematics and Its Applications | volume=137 | location=Cambridge | publisher=[[Cambridge University Press]] | year=2011 | isbn=978-0-521-19022-0 | zbl=1250.68007 | page=103 }}</ref> A 1-uniform morphism is '''strictly alphabetic'''<ref name=Sak25/> or a '''coding'''.<ref name=AS9>{{harvtxt|Allouche|Shallit|2003|p=9}}</ref> A morphism ''f'' from a free monoid ''B''<sup>∗</sup> to a free monoid ''A''<sup>∗</sup> is '''simplifiable''' if there is an alphabet ''C'' of cardinality less than that of ''B'' such the morphism ''f'' factors through ''C''<sup>∗</sup>, that is, it is the composition of a morphism from ''B''<sup>∗</sup> to ''C''<sup>∗</sup> and a morphism from that to ''A''<sup>∗</sup>; otherwise ''f'' is '''elementary'''. The morphism ''f'' is called a '''code''' if the image of the alphabet ''B'' under ''f'' is a code. Every elementary morphism is a code.<ref name=Sal72>{{harvtxt|Salomaa|1981|p=72}}</ref> ===Test sets=== For ''L'' a subset of ''B''<sup>∗</sup>, a finite subset ''T'' of ''L'' is a ''test set'' for ''L'' if morphisms ''f'' and ''g'' on ''B''<sup>∗</sup> agree on ''L'' if and only if they agree on ''T''. The '''Ehrenfeucht conjecture''' is that any subset ''L'' has a test set:<ref name=Lot1789>{{harvtxt|Lothaire|1997|pp=178–179}}</ref> it has been proved<ref name=LotII451>{{harvtxt|Lothaire|2011|p=451}}</ref> independently by Albert and Lawrence; McNaughton; and Guba. The proofs rely on [[Hilbert's basis theorem]].<ref>{{cite journal | first=A. | last=Salomaa | authorlink=Arto Salomaa | title=The Ehrenfeucht conjecture: A proof for language theorists | journal=Bulletin of the EATCS | number=27 | date=October 1985 | pages=71–82 }}</ref> ===Map and fold=== {{unreferenced section|date=February 2015}} The computational embodiment of a monoid morphism is a [[Map (higher-order function)|map]] followed by a [[Fold (higher-order function)|fold]]. In this setting, the free monoid on a set ''A'' corresponds to [[List (computing)|lists]] of elements from ''A'' with concatenation as the binary operation. A monoid homomorphism from the free monoid to any other monoid (''M'',•) is a function ''f'' such that * ''f''(''x''<sub>1</sub>...''x''<sub>''n''</sub>) = ''f''(''x''<sub>1</sub>) • ... • ''f''(''x''<sub>''n''</sub>) * ''f''() = ''e'' where ''e'' is the identity on ''M''. Computationally, every such homomorphism corresponds to a [[Map (higher-order function)|map]] operation applying ''f'' to all the elements of a list, followed by a [[Fold (higher-order function)|fold]] operation which combines the results using the binary operator •. This [[squiggol|computational paradigm]] (which can be generalized to non-associative binary operators) has inspired the [[MapReduce]] software framework.{{citation needed|date=February 2015}}
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)