OpenRaiser/Intern-Atlas huggingface dataset:
P-model Alternative to the T-model
Venue: arXiv cs.CL 2001
Year: 2001

Standard linguistic analysis of syntax uses the T-model. This model requires the ordering: D-structure $>$ S-structure $>$ LF. Between each of these representations there is movement which alters the order of the constituent words; movement is achieved using the principles and parameters of syntactic theory. Psychological serial models do not accommodate the T-model immediately so that here a new model called the P-model is introduced. Here it is argued that the LF representation should be replaced by a variant of Frege's three qualities. In the F-representation the order of elements is not necessarily the same as that in LF and it is suggested that the correct ordering is: F-representation $>$ D-structure $>$ S-structure. Within this framework movement originates as the outcome of emphasis applied to the sentence.
Tiling with bars under tomographic constraints
Venue: arXiv cs.DS 2001
Year: 2001

We wish to tile a rectangle or a torus with only vertical and horizontal bars of a given length, such that the number of bars in every column and row equals given numbers. We present results for particular instances and for a more general problem, while leaving open the initial problem.
Super Logic Programs
Venue: arXiv cs.AI 2002
Year: 2002

The Autoepistemic Logic of Knowledge and Belief (AELB) is a powerful nonmonotic formalism introduced by Teodor Przymusinski in 1994. In this paper, we specialize it to a class of theories called `super logic programs'. We argue that these programs form a natural generalization of standard logic programs. In particular, they allow disjunctions and default negation of arbibrary positive objective formulas. Our main results are two new and powerful characterizations of the static semant ics of these programs, one syntactic, and one model-theoretic. The syntactic fixed point characterization is much simpler than the fixed point construction of the static semantics for arbitrary AELB theories. The model-theoretic characterization via Kripke models allows one to construct finite representations of the inherently infinite static expansions. Both characterizations can be used as the basis of algorithms for query answering under the static semantics. We describe a query-answering interpreter for super programs which we developed based on the model-theoretic characterization and which is available on the web.
The Role of Institutions in the Design of Communication Technologies
Venue: arXiv cs.CY 2002
Year: 2002

Communication technologies contain embedded values that affect our society's fundamental values, such as privacy, freedom of speech, and the protection of intellectual property. Researchers have shown the design of technologies is not autonomous but shaped by conflicting social groups. Consequently, communication technologies contain different values when designed by different social groups. Continuing in this vein, we show that the institutions where communication technologies are designed and developed are an important source of the values of communication technologies. We use the term code to collectively refer to the hardware and software of communication technologies. Institutions differ in their motivations, structure, and susceptibility to external influences. First, we focus on the political, economic, social, and legal influences during the development of code. The institutional reactions to these influences are embodied in code. Second, we focus on the decision-making issues in the review process for code. This process determines the code's content and affects the dissemination of code through the decision whether to publicly release the code. We found these factors vary by institution. As a result, institutions differ in the values that they incorporate into code or communications technologies.
Nonorthogonal Polyhedra Built from Rectangles
Venue: arXiv cs.CG 2002
Year: 2002

We prove that any polyhedron of genus zero or genus one built out of rectangular faces must be an orthogonal polyhedron, but that there are nonorthogonal polyhedra of genus seven all of whose faces are rectangles. This leads to a resolution of a question posed by Biedl, Lubiw, and Sun [BLS99].
Incremental Construction of Compact Acyclic NFAs
Venue: arXiv cs.DS 2002
Year: 2002

This paper presents and analyzes an incremental algorithm for the construction of Acyclic Non-deterministic Finite-state Automata (NFA). Automata of this type are quite useful in computational linguistics, especially for storing lexicons. The proposed algorithm produces compact NFAs, i.e. NFAs that do not contain equivalent states. Unlike Deterministic Finite-state Automata (DFA), this property is not sufficient to ensure minimality, but still the resulting NFAs are considerably smaller than the minimal DFAs for the same languages.
Trust enhancement by multiple random beacons
Venue: arXiv cs.CR 2002
Year: 2002

Random beacons-information sources that broadcast a stream of random digits unknown by anyone beforehand-are useful for various cryptographic purposes. But such beacons can be easily and undetectably sabotaged, so that their output is known beforehand by a dishonest party, who can use this information to defeat the cryptographic protocols supposedly protected by the beacon. We explore a strategy to reduce this hazard by combining the outputs from several noninteracting (eg spacelike-separated) beacons by XORing them together to produce a single digit stream which is more trustworthy than any individual beacon, being random and unpredictable if at least one of the contributing beacons is honest. If the contributing beacons are not spacelike separated, so that a dishonest beacon can overhear and adapt to earlier outputs of other beacons, the beacons' trustworthiness can still be enhanced to a lesser extent by a time sharing strategy. We point out some disadvantages of alternative trust amplification methods based on one-way hash functions.
A Backward Analysis for Constraint Logic Programs
Venue: arXiv cs.PL 2002
Year: 2002

One recurring problem in program development is that of understanding how to re-use code developed by a third party. In the context of (constraint) logic programming, part of this problem reduces to figuring out how to query a program. If the logic program does not come with any documentation, then the programmer is forced to either experiment with queries in an ad hoc fashion or trace the control-flow of the program (backward) to infer the modes in which a predicate must be called so as to avoid an instantiation error. This paper presents an abstract interpretation scheme that automates the latter technique. The analysis presented in this paper can infer moding properties which if satisfied by the initial query, come with the guarantee that the program and query can never generate any moding or instantiation errors. Other applications of the analysis are discussed. The paper explains how abstract domains with certain computational properties (they condense) can be used to trace control-flow backward (right-to-left) to infer useful properties of initial queries. A correctness argument is presented and an implementation is reported.
Computing Preferred Answer Sets by Meta-Interpretation in Answer Set Programming
Venue: arXiv cs.LO 2002
Year: 2002

Most recently, Answer Set Programming (ASP) is attracting interest as a new paradigm for problem solving. An important aspect which needs to be supported is the handling of preferences between rules, for which several approaches have been presented. In this paper, we consider the problem of implementing preference handling approaches by means of meta-interpreters in Answer Set Programming. In particular, we consider the preferred answer set approaches by Brewka and Eiter, by Delgrande, Schaub and Tompits, and by Wang, Zhou and Lin. We present suitable meta-interpreters for these semantics using DLV, which is an efficient engine for ASP. Moreover, we also present a meta-interpreter for the weakly preferred answer set approach by Brewka and Eiter, which uses the weak constraint feature of DLV as a tool for expressing and solving an underlying optimization problem. We also consider advanced meta-interpreters, which make use of graph-based characterizations and often allow for more efficient computations. Our approach shows the suitability of ASP in general and of DLV in particular for fast prototyping. This can be fruitfully exploited for experimenting with new languages and knowledge-representation formalisms.
An Empirical Model for Volatility of Returns and Option Pricing
Venue: arXiv cs.CE 2002
Year: 2002

In a seminal paper in 1973, Black and Scholes argued how expected distributions of stock prices can be used to price options. Their model assumed a directed random motion for the returns and consequently a lognormal distribution of asset prices after a finite time. We point out two problems with their formulation. First, we show that the option valuation is not uniquely determined; in particular, stratergies based on the delta-hedge and CAMP (Capital Asset Pricing Model) are shown to provide different valuations of an option. Second, asset returns are known not to be Gaussian distributed. Empirically, distributions of returns are seen to be much better approximated by an exponential distribution. This exponential distribution of asset prices can be used to develop a new pricing model for options that is shown to provide valuations that agree very well with those used by traders. We show how the Fokker-Planck formulation of fluctuations (i.e., the dynamics of the distribution) can be modified to provide an exponential distribution for returns. We also show how a singular volatility can be used to go smoothly from exponential to Gaussian returns and thereby illustrate why exponential returns cannot be reached perturbatively starting from Gaussian ones, and explain how the theory of 'stochastic volatility' can be obtained from our model by making a bad approximation. Finally, we show how to calculate put and call prices for a stretched exponential density.
Secure History Preservation Through Timeline Entanglement
Venue: arXiv cs.DC 2002
Year: 2002

A secure timeline is a tamper-evident historic record of the states through which a system goes throughout its operational history. Secure timelines can help us reason about the temporal ordering of system states in a provable manner. We extend secure timelines to encompass multiple, mutually distrustful services, using timeline entanglement. Timeline entanglement associates disparate timelines maintained at independent systems, by linking undeniably the past of one timeline to the future of another. Timeline entanglement is a sound method to map a time step in the history of one service onto the timeline of another, and helps clients of entangled services to get persistent temporal proofs for services rendered that survive the demise or non-cooperation of the originating service. In this paper we present the design and implementation of Timeweave, our service development framework for timeline entanglement based on two novel disk-based authenticated data structures. We evaluate Timeweave's performance characteristics and show that it can be efficiently deployed in a loosely-coupled distributed system of a few hundred services with overhead of roughly 2-8% of the processing resources of a PC-grade system.
Using parametric set constraints for locating errors in CLP programs
Venue: arXiv cs.PL 2002
Year: 2002

This paper introduces a framework of parametric descriptive directional types for constraint logic programming (CLP). It proposes a method for locating type errors in CLP programs and presents a prototype debugging tool. The main technique used is checking correctness of programs w.r.t. type specifications. The approach is based on a generalization of known methods for proving correctness of logic programs to the case of parametric specifications. Set-constraint techniques are used for formulating and checking verification conditions for (parametric) polymorphic type specifications. The specifications are expressed in a parametric extension of the formalism of term grammars. The soundness of the method is proved and the prototype debugging tool supporting the proposed approach is illustrated on examples. The paper is a substantial extension of the previous work by the same authors concerning monomorphic directional types.
The SDSS SkyServer: Public Access to the Sloan Digital Sky Server Data
Venue: arXiv cs.DL 2002
Year: 2002

The SkyServer provides Internet access to the public Sloan Digi-tal Sky Survey (SDSS) data for both astronomers and for science education. This paper describes the SkyServer goals and archi-tecture. It also describes our experience operating the SkyServer on the Internet. The SDSS data is public and well-documented so it makes a good test platform for research on database algorithms and performance.
Combinatorial Auctions with Decreasing Marginal Utilities
Venue: arXiv cs.GT 2002
Year: 2002

In most of microeconomic theory, consumers are assumed to exhibit decreasing marginal utilities. This paper considers combinatorial auctions among such submodular buyers. The valuations of such buyers are placed within a hierarchy of valuations that exhibit no complementarities, a hierarchy that includes also OR and XOR combinations of singleton valuations, and valuations satisfying the gross substitutes property. Those last valuations are shown to form a zero-measure subset of the submodular valuations that have positive measure. While we show that the allocation problem among submodular valuations is NP-hard, we present an efficient greedy 2-approximation algorithm for this case and generalize it to the case of limited complementarities. No such approximation algorithm exists in a setting allowing for arbitrary complementarities. Some results about strategic aspects of combinatorial auctions among players with decreasing marginal utilities are also presented.
Truth Revelation in Approximately Efficient Combinatorial Auctions
Venue: arXiv cs.GT 2002
Year: 2002

Some important classical mechanisms considered in Microeconomics and Game Theory require the solution of a difficult optimization problem. This is true of mechanisms for combinatorial auctions, which have in recent years assumed practical importance, and in particular of the gold standard for combinatorial auctions, the Generalized Vickrey Auction (GVA). Traditional analysis of these mechanisms - in particular, their truth revelation properties - assumes that the optimization problems are solved precisely. In reality, these optimization problems can usually be solved only in an approximate fashion. We investigate the impact on such mechanisms of replacing exact solutions by approximate ones. Specifically, we look at a particular greedy optimization method. We show that the GVA payment scheme does not provide for a truth revealing mechanism. We introduce another scheme that does guarantee truthfulness for a restricted class of players. We demonstrate the latter property by identifying natural properties for combinatorial auctions and showing that, for our restricted class of players, they imply that truthful strategies are dominant. Those properties have applicability beyond the specific auction studied.
Equivalence and Isomorphism for Boolean Constraint Satisfaction
Venue: arXiv cs.CC 2002
Year: 2002

A Boolean constraint satisfaction instance is a conjunction of constraint applications, where the allowed constraints are drawn from a fixed set B of Boolean functions. We consider the problem of determining whether two given constraint satisfaction instances are equivalent and prove a Dichotomy Theorem by showing that for all sets C of allowed constraints, this problem is either polynomial-time solvable or coNP-complete, and we give a simple criterion to determine which case holds. A more general problem addressed in this paper is the isomorphism problem, the problem of determining whether there exists a renaming of the variables that makes two given constraint satisfaction instances equivalent in the above sense. We prove that this problem is coNP-hard if the corresponding equivalence problem is coNP-hard, and polynomial-time many-one reducible to the graph isomorphism problem in all other cases.
Two results for proiritized logic programming
Venue: arXiv cs.AI 2002
Year: 2002

Prioritized default reasoning has illustrated its rich expressiveness and flexibility in knowledge representation and reasoning. However, many important aspects of prioritized default reasoning have yet to be thoroughly explored. In this paper, we investigate two properties of prioritized logic programs in the context of answer set semantics. Specifically, we reveal a close relationship between mutual defeasibility and uniqueness of the answer set for a prioritized logic program. We then explore how the splitting technique for extended logic programs can be extended to prioritized logic programs. We prove splitting theorems that can be used to simplify the evaluation of a prioritized logic program under certain conditions.
Dimension in Complexity Classes
Venue: arXiv cs.CC 2002
Year: 2002

A theory of resource-bounded dimension is developed using gales, which are natural generalizations of martingales. When the resource bound Δ(a parameter of the theory) is unrestricted, the resulting dimension is precisely the classical Hausdorff dimension (sometimes called fractal dimension). Other choices of the parameter Δyield internal dimension theories in E, E2, ESPACE, and other complexity classes, and in the class of all decidable problems. In general, if C is such a class, then every set X of languages has a dimension in C, which is a real number dim(X|C) in [0,1]. Along with the elements of this theory, two preliminary applications are presented: 1. For every real number αin (0,1/2), the set FREQ(<=α), consisting of all languages that asymptotically contain at most αof all strings, has dimension H(α) -- the binary entropy of α-- in E and in E2. 2. For every real number αin (0,1), the set SIZE(α* (2^n)/n), consisting of all languages decidable by Boolean circuits of at most α*(2^n)/n gates, has dimension αin ESPACE.
The Dimensions of Individual Strings and Sequences
Venue: arXiv cs.CC 2002
Year: 2002

A constructive version of Hausdorff dimension is developed using constructive supergales, which are betting strategies that generalize the constructive supermartingales used in the theory of individual random sequences. This constructive dimension is used to assign every individual (infinite, binary) sequence S a dimension, which is a real number dim(S) in the interval [0,1]. Sequences that are random (in the sense of Martin-Lof) have dimension 1, while sequences that are decidable, Σ^0_1, or Π^0_1 have dimension 0. It is shown that for every Δ^0_2-computable real number αin [0,1] there is a Δ^0_2 sequence S such that \dim(S) = α. A discrete version of constructive dimension is also developed using termgales, which are supergale-like functions that bet on the terminations of (finite, binary) strings as well as on their successive bits. This discrete dimension is used to assign each individual string w a dimension, which is a nonnegative real number dim(w). The dimension of a sequence is shown to be the limit infimum of the dimensions of its prefixes. The Kolmogorov complexity of a string is proven to be the product of its length and its dimension. This gives a new characterization of algorithmic information and a new proof of Mayordomo's recent theorem stating that the dimension of a sequence is the limit infimum of the average Kolmogorov complexity of its first n bits. Every sequence that is random relative to any computable sequence of coin-toss biases that converge to a real number βin (0,1) is shown to have dimension \H(β), the binary entropy of β.
Creating Annotation Tools with the Annotation Graph Toolkit
Venue: arXiv cs.CL 2002
Year: 2002

The Annotation Graph Toolkit is a collection of software supporting the development of annotation tools based on the annotation graph model. The toolkit includes application programming interfaces for manipulating annotation graph data and for importing data from other formats. There are interfaces for the scripting languages Tcl and Python, a database interface, specialized graphical user interfaces for a variety of annotation tasks, and several sample applications. This paper describes all the toolkit components for the benefit of would-be application developers.
Solitaire Clobber
Venue: arXiv cs.DM 2002
Year: 2002

Clobber is a new two-player board game. In this paper, we introduce the one-player variant Solitaire Clobber where the goal is to remove as many stones as possible from the board by alternating white and black moves. We show that a checkerboard configuration on a single row (or single column) can be reduced to about n/4 stones. For boards with at least two rows and two columns, we show that a checkerboard configuration can be reduced to a single stone if and only if the number of stones is not a multiple of three, and otherwise it can be reduced to two stones. We also show that in general it is NP-complete to decide whether an arbitrary Clobber configuration can be reduced to a single stone.
Factual and Legal Risks regarding wireless Computer Networks
Venue: arXiv cs.CY 2002
Year: 2002

The IEEE 802.11b wireless ethernet standart has several serious security flaws. This paper describes this flaws, surveys wireless networks in the Cologne/Bonn area to get an assessment of the security configurations of fielded networks and analizes the legal protections provided to wireless ethernet operators by german law. We conclude that wireless ethernets without additional security measures are not usable for any transmissions which are not meant for a public audience.
Annotation Graphs and Servers and Multi-Modal Resources: Infrastructure for Interdisciplinary Education, Research and Development
Venue: arXiv cs.CL 2002
Year: 2002

Annotation graphs and annotation servers offer infrastructure to support the analysis of human language resources in the form of time-series data such as text, audio and video. This paper outlines areas of common need among empirical linguists and computational linguists. After reviewing examples of data and tools used or under development for each of several areas, it proposes a common framework for future tool development, data annotation and resource sharing based upon annotation graphs and servers.
Semantic Component Composition
Venue: arXiv cs.SE 2002
Year: 2002

Building complex software systems necessitates the use of component-based architectures. In theory, of the set of components needed for a design, only some small portion of them are "custom"; the rest are reused or refactored existing pieces of software. Unfortunately, this is an idealized situation. Just because two components should work together does not mean that they will work together. The "glue" that holds components together is not just technology. The contracts that bind complex systems together implicitly define more than their explicit type. These "conceptual contracts" describe essential aspects of extra-system semantics: e.g., object models, type systems, data representation, interface action semantics, legal and contractual obligations, and more. Designers and developers spend inordinate amounts of time technologically duct-taping systems to fulfill these conceptual contracts because system-wide semantics have not been rigorously characterized or codified. This paper describes a formal characterization of the problem and discusses an initial implementation of the resulting theoretical system.