Authors
Dariusz Kalocinski, University of Warsaw, Poland
Abstract
Following Barwise, we consider examples of natural language sentences that seem to express that there is an embedding of one partial order into the other. We prove NP-completeness of two versions of partial orders embedding problem. We show that the task of computing the truth value of such sentences in finite models is NP-complete.
Keywords
NP-completeness, partial order, embedding, natural language, computational semantics