Towards a complete classification of tractability in point algebras for nonlinear time

• Efficient reasoning about temporal constraints over nonlinear time models is vital in numerous application areas, such as planning, distributed systems and cooperating agents. We identify all tractable subclasses of the point algebra for partially-ordered time and examine one large, nontrivial tractable subclass of the point algebra for branching time.

Nyckelord

constraint programming

search problems

tractability

heuristics

routing problems

resource allocation

scheduling

satisfiability problems

constraint handling

constraint satisfaction problems

TECHNOLOGY

TEKNIKVETENSKAP

Publikations- och innehållstyp

ref (ämneskategori)

kap (ämneskategori)