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 m ↝ n 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.
13 comments:
Hi rgrig :).
Is this problem in some online judge to test my possible solution?
Thanks.
I was planning to add it to SPOJ. I'll try to do it today now that you asked.
It's problem AMBIG. I think the tests could be better. Let me know if you have any interesting cases that I should add.
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?
That's one the tests. :)
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.
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.
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.
i tried to submit solution spoj.
i am getting wrong answer. is there any corner cases to consider?
Thanks
solved thanks
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.