## 28 September 2009

### Ambiguity in CLOPS

A problem we hit while working on CLOPS. We know a good solution but it makes a nice puzzle.

Problem. A digraph has letters on edges, so there is a word corresponding to each walk. Given two nodes m and n, are there two distinct walks mn that have the same corresponding word?

Examples. We are looking at walks from blue to red.
In the graph

there are no two distinct walks with the same word.

If the graph

has the letter x on all edges then there are two distinct walks corresponding to the word xxxxxxxxxxxxxxxxx (length 17).

Comment. This problem amounts to finding whether a CLOPS input file, which is a regular grammar for what can go on the command line of a program, is ambiguous.

Hi rgrig :).

Is this problem in some online judge to test my possible solution?

Thanks.

rgrig said...

I was planning to add it to SPOJ. I'll try to do it today now that you asked.

rgrig said...

It's problem AMBIG. I think the tests could be better. Let me know if you have any interesting cases that I should add.

2 2
0 1 0
0 1 0

rgrig said...

That's one the tests. :)

2 3
0 1 0
1 0 1
1 0 1

I think the answer should be YES.

rgrig said...

If you meant "3 2" (3 edges, 2 nodes) instead of "2 3" then I agree. I added it as a test. Thanks.

Yes, I meant that, 3 edges, 2 nodes.

You are welcome.

Deximat said...

What is the name of algorithm that solves this?
Thanks.

It's a slightly modified version of automata intersection.
The problem appears in a research paper from 1965:
S Even, On Information Lossless Automata of Finite Order.

denyl said...

i tried to submit solution spoj.
i am getting wrong answer. is there any corner cases to consider?
Thanks

denyl said...

solved thanks

akshay kumar said...

i was solving the problem on spoj,it gives wrong answer in 16th-17th case,any corner case to consider?
here is my solution http://ideone.com/084uqo
any place where i can learn the algo to check ambiguity,like in this problem?