tag:blogger.com,1999:blog-11295132.post4382746632400173667..comments2014-06-25T07:05:59.204-07:00Comments on A Neighborhood of Infinity: Fast incremental regular expression matching with monoidsDan Piponihttps://plus.google.com/107913314994758123748noreply@blogger.comBlogger10125tag:blogger.com,1999:blog-11295132.post-13068918864259123152014-01-11T08:56:05.450-08:002014-01-11T08:56:05.450-08:00"We can thing of the inputs " typo"We can thing of the inputs " typoMichael Rogerhttp://www.blogger.com/profile/08729150476888743293noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-68537601449344019712012-12-25T05:56:02.301-08:002012-12-25T05:56:02.301-08:00Interesting results.
Two things:
1. Can you do s...Interesting results.<br /><br />Two things:<br /><br />1. Can you do some benchmarks against the Rope implementation? - http://jkff.info/articles/ire<br /><br />2. You mention Red/Black trees for C++ at the end there. Wouldn't that adversely affect the complexities? - Why wouldn't you use Finger Trees in C++? (there is a Masters theses floating around on the interwebs with an implementation of the 2-3 tree variant)Alec Taylorhttp://www.blogger.com/profile/02267100414793689299noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-53539171292250710872012-12-18T09:54:07.769-08:002012-12-18T09:54:07.769-08:00Dan, I just published an article that expands on t...Dan, I just published an article that expands on the ideas from this blogpost and builds a Java library for incremental matching of multiple regular expressions: http://jkff.info/articles/ire (it was actually published in the Russian functional programming journal http://fprog.ru/ but I recently got around to finish the translation)jkffhttp://www.blogger.com/profile/16923431648214439769noreply@blogger.comtag:blogger.com,1999:blog-11295132.post-50978256649680987992009-01-29T15:55:00.000-08:002009-01-29T15:55:00.000-08:00Dan,i haven't read the fingertree papers, yet. Is ...Dan,<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 ...Anonymous, 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 ...apflemus: 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 ...Minor 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,Fingertrees basically cache homomorphisms...apfelmus,<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. :-)In other words, determini...Great 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 & 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. :-)In other words, determini...Great 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 & 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