We study the Knights and Knaves problem, and find that for a proper treatment via theorem-proving, an interaction with natural language processing research is helpful. In particular, we discuss Ohlbach's claim tha...
详细信息
We study the Knights and Knaves problem, and find that for a proper treatment via theorem-proving, an interaction with natural language processing research is helpful. In particular, we discuss Ohlbach's claim that first-order logic is not well suited to handling this problem. Then we provide an interpretation of the problem using indexicals, axiomatize it, and prove the desired result. We conclude by suggesting a broader context for dealing with 'self-utterances' in automatic theorem-proving.
A new method termed population analysis is presented for approximating the distribution of node occupancies in hierarchical data structures which store a variable number of geometric data items per node. The basic ide...
详细信息
We have shown that, in some sense, computers can be taught how to learn how to learn. The mathematical result constructed sequences of functions that were easy to learn, provided they were learned one at a time in a s...
详细信息
MIRRORS/II is a software system for developing connectionist models. This paper discusses the unique features of MIRRORS/II: application independence, specification language, multiple target languages, extensibility, ...
详细信息
The visibility graph of a set of nonintersecting polygonal obstacles in the plane is an undirected graph whose vertices are the vertices of the obstacles and whose edges are pairs of vertices (u, v) such that the open...
详细信息
The visibility graph of a set of nonintersecting polygonal obstacles in the plane is an undirected graph whose vertices are the vertices of the obstacles and whose edges are pairs of vertices (u, v) such that the open line segment between u and v does not intersect any of the obstacles. The visibility graph is an important combinatorial structure in computational geometry and is used in applications such as solving visibility problems and computing shortest paths. An algorithm is presented that computes the visibility graph of s set of obstacles in time O(E + n log n), where E is the number of edges in the visibility graph and n is the total number of vertices in all the obstacles.
Let A be a set and k ∈ N be such that we wish to know the answers to x 1 ∈ A?, χ 2 ∈ A?, …, X k ∈ A? for various k-tuples (x 1 ,x 2 , …,X k )· If this problem requires k queries to A in order to be solv...
Let A be a set and k ∈ N be such that we wish to know the answers to x 1 ∈ A?, χ 2 ∈ A?, …, X k ∈ A? for various k-tuples (x 1 ,x 2 , …,X k )· If this problem requires k queries to A in order to be solved in polynomial time then A is called polynomial terse or pterse. We show the existence of both arbitrarily complex pterse and non-pterse sets; and that P=NP iff every NP-complete set is pterse. We also show connections with p-immunity, polynomial separability, p-generic sets, and the boolean hierarchy. Our techniques allow us to prove that Unique Satisfiability (USAT) is, in some sense, "close" to Satisfiability. In particular, we show that USAT is coNP-hard.
A common structure arising in computational geometry is the subdivision of a plane defined by the faces of a straight line planar graph. We consider a natural generalization of this structure on a polyhedral surface. ...
详细信息
We present a verified sliding window protocol which uses modulo-N sequence numbers to achieve reliable flow-controlled data transfer between a source and a destination. Communication channels are assumed to lose, dupl...
详细信息
暂无评论