Monoid machines: a O(log n) parser for regular languages (2006) [pdf]

Re:Monoid machines: a O(log n) parser for regular languages ... by mac01021 on Thursday July 12, 2018 @07:54PM (#17519574)

Interesting. One thing they leave implicit is the amount of work that parsing requires.

The result is that you can parse in time O(log n) if you use O(n) processors, so parsing requires O(nlogn) work. (This is probably to be expected.) I think this means that, if you have o(n) strings to parse, you're better off with the good old DFA solution which uses O(n) work and parsing the different strings in parallel.

[ Parent | on HN ]

Re:Monoid machines: a O(log n) parser for regular languages ... by gue5t on Thursday July 12, 2018 @08:41PM (#17519748)

Yes, given no context one assumes serial computation, where work and depth are identical. An O(log n)-work parser would be astounding, because it's impossible--it would have to ignore effectively all of the input. This isn't clickbait because it's a real article and a good technique, but it's definitely exaggerating the surprise factor with misleading phrasing.

[ Parent | on HN ]