OpenRaiser/Intern-Atlas huggingface dataset:
The Increased Need For FCC Merger Review In A Networked World
Venue: arXiv cs.CY 2001
Year: 2001

Recently, the FCC announced a new standard for review in mergers. Under the new standard, mass media mergers that comply with existing rules will automaticly receive approval, while those that do not will receive a more searching review. Common carrier mergers, however, will continue to receive the 4=part test established in Bell Atlantic/Nynex. The new standard fails to take into account the complexities of the emerging, converged networked world, and is essentially obsolete on arrival. Looking to those areas where Congress has required an additional public interest review of mergers, a pattern emerges. The emergence of vast, vertically integrated networks of content and conduit fit the historic pattern of areas requiring piublic interest review and re-enforce the need for increased, rather than decreased merger review.
A logic-based approach to data integration
Venue: arXiv cs.DB 2001
Year: 2001

An important aspect of data integration involves answering queries using various resources rather than by accessing database relations. The process of transforming a query from the database relations to the resources is often referred to as query folding or answering queries using views, where the views are the resources. We present a uniform approach that includes as special cases much of the previous work on this subject. Our approach is logic-based using resolution. We deal with integrity constraints, negation, and recursion also within this framework.
Practical Aspects for a Working Compile Time Garbage Collection System for Mercury
Venue: arXiv cs.PL 2001
Year: 2001

Compile-time garbage collection (CTGC) is still a very uncommon feature within compilers. In previous work we have developed a compile-time structure reuse system for Mercury, a logic programming language. This system indicates which datastructures can safely be reused at run-time. As preliminary experiments were promising, we have continued this work and have now a working and well performing near-to-ship CTGC-system built into the Melbourne Mercury Compiler (MMC). In this paper we present the multiple design decisions leading to this system, we report the results of using CTGC for a set of benchmarks, including a real-world program, and finally we discuss further possible improvements. Benchmarks show substantial memory savings and a noticeable reduction in execution time.
Two heads are better than two tapes
Venue: arXiv cs.CC 2001
Year: 2001

We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set {x2x'| x \in {0,1}^* and x' is a prefix of x} in real time, although it can do so with three tapes, two two-dimensional tapes, or one two-head tape, or in linear time with just one tape. In particular, this settles the longstanding conjecture that a two-head Turing machine can recognize more languages in real time if its heads are on the same one-dimensional tape than if they are on separate one-dimensional tapes.
An Architecture for Security and Privacy in Mobile Communications
Venue: arXiv cs.CY 2001
Year: 2001

There is much discussion and debate about how to improve the security and privacy of mobile communication systems, both voice and data. Most proposals attempt to provide incremental improvements to systems that are deployed today. Indeed, only incremental improvements are possible, given the regulatory, technological, economic, and historical structure of the telecommunications system. In this paper, we conduct a ``thought experiment'' to redesign the mobile communications system to provide a high level of security and privacy for the users of the system. We discuss the important requirements and how a different architecture might successfully satisfy them. In doing so, we hope to illuminate the possibilities for secure and private systems, as well as explore their real limits.
An Overview of Computer security
Venue: arXiv cs.CY 2001
Year: 2001

As more business activities are being automated and an increasing number of computers are being used to store vital and sensitive information the need for secure computer systems becomes more apparent. These systems can be achieved only through systematic design; they cannot be achieved through haphazard seat-of-the-pants methods.This paper introduces some known threats to the computer security, categorizes the threats, and analyses protection mechanisms and techniques for countering the threats. The threats have been classified more so as definitions and then followed by the classifications of these threats. Also mentioned are the protection mechanisms.
EquiX--A Search and Query Language for XML
Venue: arXiv cs.DB 2001
Year: 2001

EquiX is a search language for XML that combines the power of querying with the simplicity of searching. Requirements for such languages are discussed and it is shown that EquiX meets the necessary criteria. Both a graph-based abstract syntax and a formal concrete syntax are presented for EquiX queries. In addition, the semantics is defined and an evaluation algorithm is presented. The evaluation algorithm is polynomial under combined complexity. EquiX combines pattern matching, quantification and logical expressions to query both the data and meta-data of XML documents. The result of a query in EquiX is a set of XML documents. A DTD describing the result documents is derived automatically from the query.
Generating Multilingual Personalized Descriptions of Museum Exhibits - The M-PIRO Project
Venue: arXiv cs.CL 2001
Year: 2001

This paper provides an overall presentation of the M-PIRO project. M-PIRO is developing technology that will allow museums to generate automatically textual or spoken descriptions of exhibits for collections available over the Web or in virtual reality environments. The descriptions are generated in several languages from information in a language-independent database and small fragments of text, and they can be tailored according to the backgrounds of the users, their ages, and their previous interaction with the system. An authoring tool allows museum curators to update the system's database and to control the language and content of the resulting descriptions. Although the project is still in progress, a Web-based demonstrator that supports English, Greek and Italian is already available, and it is used throughout the paper to highlight the capabilities of the emerging technology.
Integrating LabVIEW into a Distributed Computing Environment
Venue: arXiv cs.OH 2001
Year: 2001

Being easy to learn and well suited for a self-contained desktop laboratory setup, many casual programmers prefer to use the National Instruments LabVIEW environment to develop their logic. An ActiveX interface is presented that allows integration into a plant-wide distributed environment based on the Experimental Physics and Industrial Control System (EPICS). This paper discusses the design decisions and provides performance information, especially considering requirements for the Spallation Neutron Source (SNS) diagnostics system.
L-Fuzzy Valued Inclusion Measure, L-Fuzzy Similarity and L-Fuzzy Distance
Venue: arXiv cs.OH 2001
Year: 2001

The starting point of this paper is the introduction of a new measure of inclusion of fuzzy set A in fuzzy set B. Previously used inclusion measures take values in the interval [0,1]; the inclusion measure proposed here takes values in a Boolean lattice. In other words, inclusion is viewed as an L-fuzzy valued relation between fuzzy sets. This relation is re exive, antisymmetric and transitive, i.e. it is a fuzzy order relation; in addition it possesess a number of properties which various authors have postulated as axiomatically appropriate for an inclusion measure. We also define an L-fuzzy valued measure of similarity between fuzzy sets and and an L-fuzzy valued distance function between fuzzy sets; these possess properties analogous to the ones of real-valued similarity and distance functions. Keywords: Fuzzy Relations, inclusion measure, subsethood, L-fuzzy sets, similarity, distance, transitivity.
Abduction with Penalization in Logic Programming
Venue: arXiv cs.LO 2001
Year: 2001

Abduction, first proposed in the setting of classical logics, has been studied with growing interest in the logic programming area during the last years. In this paper we study {\em abduction with penalization} in logic programming. This form of abductive reasoning, which has not been previously analyzed in logic programming, turns out to represent several relevant problems, including optimization problems, very naturally. We define a formal model for abduction with penalization from logic programs, which extends the abductive framework proposed by Kakas and Mancarella. We show the high expressiveness of this formalism, by encoding a couple of relevant problems, including the well-know Traveling Salesman Problem from optimization theory, in this abductive framework. The resulting encodings are very simple and elegant. We analyze the complexity of the main decisional problems arising in this framework. An interesting result in this course is that ``negation comes for free.'' Indeed, the addition of (even unstratified) negation does not cause any further increase to the complexity of the abductive reasoning tasks (which remains the same as for not-free programs).
Building Multi-Platform User Interfaces with UIML
Venue: arXiv cs.HC 2001
Year: 2001

There has been a widespread emergence of computing devices in the past few years that go beyond the capabilities of traditional desktop computers. However, users want to use the same kinds of applications and access the same data and information on these appliances that they can access on their desktop computers. The user interfaces for these platforms go beyond the traditional interaction metaphors. It is a challenge to build User Interfaces (UIs) for these devices of differing capabilities that allow the end users to perform the same kinds of tasks. The User Interface Markup Language (UIML) is an XML-based language that allows the canonical description of UIs for different platforms. We describe the language features of UIML that facilitate the development of multi-platform UIs. We also describe the key aspects of our approach that makes UIML succeed where previous approaches failed, namely the division in the representation of a UI, the use of a generic vocabulary, and an integrated development environment specifically designed for transformation-based UI development. Finally we describe the initial details of a multi-step usability engineering process for building multi-platform UI using UIML.
A Multi-Step Process for Generating Multi-Platform User Interfaces using UIML
Venue: arXiv cs.HC 2001
Year: 2001

There has been a widespread emergence of computing devices in the past few years that go beyond the capabilities of traditional desktop computers. These devices have varying input/output characteristics, modalities and interaction mechanisms. However, users want to use the same kinds of applications and access the same data and information on these appliances that they can access on their desktop computers. The user interfaces for these devices and platforms go beyond the traditional interaction metaphors. It is a challenge to build User Interfaces (UIs) for these devices of differing capabilities that allow the end users to perform the same kinds of tasks. The User Interface Markup Language (UIML) is an XML-based language that allows the canonical description of UIs for different platforms. We present a multi-step transformation-based framework for building Multi-Platform User Interfaces using UIML. We describe the language features of UIML that facilitate the development of multi-platform UIs, the multi-step process involved in our framework and the transformations needed to build the UIs.
A Dual Digital Signal Processor VME Board For Instrumentation And Control Applications
Venue: arXiv cs.AR 2001
Year: 2001

A Dual Digital Signal Processing VME Board was developed for the Continuous Electron Beam Accelerator Facility (CEBAF) Beam Current Monitor (BCM) system at Jefferson Lab. It is a versatile general-purpose digital signal processing board using an open architecture, which allows for adaptation to various applications. The base design uses two independent Texas Instrument (TI) TMS320C6711, which are 900 MFLOPS floating-point digital signal processors (DSP). Applications that require a fixed point DSP can be implemented by replacing the baseline DSP with the pin-for-pin compatible TMS320C6211. The design can be manufactured with a reduced chip set without redesigning the printed circuit board. For example it can be implemented as a single-channel DSP with no analog I/O.
Data Access - Experiences Implementing an Object Oriented Library on Various Platforms
Venue: arXiv cs.SE 2001
Year: 2001

Data Access will be the next generation data abstraction layer for EPICS. Its implementation in C++ brought up a number of issues that are related to object oriented technology's impact on CPU and memory usage. What is gained by the new abstract interface? What is the price that has to be paid for these gains? What compromises seem applicable and affordable? This paper discusses tests that have been made about performance and memory usage as well as the different measures that have been taken to optimize the situation.
Arc consistency for soft constraints
Venue: arXiv cs.AI 2001
Year: 2001

The notion of arc consistency plays a central role in constraint satisfaction. It is known that the notion of local consistency can be extended to constraint optimisation problems defined by soft constraint frameworks based on an idempotent cost combination operator. This excludes non idempotent operators such as + which define problems which are very important in practical applications such as Max-CSP, where the aim is to minimize the number of violated constraints. In this paper, we show that using a weak additional axiom satisfied by most existing soft constraints proposals, it is possible to define a notion of soft arc consistency that extends the classical notion of arc consistency and this even in the case of non idempotent cost combination operators. A polynomial time algorithm for enforcing this soft arc consistency exists and its space and time complexities are identical to that of enforcing arc consistency in CSPs when the cost combination operator is strictly monotonic (for example Max-CSP). A directional version of arc consistency is potentially even stronger than the non-directional version, since it allows non local propagation of penalties. We demonstrate the utility of directional arc consistency by showing that it not only solves soft constraint problems on trees, but that it also implies a form of local optimality, which we call arc irreducibility.
Bayesian Logic Programs
Venue: arXiv cs.AI 2001
Year: 2001

Bayesian networks provide an elegant formalism for representing and reasoning about uncertainty using probability theory. Theyare a probabilistic extension of propositional logic and, hence, inherit some of the limitations of propositional logic, such as the difficulties to represent objects and relations. We introduce a generalization of Bayesian networks, called Bayesian logic programs, to overcome these limitations. In order to represent objects and relations it combines Bayesian networks with definite clause logic by establishing a one-to-one mapping between ground atoms and random variables. We show that Bayesian logic programs combine the advantages of both definite clause logic and Bayesian networks. This includes the separation of quantitative and qualitative aspects of the model. Furthermore, Bayesian logic programs generalize both Bayesian networks as well as logic programs. So, many ideas developed
On a Special Case of the Generalized Neighbourhood Problem
Venue: arXiv cs.DM 2001
Year: 2001

For a given finite class of finite graphs H, a graph G is called a realization of H if the neighbourhood of its any vertex induces the subgraph isomorphic to a graph of H. We consider the following problem known as the Generalized Neighbourhood Problem (GNP): given a finite class of finite graphs H, does there exist a non-empty graph G that is a realization of H? In fact, there are two modifications of that problem, namely the finite (the existence of a finite realization is required) and infinite one (the realization is required to be infinite). In this paper we show that GNP and its modifications for all finite classes H of finite graphs are reduced to the same problems with an additional restriction on H. Namely, the orders of any two graphs of H are equal and every graph of H has exactly s dominating vertices.
Program schemes with binary write-once arrays and the complexity classes they capture
Venue: arXiv cs.LO 2001
Year: 2001

We study a class of program schemes, NPSB, in which, aside from basic assignments, non-deterministic guessing and while loops, we have access to arrays; but where these arrays are binary write-once in that they are initialized to `zero' and can only ever be set to `one'. We show, amongst other results, that: NPSB can be realized as a vectorized Lindstrom logic; there are problems accepted by program schemes of NPSB that are not definable in the bounded-variable infinitary logic ${\cal L}^ω_{\inftyω}$; all problems accepted by the program schemes of NPSB have a zero-one law; and on ordered structures, NPSB captures the complexity class $[ L]^[{\scriptsize NP\normalsize}]$. The class of program schemes NPSB is actually the union of an infinite hierarchy of classes of program schemes. When we amend the semantics of our program schemes slightly, we find that the classes of the resulting hierarchy capture the complexity classes $Σ^p_i$ (where $i\geq 1$) of the Polynomial Hierarchy PH. Finally, we give logical equivalences of the complexity-theoretic question `Does NP equal PSPACE?' where the logics (and classes of program schemes) involved define only problems with zero-one laws (and so do not define some computationally trivial problems).
Part of Speech Tagging in Thai Language Using Support Vector Machine
Venue: arXiv cs.CL 2001
Year: 2001

The elastic-input neuro tagger and hybrid tagger, combined with a neural network and Brill's error-driven learning, have already been proposed for the purpose of constructing a practical tagger using as little training data as possible. When a small Thai corpus is used for training, these taggers have tagging accuracies of 94.4% and 95.5% (accounting only for the ambiguous words in terms of the part of speech), respectively. In this study, in order to construct more accurate taggers we developed new tagging methods using three machine learning methods: the decision-list, maximum entropy, and support vector machine methods. We then performed tagging experiments by using these methods. Our results showed that the support vector machine method has the best precision (96.1%), and that it is capable of improving the accuracy of tagging in the Thai language. Finally, we theoretically examined all these methods and discussed how the improvements were achived.
A Straightforward Approach to Morphological Analysis and Synthesis
Venue: arXiv cs.CL 2001
Year: 2001

In this paper we present a lexicon-based approach to the problem of morphological processing. Full-form words, lemmas and grammatical tags are interconnected in a DAWG. Thus, the process of analysis/synthesis is reduced to a search in the graph, which is very fast and can be performed even if several pieces of information are missing from the input. The contents of the DAWG are updated using an on-line incremental process. The proposed approach is language independent and it does not utilize any morphophonetic rules or any other special linguistic information.
A Higher-Order Implementation of Rewriting
Venue: arXiv cs.LO 2001
Year: 2001

Many automatic theorem-provers rely on rewriting. Using theorems as rewrite rules helps to simplify the subgoals that arise during a proof. LCF is an interactive theorem-prover intended for reasoning about computation. Its implementation of rewriting is presented in detail. LCF provides a family of rewriting functions, and operators to combine them. A succession of functions is described, from pattern matching primitives to the rewriting tool that performs most inferences in LCF proofs. The design is highly modular. Each function performs a basic, specific task, such as recognizing a certain form of tautology. Each operator implements one method of building a rewriting function from simpler ones. These pieces can be put together in numerous ways, yielding a variety of rewrit- ing strategies. The approach involves programming with higher-order functions. Rewriting functions are data values, produced by computation on other rewriting functions. The code is in daily use at Cambridge, demonstrating the practical use of functional programming.
Designing a Theorem Prover
Venue: arXiv cs.LO 2001
Year: 2001

A step-by-step presentation of the code for a small theorem prover introduces theorem-proving techniques. The programming language used is Standard ML. The prover operates on a sequent calculus formulation of first-order logic, which is briefly explained. The implementation of unification and logical inference is shown. The prover is demonstrated on several small examples, including one that shows its limitations. The final part of the paper is a survey of contemporary research on interactive theorem proving.
Fixed-parameter tractability, definability, and model checking
Venue: arXiv cs.CC 2001
Year: 2001

In this article, we study parameterized complexity theory from the perspective of logic, or more specifically, descriptive complexity theory. We propose to consider parameterized model-checking problems for various fragments of first-order logic as generic parameterized problems and show how this approach can be useful in studying both fixed-parameter tractability and intractability. For example, we establish the equivalence between the model-checking for existential first-order logic, the homomorphism problem for relational structures, and the substructure isomorphism problem. Our main tractability result shows that model-checking for first-order formulas is fixed-parameter tractable when restricted to a class of input structures with an excluded minor. On the intractability side, for every t >= 0 we prove an equivalence between model-checking for first-order formulas with t quantifier alternations and the parameterized halting problem for alternating Turing machines with t alternations. We discuss the close connection between this alternation hierarchy and Downey and Fellows' W-hierarchy. On a more abstract level, we consider two forms of definability, called Fagin definability and slicewise definability, that are appropriate for describing parameterized problems. We give a characterization of the class FPT of all fixed-parameter tractable problems in terms of slicewise definability in finite variable least fixed-point logic, which is reminiscent of the Immerman-Vardi Theorem characterizing the class PTIME in terms of definability in least fixed-point logic.
On the Average Similarity Degree between Solutions of Random k-SAT and Random CSPs
Venue: arXiv cs.AI 2002
Year: 2002

To study the structure of solutions for random k-SAT and random CSPs, this paper introduces the concept of average similarity degree to characterize how solutions are similar to each other. It is proved that under certain conditions, as r (i.e. the ratio of constraints to variables) increases, the limit of average similarity degree when the number of variables approaches infinity exhibits phase transitions at a threshold point, shifting from a smaller value to a larger value abruptly. For random k-SAT this phenomenon will occur when k>4 . It is further shown that this threshold point is also a singular point with respect to r in the asymptotic estimate of the second moment of the number of solutions. Finally, we discuss how this work is helpful to understand the hardness of solving random instances and a possible application of it to the design of search algorithms.