You are viewing a javascript disabled version of the site. Please enable Javascript for this site to function properly.
Go to headerGo to navigationGo to searchGo to contentsGo to footer
In content section. Select this link to jump to navigation

Satisfiability of Inequalities in a Poset

Article type: Research Article

Authors: Pratt, Vaughan | Tiuryn, Jerzy

Affiliations: Computer Science Department, Stanford University, Stanford, CA 94305. pratt@cs.stanford.edu | Institute of Informatics, Warsaw University, Banacha 2, 02-097 Warsaw, POLAND. tiuryn@mimuw.edu.pl

Note: [] The first author is supported by ONR under grant number N00014-92-J-1974.

Note: [] The second author is partly supported by NSF Grants CCR-9417382, CCR-9304144, and by Polish KBN Grant 2 P301 031 06.

DOI: 10.3233/FI-1996-281211

Journal: Fundamenta Informaticae, vol. 28, no. 1-2, pp. 165-182, 1996

Published: 1996
Get PDF

Abstract

We consider tractable and intractable cases of the satisfiability problem for conjunctions of inequalities between variables and constants in a fixed finite poset. We show that crowns are intractable. We study members and closure properties of the class of tractable posets. We define a feasible poset to be one whose potential obstacles to satisfiability are representable by a certain formula of the first-order extended by the least fixed operator. For bipartite posets we give a complete classification of hard posets and feasible ones.

Show more