Regular intersection emptiness of graph problems: finding a needle in a haystack of graphs with the help of automata
The Int_reg-problem of a combinatorial problem P asks, given a nondeterministic automaton
M as input, whether the language L (M) accepted by M contains any positive instance of the
problem P. We consider the Int_reg-problem for a number of different graph problems and
give general criteria that give decision procedures for these Int_reg-problems. To achieve
this goal, we consider a natural graph encoding so that the language of all graph encodings
is regular. Then, we draw the connection between classical pumping-and interchange …
M as input, whether the language L (M) accepted by M contains any positive instance of the
problem P. We consider the Int_reg-problem for a number of different graph problems and
give general criteria that give decision procedures for these Int_reg-problems. To achieve
this goal, we consider a natural graph encoding so that the language of all graph encodings
is regular. Then, we draw the connection between classical pumping-and interchange …
以上显示的是最相近的搜索结果。 查看全部搜索结果