The common order-theoretic structure of version spaces and ATMSs
Artificial IntelligencePublished 1 September 1997Open access
Carl A. Gunter, Teow-Hin Ngair, Devika Subramanian
Citations17
SJR quartileQ1
SJR score1.84
SNIP3.30
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We demonstrate how order-theoretic abstractions can be useful in identifying, formalizing, and exploiting relationships between seemingly dissimilar AI algorithms that perform computations on partially-ordered sets. In particular, we show how the order-theoretic concept of an anti-chain can be used to provide an efficient representation for such sets when they satisfy certain special properties. We use anti-chains to identify and analyze the basic operations and representation optimizations in the version space learning algorithm and the assumption-based truth maintenance system (ATMS). Our analysis allows us to (1) extend the known theory of admissibility of concept spaces for incremental version space merging, and (2) develop new, simpler label-update algorithms for ATMSs with DNF assumption formulas.
Keywords
Computer Science
Cambridge University Press eBooksIntroduction to Lattices and Order
4,924 Citations2002Brian Davey, H. A. Priestley
Artificial IntelligenceAn assumption-based TMS
1,745 Citations1986Johan de Kleer
A new view of problem solving motivated by a new kind of truth maintenance system based on manipulating assumption sets is presented, which is possible to work effectively and efficiently with inconsistent information, context switching is free, and most backtracking is avoided.
Journal of Symbolic LogicSteven Vickers. Topology via logic. Cambridge tracts in theoretical computer science, no. 5. Cambridge University Press, Cambridge etc. 1989, xiii + 200 pp.
490 Citations1991Steven Vickers
Readings in Machine Learning
425 Citations1991Jude Shavlik, Thomas E. Deitterich +1 more
Readings in Machine Learning collects the best of the published machine learning literature, including papers that address a wide range of learning tasks, and that introduce a variety of techniques for giving machines the ability to learn.
Choice Reviews OnlineSemantics of programming languages: structures and techniques
422 Citations1993
Semantics of Programming Languages exposes the basic motivations and philosophy underlying the applications of semantic techniques in computer science, and introduces the mathematical theory of programming languages with an emphasis on higher-order functions and type systems.
Building problem solvers
361 Citations1993Kenneth D. Forbus, Johan de Kleer
Although Building Problem Solvers is designed primarily as a text for advanced AI classes or AI programming classes, it can be used by researchers in universities and industrial laboratories who want to apply these techniques in their work, and by programmers whowant to incorporate these ideas in their applications.
Foundations of Computing
241 Citations1997Jozef Gruska
Artificial IntelligenceExtending the ATMS
222 Citations1986Johan de Kleer
This paper shows how the basic ATMS is extended to handle defaults and disjunctions of assumptions, which are used to encode disjunction of nodes, nonmonotonic justifications, normal defaults, nonnormal defaults, and arbitrary propositional formulas.
eCommons (Cornell University)On some central problems in computational complexity.
169 Citations1975Janoš Šimon
This thesis examines some of the central problems in the theory of computational complexity, like the trade-offs between time and memory, the power of nondeterminism and parallelism, and the speed gained by adding new operations to random access machines.
Proceedings of the IREComputers and Automata
119 Citations1953Claude E. Shannon
Some theoretical questions and developments are discussed, such as a comparison of computers and the brain, Turing's formulation of computing machines and von Neumann's models of self-reproducing machines.
Theoretical Computer ScienceThe largest cartesian closed category of domains
101 Citations1983Michael B. Smyth
The main result of this paper provides a necessary and sufficient condition that the function space of a domain D be again a domain, enabling us to conclude that SFP is the largest category of domains that is closed under the constructions of interest in semantics.
Kluwer international series in engineering and computer scienceIncremental Version-Space Merging: A General Framework for Concept Learning
73 Citations1990Haym Hirsh
This work focuses on version spaces and the Candidate-Elimination Algorithm, which combines Empirical and Analytical Learning with Bounded Inconsistency to solve the problem of intractable Domains in Version Spaces.
Artificial IntelligenceThe description identification problem
33 Citations1991Chris Mellish
An algorithm for solving the more general description identification problem, which extends the version space strategy of Mitchell, is presented and can be regarded as a further formalisation and development of the work of Mitchell on version space representation and the Work of Young et al. and Plotkin on description spaces.
Foundations of Computing
18 Citations2021Gerard O’Regan
ScholarlyCommons (University of Pennsylvania)Convex spaces as an order theoretic basis for problem-solving
15 Citations1992Teow-Hin Ngair
This thesis advocates that ordered structures play an important role in many problem domains and focuses on the study of an ordered structure called a convex space, which helps answer some of the important questions concerning problem solving tasks in the fields of Artificial Intelligence and Database Systems.
Lecture notes in computer scienceOn logical foundations of the ATMS
7 Citations2006Yasushi Fujiwara, Shinichi Honiden
The declarative semantics of the ATMS is exhibited in terms of propositional Horn logic and the correctness of its label update algorithm is proved with respect to the semantics.