OpenRaiser/Intern-Atlas huggingface dataset:
Extending the Stable Model Semantics with More Expressive Rules
Venue: arXiv cs.LO 1999
Year: 1999

The rules associated with propositional logic programs and the stable model semantics are not expressive enough to let one write concise programs. This problem is alleviated by introducing some new types of propositional rules. Together with a decision procedure that has been used as a base for an efficient implementation, the new rules supplant the standard ones in practical applications of the stable model semantics.
Computational Geometry Column 36
Venue: arXiv cs.CG 1999
Year: 1999

Two results in "computational origami" are illustrated.
An Introduction to Collective Intelligence
Venue: arXiv cs.LG 1999
Year: 1999

This paper surveys the emerging science of how to design a ``COllective INtelligence'' (COIN). A COIN is a large multi-agent system where: (i) There is little to no centralized communication or control; and (ii) There is a provided world utility function that rates the possible histories of the full system. In particular, we are interested in COINs in which each agent runs a reinforcement learning (RL) algorithm. Rather than use a conventional modeling approach (e.g., model the system dynamics, and hand-tune agents to cooperate), we aim to solve the COIN design problem implicitly, via the ``adaptive'' character of the RL algorithms of each of the agents. This approach introduces an entirely new, profound design problem: Assuming the RL algorithms are able to achieve high rewards, what reward functions for the individual agents will, when pursued by those agents, result in high world utility? In other words, what reward functions will best ensure that we do not have phenomena like the tragedy of the commons, Braess's paradox, or the liquidity trap? Although still very young, research specifically concentrating on the COIN design problem has already resulted in successes in artificial domains, in particular in packet-routing, the leader-follower problem, and in variants of Arthur's El Farol bar problem. It is expected that as it matures and draws upon other disciplines related to COINs, this research will greatly expand the range of tasks addressable by human engineers. Moreover, in addition to drawing on them, such a fully developed scie nce of COIN design may provide much insight into other already established scientific fields, such as economics, game theory, and population biology.
Quadrilateral Meshing by Circle Packing
Venue: arXiv cs.CG 1999
Year: 1999

We use circle-packing methods to generate quadrilateral meshes for polygonal domains, with guaranteed bounds both on the quality and the number of elements. We show that these methods can generate meshes of several types: (1) the elements form the cells of a Voronoi diagram, (2) all elements have two opposite right angles, (3) all elements are kites, or (4) all angles are at most 120 degrees. In each case the total number of elements is O(n), where n is the number of input vertices.
Convex Tours of Bounded Curvature
Venue: arXiv cs.CG 1999
Year: 1999

We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m vertices, containing an obstacle in a form of a simple polygon with $n$ vertices. We present an O(m+n) time algorithm finding the path, going around the obstacle, whose curvature is the smallest possible.
Computing largest circles separating two sets of segments
Venue: arXiv cs.CG 1999
Year: 1999

A circle $C$ separates two planar sets if it encloses one of the sets and its open interior disk does not meet the other set. A separating circle is a largest one if it cannot be locally increased while still separating the two given sets. An Theta(n log n) optimal algorithm is proposed to find all largest circles separating two given sets of line segments when line segments are allowed to meet only at their endpoints. In the general case, when line segments may intersect $Ω(n^2)$ times, our algorithm can be adapted to work in O(n alpha(n) log n) time and O(n α(n)) space, where alpha(n) represents the extremely slowly growing inverse of the Ackermann function.
Locked and Unlocked Polygonal Chains in 3D
Venue: arXiv cs.CG 1999
Year: 1999

In this paper, we study movements of simple polygonal chains in 3D. We say that an open, simple polygonal chain can be straightened if it can be continuously reconfigured to a straight sequence of segments in such a manner that both the length of each link and the simplicity of the chain are maintained throughout the movement. The analogous concept for closed chains is convexification: reconfiguration to a planar convex polygon. Chains that cannot be straightened or convexified are called locked. While there are open chains in 3D that are locked, we show that if an open chain has a simple orthogonal projection onto some plane, it can be straightened. For closed chains, we show that there are unknotted but locked closed chains, and we provide an algorithm for convexifying a planar simple polygon in 3D. All our algorithms require only O(n) basic ``moves'' and run in linear time.
A statistical model for word discovery in child directed speech
Venue: arXiv cs.CL 1999
Year: 1999

A statistical model for segmentation and word discovery in child directed speech is presented. An incremental unsupervised learning algorithm to infer word boundaries based on this model is described and results of empirical tests showing that the algorithm is competitive with other models that have been used for similar tasks are also presented.
Two-way finite automata with quantum and classical states
Venue: arXiv cs.CC 1999
Year: 1999

We introduce 2-way finite automata with quantum and classical states (2qcfa's). This is a variant on the 2-way quantum finite automata (2qfa) model which may be simpler to implement than unrestricted 2qfa's; the internal state of a 2qcfa may include a quantum part that may be in a (mixed) quantum state, but the tape head position is required to be classical. We show two languages for which 2qcfa's are better than classical 2-way automata. First, 2qcfa's can recognize palindromes, a language that cannot be recognized by 2-way deterministic or probabilistic finite automata. Second, in polynomial time 2qcfa's can recognize {a^n b^n | n>=0}, a language that can be recognized classically by a 2-way probabilistic automaton but only in exponential time.
The Sources of Certainty in Computation and Formal Systems
Venue: arXiv cs.OH 1999
Year: 1999

In his Discourse on the Method of Rightly Conducting the Reason, and Seeking Truth in the Sciences, Rene Descartes sought ``clear and certain knowledge of all that is useful in life.'' Almost three centuries later, in ``The foundations of mathematics,'' David Hilbert tried to ``recast mathematical definitions and inferences in such a way that they are unshakable.'' Hilbert's program relied explicitly on formal systems (equivalently, computational systems) to provide certainty in mathematics. The concepts of computation and formal system were not defined in his time, but Descartes' method may be understood as seeking certainty in essentially the same way. In this article, I explain formal systems as concrete artifacts, and investigate the way in which they provide a high level of certainty---arguably the highest level achievable by rational discourse. The rich understanding of formal systems achieved by mathematical logic and computer science in this century illuminates the nature of programs, such as Descartes' and Hilbert's, that seek certainty through rigorous analysis.
Scalability Terminology: Farms, Clones, Partitions, Packs, RACS and RAPS
Venue: arXiv cs.AR 1999
Year: 1999

Defines a vocabulary for scaleable systems: Geoplexes, Farms, Clones, RACS, RAPS, clones, partitions, and packs and dicusses the design tradeoffs of using clones, partitons, and packs.
Adaptivity in Agent-Based Routing for Data Networks
Venue: arXiv cs.MA 1999
Year: 1999

Adaptivity, both of the individual agents and of the interaction structure among the agents, seems indispensable for scaling up multi-agent systems (MAS's) in noisy environments. One important consideration in designing adaptive agents is choosing their action spaces to be as amenable as possible to machine learning techniques, especially to reinforcement learning (RL) techniques. One important way to have the interaction structure connecting agents itself be adaptive is to have the intentions and/or actions of the agents be in the input spaces of the other agents, much as in Stackelberg games. We consider both kinds of adaptivity in the design of a MAS to control network packet routing. We demonstrate on the OPNET event-driven network simulator the perhaps surprising fact that simply changing the action space of the agents to be better suited to RL can result in very large improvements in their potential performance: at their best settings, our learning-amenable router agents achieve throughputs up to three and one half times better than that of the standard Bellman-Ford routing algorithm, even when the Bellman-Ford protocol traffic is maintained. We then demonstrate that much of that potential improvement can be realized by having the agents learn their settings when the agent interaction structure is itself adaptive.
Von Neumann Quantum Logic vs. Classical von Neumann Architecture?
Venue: arXiv cs.OH 2000
Year: 2000

The name of John von Neumann is common both in quantum mechanics and computer science. Are they really two absolutely unconnected areas? Many works devoted to quantum computations and communications are serious argument to suggest about existence of such a relation, but it is impossible to touch the new and active theme in a short review. In the paper are described the structures and models of linear algebra and just due to their generality it is possible to use universal description of very different areas as quantum mechanics and theory of Bayesian image analysis, associative memory, neural networks, fuzzy logic.
Agents of Choice: Tools that Facilitate Notice and Choice about Web Site Data Practices
Venue: arXiv cs.CY 2000
Year: 2000

A variety of tools have been introduced recently that are designed to help people protect their privacy on the Internet. These tools perform many different functions in-cluding encrypting and/or anonymizing communications, preventing the use of persistent identifiers such as cookies, automatically fetching and analyzing web site privacy policies, and displaying privacy-related information to users. This paper discusses the set of privacy tools that aim specifically at facilitating notice and choice about Web site data practices. While these tools may also have components that perform other functions such as encryption, or they may be able to work in conjunction with other privacy tools, the primary pur-pose of these tools is to help make users aware of web site privacy practices and to make it easier for users to make informed choices about when to provide data to web sites. Examples of such tools include the Platform for Privacy Preferences (P3P) and various infomediary services.
Pattern Discovery and Computational Mechanics
Venue: arXiv cs.LG 2000
Year: 2000

Computational mechanics is a method for discovering, describing and quantifying patterns, using tools from statistical physics. It constructs optimal, minimal models of stochastic processes and their underlying causal structures. These models tell us about the intrinsic computation embedded within a process---how it stores and transforms information. Here we summarize the mathematics of computational mechanics, especially recent optimality and uniqueness results. We also expound the principles and motivations underlying computational mechanics, emphasizing its connections to the minimum description length principle, PAC theory, and other aspects of machine learning.
On Automata with Boundary
Venue: arXiv cs.DC 2000
Year: 2000

We present a theory of automata with boundary for designing, modelling and analysing distributed systems. Notions of behaviour, design and simulation appropriate to the theory are defined. The problem of model checking for deadlock detection is discussed, and an algorithm for state space reduction in exhaustive search, based on the theory presented here, is described. Three examples of the application of the theory are given, one in the course of the development of the ideas and two as illustrative examples of the use of the theory.
Syntactic Autonomy: Why There is no Autonomy without Symbols and How Self-Organization Might Evolve Them
Venue: arXiv cs.AI 2000
Year: 2000

Two different types of agency are discussed based on dynamically coherent and incoherent couplings with an environment respectively. I propose that until a private syntax (syntactic autonomy) is discovered by dynamically coherent agents, there are no significant or interesting types of closure or autonomy. When syntactic autonomy is established, then, because of a process of description-based selected self-organization, open-ended evolution is enabled. At this stage, agents depend, in addition to dynamics, on localized, symbolic memory, thus adding a level of dynamical incoherence to their interaction with the environment. Furthermore, it is the appearance of syntactic autonomy which enables much more interesting types of closures amongst agents which share the same syntax. To investigate how we can study the emergence of syntax from dynamical systems, experiments with cellular automata leading to emergent computation to solve non-trivial tasks are discussed. RNA editing is also mentioned as a process that may have been used to obtain a primordial biological code necessary open-ended evolution.
Biologically Motivated Distributed Designs for Adaptive Knowledge Management
Venue: arXiv cs.IR 2000
Year: 2000

We discuss how distributed designs that draw from biological network metaphors can largely improve the current state of information retrieval and knowledge management of distributed information systems. In particular, two adaptive recommendation systems named TalkMine and @ApWeb are discussed in more detail. TalkMine operates at the semantic level of keywords. It leads different databases to learn new and adapt existing keywords to the categories recognized by its communities of users using distributed algorithms. @ApWeb operates at the structural level of information resources, namely citation or hyperlink structure. It relies on collective behavior to adapt such structure to the expectations of users. TalkMine and @ApWeb are currently being implemented for the research library of the Los Alamos National Laboratory under the Active Recommendation Project. Together they define a biologically motivated information retrieval system, recommending simultaneously at the level of user knowledge categories expressed in keywords, and at the level of individual documents and their associations to other documents. Rather than passive information retrieval, with this system, users obtain an active, evolving interaction with information resources.
Computing and Comparing Semantics of Programs in Multi-valued Logics
Venue: arXiv cs.LO 2000
Year: 2000

The different semantics that can be assigned to a logic program correspond to different assumptions made concerning the atoms whose logical values cannot be inferred from the rules. Thus, the well founded semantics corresponds to the assumption that every such atom is false, while the Kripke-Kleene semantics corresponds to the assumption that every such atom is unknown. In this paper, we propose to unify and extend this assumption-based approach by introducing parameterized semantics for logic programs. The parameter holds the value that one assumes for all atoms whose logical values cannot be inferred from the rules. We work within multi-valued logic with bilattice structure, and we consider the class of logic programs defined by Fitting. Following Fitting's approach, we define a simple operator that allows us to compute the parameterized semantics, and to compare and combine semantics obtained for different values of the parameter. The semantics proposed by Fitting corresponds to the value false. We also show that our approach captures and extends the usual semantics of conventional logic programs thereby unifying their computation.
Don't Trash your Intermediate Results, Cache 'em
Venue: arXiv cs.DB 2000
Year: 2000

In data warehouse and data mart systems, queries often take a long time to execute due to their complex nature. Query response times can be greatly improved by caching final/intermediate results of previous queries, and using them to answer later queries. In this paper we describe a caching system called Exchequer which incorporates several novel features including optimization aware cache maintenance and the use of a cache aware optimizer. In contrast, in existing work, the module that makes cost-benefit decisions is part of the cache manager and works independent of the optimizer which essentially reconsiders these decisions while finding the best plan for a query. In our work, the optimizer takes the decisions for the cache manager. Furthermore, existing approaches are either restricted to cube (slice/point) queries, or cache just the query results. On the other hand, our work is extens ible and in fact presents a data-model independent framework and algorithm. Our experimental results attest to the efficacy of our cache management techniques and show that over a wide range of parameters (a) Exchequer's query response times are lower by more than 30% compared to the best performing competitor, and (b) Exchequer can deliver the same response time as its competitor with just one tenth of the cache size.
A Comparison of Logic Programming Approaches for Representation and Solving of Constraint Satisfaction Problems
Venue: arXiv cs.LO 2000
Year: 2000

Many logic programming based approaches can be used to describe and solve combinatorial search problems. On the one hand there are definite programs and constraint logic programs that compute a solution as an answer substitution to a query containing the variables of the constraint satisfaction problem. On the other hand there are approaches based on stable model semantics, abduction, and first-order logic model generation that compute solutions as models of some theory. This paper compares these different approaches from point of view of knowledge representation (how declarative are the programs) and from point of view of performance (how good are they at solving typical problems).
Problem solving in ID-logic with aggregates: some experiments
Venue: arXiv cs.AI 2000
Year: 2000

The goal of the LP+ project at the K.U.Leuven is to design an expressive logic, suitable for declarative knowledge representation, and to develop intelligent systems based on Logic Programming technology for solving computational problems using the declarative specifications. The ID-logic is an integration of typed classical logic and a definition logic. Different abductive solvers for this language are being developed. This paper is a report of the integration of high order aggregates into ID-logic and the consequences on the solver SLDNFA.
Declarative Representation of Revision Strategies
Venue: arXiv cs.AI 2000
Year: 2000

In this paper we introduce a nonmonotonic framework for belief revision in which reasoning about the reliability of different pieces of information based on meta-knowledge about the information is possible, and where revision strategies can be described declaratively. The approach is based on a Poole-style system for default reasoning in which entrenchment information is represented in the logical language. A notion of inference based on the least fixed point of a monotone operator is used to make sure that all theories possess a consistent set of conclusions.
A Splitting Set Theorem for Epistemic Specifications
Venue: arXiv cs.AI 2000
Year: 2000

Over the past decade a considerable amount of research has been done to expand logic programming languages to handle incomplete information. One such language is the language of epistemic specifications. As is usual with logic programming languages, the problem of answering queries is intractable in the general case. For extended disjunctive logic programs, an idea that has proven useful in simplifying the investigation of answer sets is the use of splitting sets. In this paper we will present an extended definition of splitting sets that will be applicable to epistemic specifications. Furthermore, an extension of the splitting set theorem will be presented. Also, a characterization of stratified epistemic specifications will be given in terms of splitting sets. This characterization leads us to an algorithmic method of computing world views of a subclass of epistemic logic programs.
A tableau methodology for deontic conditional logics
Venue: arXiv cs.LO 2000
Year: 2000

In this paper we present a theorem proving methodology for a restricted but significant fragment of the conditional language made up of (boolean combinations of) conditional statements with unnested antecedents. The method is based on the possible world semantics for conditional logics. The KEM label formalism, designed to account for the semantics of normal modal logics, is easily adapted to the semantics of conditional logics by simply indexing labels with formulas. The inference rules are provided by the propositional system KE+ - a tableau-like analytic proof system devised to be used both as a refutation and a direct method of proof - enlarged with suitable elimination rules for the conditional connective. The theorem proving methodology we are going to present can be viewed as a first step towards developing an appropriate algorithmic framework for several conditional logics for (defeasible) conditional obligation.
A Problem-Specific Fault-Tolerance Mechanism for Asynchronous, Distributed Systems
Venue: arXiv cs.DC 2000
Year: 2000

The idle computers on a local area, campus area, or even wide area network represent a significant computational resource---one that is, however, also unreliable, heterogeneous, and opportunistic. This type of resource has been used effectively for embarrassingly parallel problems but not for more tightly coupled problems. We describe an algorithm that allows branch-and-bound problems to be solved in such environments. In designing this algorithm, we faced two challenges: (1) scalability, to effectively exploit the variably sized pools of resources available, and (2) fault tolerance, to ensure the reliability of services. We achieve scalability through a fully decentralized algorithm, by using a membership protocol for managing dynamically available resources. However, this fully decentralized design makes achieving reliability even more challenging. We guarantee fault tolerance in the sense that the loss of up to all but one resource will not affect the quality of the solution. For propagating information efficiently, we use epidemic communication for both the membership protocol and the fault-tolerance mechanism. We have developed a simulation framework that allows us to evaluate design alternatives. Results obtained in this framework suggest that our techniques can execute scalably and reliably.
A note on the Declarative reading(s) of Logic Programming
Venue: arXiv cs.LO 2000
Year: 2000

This paper analyses the declarative readings of logic programming. Logic programming - and negation as failure - has no unique declarative reading. One common view is that logic programming is a logic for default reasoning, a sub-formalism of default logic or autoepistemic logic. In this view, negation as failure is a modal operator. In an alternative view, a logic program is interpreted as a definition. In this view, negation as failure is classical objective negation. From a commonsense point of view, there is definitely a difference between these views. Surprisingly though, both types of declarative readings lead to grosso modo the same model semantics. This note investigates the causes for this.