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.


Jorge Bernadas said...

Hi rgrig :).

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


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.

Jorge Bernadas said...

Thanks for uploading the problem, I managed to solve it :).

About this case:

2 2
0 1 0
0 1 0

The answer is YES, right?

rgrig said...

That's one the tests. :)

Jorge Bernadas said...

I supposed that. What about this one?

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.

Jorge Bernadas said...

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

You are welcome.

Deximat said...

What is the name of algorithm that solves this?

Radu Grigore said...

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?

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?

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.