摘要:

AbstractThis article ties together previously scattered research on discontinuous grammars—logic grammars in which non‐explicit sequences of symbols can be alluded to in the rules and sometimes repositioned by them. After an introduction, we define them formally, present their background, and provide intuitive insight into their use. Next, we examine several motivating arguments, from both formal and natural language processing viewpoints, and we discuss thestatic discontinuityfamily of these grammars, in which (a) the nonexplicit strings are not allowed to move and (b) linguistic constraints specifically designed to suit, in particular, Government and Binding theory can be defined modularly and statically in terms of node domination in parse trees and are enforced dynamically. Finally, we discuss implementation issues, related work, and extensi

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1989.tb00326.x

出版商:Blackwell Publishing Ltd    

年代:1989

数据来源: WILEY

摘要:

AbstractThis paper addresses the problem in inductive generalization of determining when a general hypothesis is supported by a particular instance. If we accept that, first, some facts do indeed support a general hypothesis and, second, that an instance that supports a hypothesis also supports all logical consequences of the hypothesis, then unintuitive and problematic results are immediately forthcoming. These assumptions lead, for example, to the conclusion that a blue Honda is confirming evidence for the hypothesis that ravens are black. This problem is variously known asthe paradoxes of confirmationorHempel's paradox. In this paper I develop a formal characterization of the problem. The assumption that whatever supports all classical consequences of the hypothesis is rejected. Rather, I argue that a weaker notion of consequence should be adopted for determining what consequences of a hypothesis are supported by the same evidence. An extant formal system for learning from examples is used to address these problems of evidential support, and it is shown that in this framework the problems do not arise.

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1989.tb00327.x

出版商:Blackwell Publishing Ltd    

年代:1989

数据来源: WILEY

摘要:

AbstractConstraint satisfaction problems are ubiquitous in artificial intelligence and many algorithms have been developed for their solution. This paper provides a unified survey of some of these, in terms of three classes: (i) tree search, (ii) arc consistency (AC), and (iii) hybrid tree search/arc consistency algorithms. It is shown that several important algorithms, when slightly rearranged, are of the latter hybrid form, but with arc consistency components that do not necessarily achieve full arc consistency at the tree nodes. Accordingly, we define several newpartialAC procedures, AC1/5, AC1/4, AC1/3, and AC½, analogous to the well‐knownfullAC algorithms which Mackworth has called AC1, AC2, and AC3. The fractional suffixes on our AC algorithms are roughly proportional to the degree of partial arc consistency they achieve. Unlike traditional versions, our AC algorithms (full and partial) are presented in a parameterized form to allow them to be embedded efficiently at the nodes of a tree search process. Algorithm complexities are compared empirically, using then‐queens problem and a new version called confusedn‐queens. Gaschnig's Backmarking (a tree search algorithm) and Haralick's Forward Checking (a hybrid algorithm) are found to be the most efficient. For the hybrid algorithms, we find that it pays to do little arc consistency processing at the nodes, incurring more nodes, but sufficiently reducing the work per node so as to obtain less work over the whole tree. The unified view taken here suggests several new algorithms. Preliminary results show one of these to be the best algorithm

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1989.tb00328.x

出版商:Blackwell Publishing Ltd    

年代:1989

数据来源: WILEY

摘要:

AbstractThis paper develops and explores a first‐order theory of time that appears useful as an underlying framework for a wide range of practical applications in artificial intelligence (AI). In particular, it presents a concise, formal axiomatization of “interval‐based” time as described by Allen and then explores the relationship between interval‐based and point‐based temporal theories in detail. This analysis should be useful to both theoretical and practical work in AI that involves the representation of time, since it shows what distinctions are actually substantive and what arise merely from formalisms being notational variants of

ISSN:0824-7935    

DOI:10.1111/j.1467-8640.1989.tb00329.x

出版商:Blackwell Publishing Ltd    

年代:1989

数据来源: WILEY