[Clops-users] ambiguity of regular grammars

[Radu G. <rad...@gm...>]

I have implemented a toy version of the ambiguity check algorithm (in
ocaml). While doing so I realized that our algorithm is the *same* as
that of Even if we plug in the correct stopping condition C. I did not
implement the black/white nodes thing (so ambiguities *within* one
option aren't ignored). For automata with at most 2000 nodes and at
most 2000 edges the worst case is solved in <0.6s. That worst case
looks like [0]. The problem is here:
  https://www.spoj.pl/problems/AMBIG/
I'm not very happy with the tests: I think there must be some more
interesting cases than the ones I came up with. While writing the
tests I noticed that my worry about multiplying lengths of cycles was
misguided: It's never the case that more than two cycles interact!

The first solution submitted by someone else to that problem is in C++
and is about 8 times faster than my ocaml, so we can probably safely
assume that <0.6s can be made <0.1s.

I'd say it's fast enough for CLOPS. What do you think?

[0] http://tinyurl.com/ydctoju