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
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.