Složitost problémů splnitelnosti časových omezení

Abstrakt

Jazyk časových omezení je množina relací, která má definici v logice prvního řádu nad hustým lineárním uspořádáním racionálních čísel. V práci prezentujeme úplnou klasifikaci výpočetní složitosti problémů splnitelnosti pro jazyky časových omezení.

Klíčová slova

• Complexity
• Temporal
• Constraint
• Satisfaction
• Problems