Rozhodování vlastností prvního řádu pro řídké grafy

Publikace na Matematicko-fyzikální fakulta |

2010

Ukážeme, že každou vlastnost popsatelnou formulí v logice prvního řádu lze rozhodovat v lineárním čase pro grafy s omezenou expanzí.