tag:blogger.com,1999:blog-11295132.post4382746632400173667..comments2010-05-15T11:49:20.012-07:00sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-11295132.post-50978256649680987992009-01-29T15:55:00.000-08:002009-01-29T15:55:00.000-08:00Dan,<BR/><BR/>i haven't read the fingertree papers, yet. Is there an account of how the finger tree representation/analysis relates to <A HREF="http://www.springerlink.com/content/w47217708184013u/" REL="nofollow">quantaloids</A>?<BR/><BR/>Best wishes,<BR/><BR/>--gregleithaushttp://www.blogger.com/profile/01069099703796397027noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-38249259332871226642009-01-27T20:14:00.000-08:002009-01-27T20:14:00.000-08:00Anonymous, nope. I think you meant + not *. It is needed in order to handle cases where you have more than two zeros preceding the 7. <BR/><BR/>It lets you match:<BR/><BR/>/.*(.*000*7.*).*/?<BR/><BR/>but that matches the same inputs as<BR/><BR/>/.*(.*007.*).*/?<BR/><BR/>because <BR/><BR/>.*000* and .*00 match exactly the same inputs. <BR/><BR/>If the 0* in .*000* matched any characters then we know that the .* could have munched more characters. <BR/><BR/>If the .* in .*00 matches something that ends in a run of 0's then .*000* could match all but the first two in the 0* portion.Edward Kmetthttp://www.blogger.com/profile/16144424873202502715noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-62400702390092978452009-01-26T12:59:00.000-08:002009-01-26T12:59:00.000-08:00apflemus: I don't suppose you remember how it can be used to minimize FSAs?Aaron Denneyhttp://www.blogger.com/profile/15613957348593645695noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-73271267486367669092009-01-26T05:36:00.000-08:002009-01-26T05:36:00.000-08:00Minor nitpick (and I could be wrong): doesn't the self loop of the 3rd node of your fsm allow it to actually match /.*(.*00*7.*).*/?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-17514463657025219792009-01-25T07:22:00.000-08:002009-01-25T07:22:00.000-08:00apfelmus,<BR/><BR/>Fingertrees basically cache homomorphisms from the free monoid.<BR/><BR/>There's an extra twist you can squeeze out of this formalism. You can label the transitions of the automaton with output values that live in a monoid. Then you can do things like counting and minimisation while matching - eg. to count the number of lexems, or find the longest one, or find the longest string between a certain pair and so on.sigfpehttp://www.blogger.com/profile/08096190433222340957noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-82607187900872752022009-01-25T01:43:00.001-08:002009-01-25T01:43:00.001-08:00Great post, as usual. :-)<BR/><BR/>In other words, deterministic finite state automata and thus regular expressions are actually monoid morphisms from the free monoid over the alphabet to a finite monoid, namely the monoid of endomorphisms on the states.<BR/><BR/>I finally remember this connection from a past automata &amp; languages lesson. For instance, the converse is true as well, every homomorphism to a finite monoid gives rise to a finite state automaton. (Construction: take the monoid itself as state space, every element corresponds to an endomorphism via left multiplication). I think this can and is used to minimize finite state automata.apfelmushttp://apfelmus.nfshost.comnoreply@blogger.comtag:blogger.com,1999:blog-11295132.post-25336271135520686292009-01-25T01:42:00.000-08:002009-01-25T01:42:00.000-08:00Great post, as usual. :-)<BR/><BR/>In other words, deterministic finite state automata and thus regular expressions are actually monoid morphisms from the free monoid over the alphabet to a finite monoid, namely the monoid of endomorphisms on the states.<BR/><BR/>I finally remember this connection from a past automata &amp; languages lesson. For instance, the converse is true as well, every homomorphism to a finite monoid gives rise to a finite state automaton. (Construction: take the monoid itself as state space, every element corresponds to an endomorphism via left multiplication). I think this can and is used to minimize finite state automata.apfelmushttp://apfelmus.nfshost.comnoreply@blogger.com