Publikace na Matematicko-fyzikální fakulta |
2007
Abstrakt
Říkáme, že nedeterministický restartovací automat M (silně) zachovává správnost, pokud, pro každý cyklus , slovo v patří do úplného jazyka L C (M) přijímaného pomocí M, pokud tam patří u. Zde, abychom rozlišili restartovací automaty zachovávající správnost od automatů bez této vlastnosti, zavádíme dva způsoby postupné relaxace zachovávání správnosti. Tyto relaxace vedou k nekonečné dvou dimensionální hierarchii tříd jazyků s rozpoznáváním rozhodnutelném v polynomiálním čase.