OpenRaiser/Intern-Atlas huggingface dataset:
Approximate Graph Coloring by Semidefinite Programming
Venue: arXiv cs.DS 1998
Year: 1998

We consider the problem of coloring k-colorable graphs with the fewest possible colors. We present a randomized polynomial time algorithm that colors a 3-colorable graph on $n$ vertices with min O(Delta^{1/3} log^{1/2} Delta log n), O(n^{1/4} log^{1/2} n) colors where Delta is the maximum degree of any vertex. Besides giving the best known approximation ratio in terms of n, this marks the first non-trivial approximation result as a function of the maximum degree Delta. This result can be generalized to k-colorable graphs to obtain a coloring using min O(Delta^{1-2/k} log^{1/2} Delta log n), O(n^{1-3/(k+1)} log^{1/2} n) colors. Our results are inspired by the recent work of Goemans and Williamson who used an algorithm for semidefinite optimization problems, which generalize linear programs, to obtain improved approximations for the MAX CUT and MAX 2-SAT problems. An intriguing outcome of our work is a duality relationship established between the value of the optimum solution to our semidefinite program and the Lovasz theta-function. We show lower bounds on the gap between the optimum solution of our semidefinite program and the actual chromatic number; by duality this also demonstrates interesting new facts about the theta-function.
An Adaptive Agent Oriented Software Architecture
Venue: arXiv cs.DC 1998
Year: 1998

A new approach to software design based on an agent-oriented architecture is presented. Unlike current research, we consider software to be designed and implemented with this methodology in mind. In this approach agents are considered adaptively communicating concurrent modules which are divided into a white box module responsible for the communications and learning, and a black box which is the independent specialized processes of the agent. A distributed Learning policy is also introduced for adaptability.
Forgetting Exceptions is Harmful in Language Learning
Venue: arXiv cs.CL 1998
Year: 1998

We show that in language learning, contrary to received wisdom, keeping exceptional training instances in memory can be beneficial for generalization accuracy. We investigate this phenomenon empirically on a selection of benchmark natural language processing tasks: grapheme-to-phoneme conversion, part-of-speech tagging, prepositional-phrase attachment, and base noun phrase chunking. In a first series of experiments we combine memory-based learning with training set editing techniques, in which instances are edited based on their typicality and class prediction strength. Results show that editing exceptional instances (with low typicality or low class prediction strength) tends to harm generalization accuracy. In a second series of experiments we compare memory-based learning and decision-tree learning methods on the same selection of tasks, and find that decision-tree learning often performs worse than memory-based learning. Moreover, the decrease in performance can be linked to the degree of abstraction from exceptions (i.e., pruning or eagerness). We provide explanations for both results in terms of the properties of the natural language processing tasks and the learning algorithms.
Hypertree Decompositions and Tractable Queries
Venue: arXiv cs.DB 1998
Year: 1998

Several important decision problems on conjunctive queries (CQs) are NP-complete in general but become tractable, and actually highly parallelizable, if restricted to acyclic or nearly acyclic queries. Examples are the evaluation of Boolean CQs and query containment. These problems were shown tractable for conjunctive queries of bounded treewidth and of bounded degree of cyclicity. The so far most general concept of nearly acyclic queries was the notion of queries of bounded query-width introduced by Chekuri and Rajaraman (1997). While CQs of bounded query width are tractable, it remained unclear whether such queries are efficiently recognizable. Chekuri and Rajaraman stated as an open problem whether for each constant k it can be determined in polynomial time if a query has query width less than or equal to k. We give a negative answer by proving this problem NP-complete (specifically, for k=4). In order to circumvent this difficulty, we introduce the new concept of hypertree decomposition of a query and the corresponding notion of hypertree width. We prove: (a) for each k, the class of queries with query width bounded by k is properly contained in the class of queries whose hypertree width is bounded by k; (b) unlike query width, constant hypertree-width is efficiently recognizable; (c) Boolean queries of constant hypertree width can be efficiently evaluated.
Virtual Kathakali : Gesture Driven Metamorphosis
Venue: arXiv cs.HC 1998
Year: 1998

Training in motor skills such as athletics, dance, or gymnastics is not possible today except in the direct presence of the coach/instructor. This paper describes a computer vision based gesture recognition system which is used to metamorphose the user into a Virtual person, e.g. as a Kathakali dancer, which is graphically recreated at a near or diatant location. Thus this can be seen by an off-site coach using low-bandwidth joint-motion data which permits real time animation. The metamorphosis involves altering the appearance and identity of the user and also creating a specific environment possibly in interaction with other virtual creatures. A robust vision module is used to identify the user, based on very simple binary image processing in real time which also manages to resolve self-occlusion, correct for clothing/colour and other variations among users. Gestures are identified by locating key points at the shoulder, elbow and wrist joint, which are then recreated in an articulated humanoid model, which in this instance, representes a Kathakali dancer in elaborate traditional dress. Unlike glove based or other and movement tracking systems, this application requires the user to wear no hardwire devices and is aimed at making gesture tracking simpler, cheaper, and more user friendly.
Universal Object Oriented Languages and Computer Algebra
Venue: arXiv cs.PL 1999
Year: 1999

The universal object oriented languages made programming more simple and efficient. In the article is considered possibilities of using similar methods in computer algebra. A clear and powerful universal language is useful if particular problem was not implemented in standard software packages like REDUCE, MATHEMATICA, etc. and if the using of internal programming languages of the packages looks not very efficient. Functional languages like LISP had some advantages and traditions for algebraic and symbolic manipulations. Functional and object oriented programming are not incompatible ones. An extension of the model of an object for manipulation with pure functions and algebraic expressions is considered.
Representation Theory for Default Logic
Venue: arXiv cs.LO 1999
Year: 1999

Default logic can be regarded as a mechanism to represent families of belief sets of a reasoning agent. As such, it is inherently second-order. In this paper, we study the problem of representability of a family of theories as the set of extensions of a default theory. We give a complete solution to the representability by means of normal default theories. We obtain partial results on representability by arbitrary default theories. We construct examples of denumerable families of non-including theories that are not representable. We also study the concept of equivalence between default theories.
KEA: Practical Automatic Keyphrase Extraction
Venue: arXiv cs.DL 1999
Year: 1999

Keyphrases provide semantic metadata that summarize and characterize documents. This paper describes Kea, an algorithm for automatically extracting keyphrases from text. Kea identifies candidate keyphrases using lexical methods, calculates feature values for each candidate, and uses a machine-learning algorithm to predict which candidates are good keyphrases. The machine learning scheme first builds a prediction model using training documents with known keyphrases, and then uses the model to find keyphrases in new documents. We use a large test corpus to evaluate Kea's effectiveness in terms of how many author-assigned keyphrases are correctly identified. The system is simple, robust, and publicly available.
Multimedia Description Framework (MDF) for Content Description of Audio/Video Documents
Venue: arXiv cs.DL 1999
Year: 1999

MPEG is undertaking a new initiative to standardize content description of audio and video data/documents. When it is finalized in 2001, MPEG-7 is expected to provide standardized description schemes for concise and unambiguous content description of data/documents of complex media types. Meanwhile, other meta-data or description schemes, such as Dublin Core, XML, etc., are becoming popular in different application domains. In this paper, we propose the Multimedia Description Framework (MDF), which is designated to accommodate multiple description (meta-data) schemes, both MPEG-7 and non-MPEG-7, into integrated architecture. We will use examples to show how MDF description makes use of combined strength of different description schemes to enhance its expression power and flexibility. We conclude the paper with discussion of using MDF description of a movie video to search/retrieve required scene clips from the movie, on the MDF prototype system we have implemented.
Semi-Automatic Indexing of Multilingual Documents
Venue: arXiv cs.DL 1999
Year: 1999

With the growing significance of digital libraries and the Internet, more and more electronic texts become accessible to a wide and geographically disperse public. This requires adequate tools to facilitate indexing, storage, and retrieval of documents written in different languages. We present a method for semi-automatic indexing of electronic documents and construction of a multilingual thesaurus, which can be used for query formulation and information retrieval. We use special dictionaries and user interaction in order to solve ambiguities and find adequate canonical terms in the language and adequate abstract language-independent terms. The abstract thesaurus is updated incrementally by new indexed documents and is used to search document concerning terms in a query to the document base.
Some Remarks on the Geometry of Grammar
Venue: arXiv cs.CL 1999
Year: 1999

This paper, following (Dymetman:1998), presents an approach to grammar description and processing based on the geometry of cancellation diagrams, a concept which plays a central role in combinatorial group theory (Lyndon-Schuppe:1977). The focus here is on the geometric intuitions and on relating group-theoretical diagrams to the traditional charts associated with context-free grammars and type-0 rewriting systems. The paper is structured as follows. We begin in Section 1 by analyzing charts in terms of constructs called cells, which are a geometrical counterpart to rules. Then we move in Section 2 to a presentation of cancellation diagrams and show how they can be used computationally. In Section 3 we give a formal algebraic presentation of the concept of group computation structure, which is based on the standard notions of free group and conjugacy. We then relate in Section 4 the geometric and the algebraic views of computation by using the fundamental theorem of combinatorial group theory (Rotman:1994). In Section 5 we study in more detail the relationship between the two views on the basis of a simple grammar stated as a group computation structure. In section 6 we extend this grammar to handle non-local constructs such as relative pronouns and quantifiers. We conclude in Section 7 with some brief notes on the differences between normal submonoids and normal subgroups, group computation versus rewriting systems, and the use of group morphisms to study the computational complexity of parsing and generation.
A class of problems of NP to be worth to search an efficient solving algorithm
Venue: arXiv cs.DS 1999
Year: 1999

We examine possibility to design an efficient solving algorithm for problems of the class \np. It is introduced a classification of \np problems by the property that a partial solution of size $k$ can be extended into a partial solution of size $k+1$ in polynomial time. It is defined an unique class problems to be worth to search an efficient solving algorithm. The problems, which are outside of this class, are inherently exponential. We show that the Hamiltonian cycle problem is inherently exponential.
A complete anytime algorithm for balanced number partitioning
Venue: arXiv cs.DS 1999
Year: 1999

Given a set of numbers, the balanced partioning problem is to divide them into two subsets, so that the sum of the numbers in each subset are as nearly equal as possible, subject to the constraint that the cardinalities of the subsets be within one of each other. We combine the balanced largest differencing method (BLDM) and Korf's complete Karmarkar-Karp algorithm to get a new algorithm that optimally solves the balanced partitioning problem. For numbers with twelve significant digits or less, the algorithm can optimally solve balanced partioning problems of arbitrary size in practice. For numbers with greater precision, it first returns the BLDM solution, then continues to find better solutions as time allows.
The Impact of Net Culture on Mainstream Societies: a Global Analysis
Venue: arXiv cs.CY 1999
Year: 1999

In this work the impact of the Internet culture on standard mainstream societies has been analyzed. After analytically establishing the fact that the Net can be viewed as a pan-societal superstructure which supports its own distinct culture, an ethnographic analysis is provided to find out the key aspects of this culture. The elements of this culture which have an empowering impacts on the standard mainstream societies, as well as the elements in it which can cause discouraging social effects are then discussed by a global investigation of the present status of various fundamental aspects (e,g, education, economics, politics, entertainment etc) of the mainstream societies as well as their links with the Net culture. Though immensely potential for providing various prominent positive impacts, the key findings of this work indicate that misuse of Internet can create tremendous harm to the members of the mainstream societies by generating a set of morally crippled people as well as a future generation completely void of principles and ethics. This structured diagnostic approach to the social problems caused by the manhandling of Internet leads to a concrete effort of providing the measures that can be taken to enhance or to overcome the supporting and limiting effects of the Net culture respectively with the intent to benefit our society and to protect the teratoidation of certain ethical values.
SIMMUNE, a tool for simulating and analyzing immune system behavior
Venue: arXiv cs.MA 1999
Year: 1999

We present a new approach to the simulation and analysis of immune system behavior. The simulations that can be done with our software package called SIMMUNE are based on immunological data that describe the behavior of immune system agents (cells, molecules) on a microscopial (i.e. agent-agent interaction) scale by defining cellular stimulus-response mechanisms. Since the behavior of the agents in SIMMUNE can be very flexibly configured, its application is not limited to immune system simulations. We outline the principles of SIMMUNE's multiscale analysis of emergent structure within the simulated immune system that allow the identification of immunological contexts using minimal a priori assumptions about the higher level organization of the immune system.
A Proposal for the Establishment of Review Boards - a flexible approach to the selection of academic knowledge
Venue: arXiv cs.CY 1999
Year: 1999

Paper journals use a small number of trusted academics to select information on behalf of all their readers. This inflexibility in the selection was justified due to the expense of publishing. The advent of cheap distribution via the internet allows a new trade-off between time and expense and the flexibility of the selection process. This paper explores one such possible process one where the role of mark-up and archiving is separated from that of review. The idea is that authors publish their papers on their own web pages or in a public paper archive, a board of reviewers judge that paper on a number of different criteria. The detailed results of the reviews are stored in such a way as to enable readers to use these judgements to find the papers they want using search engines on the web. Thus instead of journals using generic selection criteria readers can set their own to suit their needs. The resulting system might be even cheaper than web-journals to implement.
A geometric framework for modelling similarity search
Venue: arXiv cs.IR 1999
Year: 1999

The aim of this paper is to propose a geometric framework for modelling similarity search in large and multidimensional data spaces of general nature, which seems to be flexible enough to address such issues as analysis of complexity, indexability, and the `curse of dimensionality.' Such a framework is provided by the concept of the so-called similarity workload, which is a probability metric space $Ω$ (query domain) with a distinguished finite subspace $X$ (dataset), together with an assembly of concepts, techniques, and results from metric geometry. They include such notions as metric transform, $\e$-entropy, and the phenomenon of concentration of measure on high-dimensional structures. In particular, we discuss the relevance of the latter to understanding the curse of dimensionality. As some of those concepts and techniques are being currently reinvented by the database community, it seems desirable to try and bridge the gap between database research and the relevant work already done in geometry and analysis.
Transport Level Security: a proof using the Gong-Needham-Yahalom Logic
Venue: arXiv cs.CR 1999
Year: 1999

This paper provides a proof of the proposed Internet standard Transport Level Security protocol using the Gong-Needham-Yahalom logic. It is intended as a teaching aid and hopes to show to students: the potency of a formal method for protocol design; some of the subtleties of authenticating parties on a network where all messages can be intercepted; the design of what should be a widely accepted standard.
DRAFT : Task System and Item Architecture (TSIA)
Venue: arXiv cs.PL 1999
Year: 1999

During its execution, a task is independent of all other tasks. For an application which executes in terms of tasks, the application definition can be free of the details of the execution. Many projects have demonstrated that a task system (TS) can provide such an application with a parallel, distributed, heterogeneous, adaptive, dynamic, real-time, interactive, reliable, secure or other execution. A task consists of items and thus the application is defined in terms of items. An item architecture (IA) can support arrays, routines and other structures of items, thus allowing for a structured application definition. Taking properties from many projects, the support can extend through to currying, application defined types, conditional items, streams and other definition elements. A task system and item architecture (TSIA) thus promises unprecedented levels of support for application execution and definition.
Combining Inclusion Polymorphism and Parametric Polymorphism
Venue: arXiv cs.LO 1999
Year: 1999

We show that the question whether a term is typable is decidable for type systems combining inclusion polymorphism with parametric polymorphism provided the type constructors are at most unary. To prove this result we first reduce the typability problem to the problem of solving a system of type inequations. The result is then obtained by showing that the solvability of the resulting system of type inequations is decidable.
Evaluation of the NLP Components of the OVIS2 Spoken Dialogue System
Venue: arXiv cs.CL 1999
Year: 1999

The NWO Priority Programme Language and Speech Technology is a 5-year research programme aiming at the development of spoken language information systems. In the Programme, two alternative natural language processing (NLP) modules are developed in parallel: a grammar-based (conventional, rule-based) module and a data-oriented (memory-based, stochastic, DOP) module. In order to compare the NLP modules, a formal evaluation has been carried out three years after the start of the Programme. This paper describes the evaluation procedure and the evaluation results. The grammar-based component performs much better than the data-oriented one in this comparison.
Generalization of automatic sequences for numeration systems on a regular language
Venue: arXiv cs.CC 1999
Year: 1999

Let L be an infinite regular language on a totally ordered alphabet (A,<). Feeding a finite deterministic automaton (with output) with the words of L enumerated lexicographically with respect to < leads to an infinite sequence over the output alphabet of the automaton. This process generalizes the concept of k-automatic sequence for abstract numeration systems on a regular language (instead of systems in base k). Here, I study the first properties of these sequences and their relations with numeration systems.
On the Power of Positive Turing Reductions
Venue: arXiv cs.CC 1999
Year: 1999

In the early 1980s, Selman's seminal work on positive Turing reductions showed that positive Turing reduction to NP yields no greater computational power than NP itself. Thus, positive Turing and Turing reducibility to NP differ sharply unless the polynomial hierarchy collapses. We show that the situation is quite different for DP, the next level of the boolean hierarchy. In particular, positive Turing reduction to DP already yields all (and only) sets Turing reducibility to NP. Thus, positive Turing and Turing reducibility to DP yield the same class. Additionally, we show that an even weaker class, P(NP[1]), can be substituted for DP in this context.
Events in Property Patterns
Venue: arXiv cs.SE 1999
Year: 1999

A pattern-based approach to the presentation, codification and reuse of property specifications for finite-state verification was proposed by Dwyer and his collegues. The patterns enable non-experts to read and write formal specifications for realistic systems and facilitate easy conversion of specifications between formalisms, such as LTL, CTL, QRE. In this paper, we extend the pattern system with events - changes of values of variables in the context of LTL.
Representing Text Chunks
Venue: arXiv cs.CL 1999
Year: 1999

Dividing sentences in chunks of words is a useful preprocessing step for parsing, information extraction and information retrieval. (Ramshaw and Marcus, 1995) have introduced a "convenient" data representation for chunking by converting it to a tagging task. In this paper we will examine seven different data representations for the problem of recognizing noun phrase chunks. We will show that the the data representation choice has a minor influence on chunking performance. However, equipped with the most suitable data representation, our memory-based learning chunker was able to improve the best published chunking results for a standard data set.
Selective Magic HPSG Parsing
Venue: arXiv cs.CL 1999
Year: 1999

We propose a parser for constraint-logic grammars implementing HPSG that combines the advantages of dynamic bottom-up and advanced top-down control. The parser allows the user to apply magic compilation to specific constraints in a grammar which as a result can be processed dynamically in a bottom-up and goal-directed fashion. State of the art top-down processing techniques are used to deal with the remaining constraints. We discuss various aspects concerning the implementation of the parser as part of a grammar development system.