title: Propositional satisfiability in answer-set programming

abstract:
  We show that propositional logic and its extensions can support answer-set
programming in the same way stable logic programming and disjunctive logic
programming do. To this end, we introduce a logic based on the logic of
propositional schemata and on a version of the Closed World Assumption. We call
it the extended logic of propositional schemata with CWA (PS+, in symbols). An
important feature of this logic is that it supports explicit modeling of
constraints on cardinalities of sets. In the paper, we characterize the class
of problems that can be solved by finite PS+ theories. We implement a
programming system based on the logic PS+ and design and implement a solver for
processing theories in PS+. We present encouraging performance results for our
approach --- we show it to be competitive with smodels, a state-of-the-art
answer-set programming system based on stable logic programming.


title:
aspps --- an implementation of answer-set programming with propositional
  schemata

abstract:
  We present an implementation of an answer-set programming paradigm, called
aspps (short for answer-set programming with propositional schemata). The
system aspps is designed to process PS+ theories. It consists of two basic
modules. The first module, psgrnd, grounds an PS+ theory. The second module,
referred to as aspps, is a solver. It computes models of ground PS+ theories.


title: Reconciliation of a Quantum-Distributed Gaussian Key

abstract:
  Two parties, Alice and Bob, wish to distill a binary secret key out of a list
of correlated variables that they share after running a quantum key
distribution protocol based on continuous-spectrum quantum carriers. We present
a novel construction that allows the legitimate parties to get equal bit
strings out of correlated variables by using a classical channel, with as few
leaked information as possible. This opens the way to securely correcting
non-binary key elements. In particular, the construction is refined to the case
of Gaussian variables as it applies directly to recent continuous-variable
protocols for quantum key distribution.


title: The Complexity of Clickomania

abstract:
  We study a popular puzzle game known variously as Clickomania and Same Game.
Basically, a rectangular grid of blocks is initially colored with some number
of colors, and the player repeatedly removes a chosen connected monochromatic
group of at least two square blocks, and any blocks above it fall down. We show
that one-column puzzles can be solved, i.e., the maximum possible number of
blocks can be removed, in linear time for two colors, and in polynomial time
for an arbitrary number of colors. On the other hand, deciding whether a puzzle
is solvable (all blocks can be removed) is NP-complete for two columns and five
colors, or five columns and three colors.


title: Coupled Clustering: a Method for Detecting Structural Correspondence

abstract:
  This paper proposes a new paradigm and computational framework for
identification of correspondences between sub-structures of distinct composite
systems. For this, we define and investigate a variant of traditional data
clustering, termed coupled clustering, which simultaneously identifies
corresponding clusters within two data sets. The presented method is
demonstrated and evaluated for detecting topical correspondences in textual
corpora.


title: Yet another zeta function and learning

abstract:
  We study the convergence speed of the batch learning algorithm, and compare
its speed to that of the memoryless learning algorithm and of learning with
memory (as analyzed in joint work with N. Komarova). We obtain precise results
and show in particular that the batch learning algorithm is never worse than
the memoryless learning algorithm (at least asymptotically). Its performance
vis-a-vis learning with full memory is less clearcut, and depends on
certainprobabilistic assumptions. These results necessitate theintroduction of
the moment zeta function of a probability distribution and the study of some of
its properties.


title: NEOS Server 4.0 Administrative Guide

abstract:
  The NEOS Server 4.0 provides a general Internet-based client/server as a link
between users and software applications. The administrative guide covers the
fundamental principals behind the operation of the NEOS Server, installation
and trouble-shooting of the Server software, and implementation details of
potential interest to a NEOS Server administrator. The guide also discusses
making new software applications available through the Server, including areas
of concern to remote solver administrators such as maintaining security,
providing usage instructions, and enforcing reasonable restrictions on jobs.
The administrative guide is intended both as an introduction to the NEOS Server
and as a reference for use when running the Server.


title:
Semantic Web Content Accessibility Guidelines for Current Research
  Information Systems (CRIS)

abstract:
  The most exciting challenge for CRIS is to create a service for research
information which should be wide-spread, distributed and actual like Google,
but at the same time structured, trusted, with a complex search and navigation
similar to today CRIS application. The core technology for such a "new" CRIS is
the semantic web technology to integrate database contents with HTML and XML
web pages for being provided to the research interested public. One (at the
moment the best) possible way is to use RDF (Resource Description Framework)
which is also recommended by the W3 consortium.


title: TeXmacs interfaces to Maxima, MuPAD and REDUCE

abstract:
  GNU TeXmacs is a free wysiwyg word processor providing an excellent
typesetting quality of texts and formulae. It can also be used as an interface
to Computer Algebra Systems (CASs). In the present work, interfaces to three
general-purpose CASs have been implemented.


title:
The Cactus Worm: Experiments with Dynamic Resource Discovery and
  Allocation in a Grid Environment

abstract:
  The ability to harness heterogeneous, dynamically available "Grid" resources
is attractive to typically resource-starved computational scientists and
engineers, as in principle it can increase, by significant factors, the number
of cycles that can be delivered to applications. However, new adaptive
application structures and dynamic runtime system mechanisms are required if we
are to operate effectively in Grid environments. In order to explore some of
these issues in a practical setting, we are developing an experimental
framework, called Cactus, that incorporates both adaptive application
structures for dealing with changing resource characteristics and adaptive
resource selection mechanisms that allow applications to change their resource
allocations (e.g., via migration) when performance falls outside specified
limits. We describe here the adaptive resource selection mechanisms and
describe how they are used to achieve automatic application migration to
"better" resources following performance degradation. Our results provide
insights into the architectural structures required to support adaptive
resource selection. In addition, we suggest that this "Cactus Worm" is an
interesting challenge problem for Grid computing.


title: Bounded Concurrent Timestamp Systems Using Vector Clocks

abstract:
  Shared registers are basic objects used as communication mediums in
asynchronous concurrent computation. A concurrent timestamp system is a higher
typed communication object, and has been shown to be a powerful tool to solve
many concurrency control problems. It has turned out to be possible to
construct such higher typed objects from primitive lower typed ones. The next
step is to find efficient constructions. We propose a very efficient wait-free
construction of bounded concurrent timestamp systems from 1-writer multireader
registers. This finalizes, corrects, and extends, a preliminary bounded
multiwriter construction proposed by the second author in 1986. That work
partially initiated the current interest in wait-free concurrent objects, and
introduced a notion of discrete vector clocks in distributed algorithms.


title: The Partial Evaluation Approach to Information Personalization

abstract:
  Information personalization refers to the automatic adjustment of information
content, structure, and presentation tailored to an individual user. By
reducing information overload and customizing information access,
personalization systems have emerged as an important segment of the Internet
economy. This paper presents a systematic modeling methodology - PIPE
(`Personalization is Partial Evaluation') - for personalization.
Personalization systems are designed and implemented in PIPE by modeling an
information-seeking interaction in a programmatic representation. The
representation supports the description of information-seeking activities as
partial information and their subsequent realization by partial evaluation, a
technique for specializing programs. We describe the modeling methodology at a
conceptual level and outline representational choices. We present two
application case studies that use PIPE for personalizing web sites and describe
how PIPE suggests a novel evaluation criterion for information system designs.
Finally, we mention several fundamental implications of adopting the PIPE model
for personalization and when it is (and is not) applicable.


title: Links tell us about lexical and semantic Web content

abstract:
  The latest generation of Web search tools is beginning to exploit hypertext
link information to improve ranking\cite{Brin98,Kleinberg98} and
crawling\cite{Menczer00,Ben-Shaul99etal,Chakrabarti99} algorithms. The hidden
assumption behind such approaches, a correlation between the graph structure of
the Web and its content, has not been tested explicitly despite increasing
research on Web topology\cite{Lawrence98,Albert99,Adamic99,Butler00}. Here I
formalize and quantitatively validate two conjectures drawing connections from
link information to lexical and semantic Web content. The clink-content
conjecture states that a page is similar to the pages that link to it, i.e.,
one can infer the lexical content of a page by looking at the pages that link
to it. I also show that lexical inferences based on link cues are quite
heterogeneous across Web communities. The link-cluster conjecture states that
pages about the same topic are clustered together, i.e., one can infer the
meaning of a page by looking at its neighbours. These results explain the
success of the newest search technologies and open the way for more dynamic and
scalable methods to locate information in a topic or user driven way.


title: A Bit of Progress in Language Modeling

abstract:
  In the past several years, a number of different language modeling
improvements over simple trigram models have been found, including caching,
higher-order n-grams, skipping, interpolated Kneser-Ney smoothing, and
clustering. We present explorations of variations on, or of the limits of, each
of these techniques, including showing that sentence mixture models may have
more potential. While all of these techniques have been studied separately,
they have rarely been studied in combination. We find some significant
interactions, especially with smoothing and clustering techniques. We compare a
combination of all techniques together to a Katz smoothed trigram model with no
count cutoffs. We achieve perplexity reductions between 38% and 50% (1 bit of
entropy), depending on training data size, as well as a word error rate
reduction of 8.9%. Our perplexity reductions are perhaps the highest reported
compared to a fair baseline. This is the extended version of the paper; it
contains additional details and proofs, and is designed to be a good
introduction to the state of the art in language modeling.


title: Classes for Fast Maximum Entropy Training

abstract:
  Maximum entropy models are considered by many to be one of the most promising
avenues of language modeling research. Unfortunately, long training times make
maximum entropy research difficult. We present a novel speedup technique: we
change the form of the model to use classes. Our speedup works by creating two
maximum entropy models, the first of which predicts the class of each word, and
the second of which predicts the word itself. This factoring of the model leads
to fewer non-zero indicator functions, and faster normalization, achieving
speedups of up to a factor of 35 over one of the best previous techniques. It
also results in typically slightly lower perplexities. The same trick can be
used to speed training of other machine learning techniques, e.g. neural
networks, applied to any problem with a large number of outputs, such as
language modeling.


title: Abstract versus Concrete Computation on Metric Partial Algebras

abstract:
  A model of computation is abstract if, when applied to any algebra, the
resulting programs for computable functions and sets on that algebra are
invariant under isomorphisms, and hence do not depend on a representation for
the algebra. Otherwise it is concrete. Intuitively, concrete models depend on
the implementation of the algebra.
  The difference is particularly striking in the case of topological partial
algebras, and notably in algebras over the reals. We investigate the
relationship between abstract and concrete models of partial metric algebras.
In the course of this investigation, interesting aspects of continuity,
extensionality and non-determinism are uncovered.


title:
Using Methods of Declarative Logic Programming for Intelligent
  Information Agents

abstract:
  The search for information on the web is faced with several problems, which
arise on the one hand from the vast number of available sources, and on the
other hand from their heterogeneity. A promising approach is the use of
multi-agent systems of information agents, which cooperatively solve advanced
information-retrieval problems. This requires capabilities to address complex
tasks, such as search and assessment of sources, query planning, information
merging and fusion, dealing with incomplete information, and handling of
inconsistency. In this paper, our interest is in the role which some methods
from the field of declarative logic programming can play in the realization of
reasoning capabilities for information agents. In particular, we are interested
in how they can be used and further developed for the specific needs of this
application domain. We review some existing systems and current projects, which
address information-integration problems. We then focus on declarative
knowledge-representation methods, and review and evaluate approaches from logic
programming and nonmonotonic reasoning for information agents. We discuss
advantages and drawbacks, and point out possible extensions and open issues.


title: Artificial Neurons with Arbitrarily Complex Internal Structures

abstract:
  Artificial neurons with arbitrarily complex internal structure are
introduced. The neurons can be described in terms of a set of internal
variables, a set activation functions which describe the time evolution of
these variables and a set of characteristic functions which control how the
neurons interact with one another. The information capacity of attractor
networks composed of these generalized neurons is shown to reach the maximum
allowed bound. A simple example taken from the domain of pattern recognition
demonstrates the increased computational power of these neurons. Furthermore, a
specific class of generalized neurons gives rise to a simple transformation
relating attractor networks of generalized neurons to standard three layer
feed-forward networks. Given this correspondence, we conjecture that the
maximum information capacity of a three layer feed-forward network is 2 bits
per weight.


title: A Note on Tiling under Tomographic Constraints

abstract:
  Given a tiling of a 2D grid with several types of tiles, we can count for
every row and column how many tiles of each type it intersects. These numbers
are called the_projections_. We are interested in the problem of reconstructing
a tiling which has given projections. Some simple variants of this problem,
involving tiles that are 1x1 or 1x2 rectangles, have been studied in the past,
and were proved to be either solvable in polynomial time or NP-complete. In
this note we make progress toward a comprehensive classification of various
tiling reconstruction problems, by proving NP-completeness results for several
sets of tiles.


title: On Classes of Functions for which No Free Lunch Results Hold

abstract:
  In a recent paper it was shown that No Free Lunch results hold for any subset
F of the set of all possible functions from a finite set X to a finite set Y
iff F is closed under permutation of X. In this article, we prove that the
number of those subsets can be neglected compared to the overall number of
possible subsets. Further, we present some arguments why problem classes
relevant in practice are not likely to be closed under permutation.


title: A polynomial axles-detection algorithm for a four-contacts treadle

abstract:
  This submission was removed because it contained proprietary information that
was distributed without permission.


title:
Convergent Approximate Solving of First-Order Constraints by Approximate
  Quantifiers

abstract:
  Exactly solving first-order constraints (i.e., first-order formulas over a
certain predefined structure) can be a very hard, or even undecidable problem.
In continuous structures like the real numbers it is promising to compute
approximate solutions instead of exact ones. However, the quantifiers of the
first-order predicate language are an obstacle to allowing approximations to
arbitrary small error bounds. In this paper we solve the problem by modifying
the first-order language and replacing the classical quantifiers with
approximate quantifiers. These also have two additional advantages: First, they
are tunable, in the sense that they allow the user to decide on the trade-off
between precision and efficiency. Second, they introduce additional
expressivity into the first-order language by allowing reasoning over the size
of solution sets.


title:
What's Fit To Print: The Effect Of Ownership Concentration On Product
  Variety In Daily Newspaper Markets

abstract:
  This paper examines the effect of ownership concentration on product
position, product variety and readership in markets for daily newspapers. US
antitrust policy presumes that mergers reduce the amount and diversity of
content available to consumers. However, the effects of consolidation in
differentiated product markets cannot be determined solely from theory. Because
multi-product firms internalize business stealing, mergers may encourage firms
to reposition products, leading to more, not less, variety. Using data on
reporter assignments from 1993-1999, results show that differentiation and
variety increase with concentration. Moreover, there is evidence that
additional variety increases readership, suggesting that concentration benefits
consumers.


title:
Spiders and Crawlers and Bots, Oh My: The Economic Efficiency and Public
  Policy of Contracts that Restrict Data Collection

abstract:
  Recent trends reveal the search by companies for a legal hook to prevent the
undesired and unauthorized copying of information posted on websites. In the
center of this controversy are metasites, websites that display prices for a
variety of vendors. Metasites function by implementing shopbots, which extract
pricing data from other vendors' websites. Technological mechanisms have proved
unsuccessful in blocking shopbots, and in response, websites have asserted a
variety of legal claims. Two recent cases, which rely on the troublesome
trespass to chattels doctrine, suggest that contract law may provide a less
demanding legal method of preventing the search of websites by data robots. If
blocking collection of pricing data is as simple as posting an online contract,
the question arises whether this end result is desirable and legally viable.


title:
Verifying Sequential Consistency on Shared-Memory Multiprocessors by
  Model Checking

abstract:
  The memory model of a shared-memory multiprocessor is a contract between the
designer and programmer of the multiprocessor. The sequential consistency
memory model specifies a total order among the memory (read and write) events
performed at each processor. A trace of a memory system satisfies sequential
consistency if there exists a total order of all memory events in the trace
that is both consistent with the total order at each processor and has the
property that every read event to a location returns the value of the last
write to that location.
  Descriptions of shared-memory systems are typically parameterized by the
number of processors, the number of memory locations, and the number of data
values. It has been shown that even for finite parameter values, verifying
sequential consistency on general shared-memory systems is undecidable. We
observe that, in practice, shared-memory systems satisfy the properties of
causality and data independence. Causality is the property that values of read
events flow from values of write events. Data independence is the property that
all traces can be generated by renaming data values from traces where the
written values are distinct from each other. If a causal and data independent
system also has the property that the logical order of write events to each
location is identical to their temporal order, then sequential consistency can
be verified algorithmically. Specifically, we present a model checking
algorithm to verify sequential consistency on such systems for a finite number
of processors and memory locations and an arbitrary number of data values.


title: Security Considerations for Remote Electronic Voting over the Internet

abstract:
  This paper discusses the security considerations for remote electronic voting
in public elections. In particular, we examine the feasibility of running
national federal elections over the Internet. The focus of this paper is on the
limitations of the current deployed infrastructure in terms of the security of
the hosts and the Internet itself. We conclude that at present, our
infrastructure is inadequate for remote Internet voting.


title: Bipartite graph partitioning and data clustering

abstract:
  Many data types arising from data mining applications can be modeled as
bipartite graphs, examples include terms and documents in a text corpus,
customers and purchasing items in market basket analysis and reviewers and
movies in a movie recommender system. In this paper, we propose a new data
clustering method based on partitioning the underlying bipartite graph. The
partition is constructed by minimizing a normalized sum of edge weights between
unmatched pairs of vertices of the bipartite graph. We show that an approximate
solution to the minimization problem can be obtained by computing a partial
singular value decomposition (SVD) of the associated edge weight matrix of the
bipartite graph. We point out the connection of our clustering algorithm to
correspondence analysis used in multivariate analysis. We also briefly discuss
the issue of assigning data objects to multiple clusters. In the experimental
results, we apply our clustering algorithm to the problem of document
clustering to illustrate its effectiveness and efficiency.


title:
Scalable Unix Commands for Parallel Processors: A High-Performance
  Implementation

abstract:
  We describe a family of MPI applications we call the Parallel Unix Commands.
These commands are natural parallel versions of common Unix user commands such
as ls, ps, and find, together with a few similar commands particular to the
parallel environment. We describe the design and implementation of these
programs and present some performance results on a 256-node Linux cluster. The
Parallel Unix Commands are open source and freely available.


title: Flipping Cubical Meshes

abstract:
  We define and examine flip operations for quadrilateral and hexahedral
meshes, similar to the flipping transformations previously used in triangular
and tetrahedral mesh generation.


title: Computational Geometry Column 42

abstract:
  A compendium of thirty previously published open problems in computational
geometry is presented.


title: Portability of Syntactic Structure for Language Modeling

abstract:
  The paper presents a study on the portability of statistical syntactic
knowledge in the framework of the structured language model (SLM). We
investigate the impact of porting SLM statistics from the Wall Street Journal
(WSJ) to the Air Travel Information System (ATIS) domain. We compare this
approach to applying the Microsoft rule-based parser (NLPwin) for the ATIS data
and to using a small amount of data manually parsed at UPenn for gathering the
intial SLM statistics. Surprisingly, despite the fact that it performs modestly
in perplexity (PPL), the model initialized on WSJ parses outperforms the other
initialization methods based on in-domain annotated data, achieving a
significant 0.4% absolute and 7% relative reduction in word error rate (WER)
over a baseline system whose word error rate is 5.8%; the improvement measured
relative to the minimum WER achievable on the N-best lists we worked with is
12%.


title: Information Extraction Using the Structured Language Model

abstract:
  The paper presents a data-driven approach to information extraction (viewed
as template filling) using the structured language model (SLM) as a statistical
parser. The task of template filling is cast as constrained parsing using the
SLM. The model is automatically trained from a set of sentences annotated with
frame/slot labels and spans. Training proceeds in stages: first a constrained
syntactic parser is trained such that the parses on training data meet the
specified semantic spans, then the non-terminal labels are enriched to contain
semantic information and finally a constrained syntactic+semantic parser is
trained on the parse trees resulting from the previous stage. Despite the small
amount of training data used, the model is shown to outperform the slot level
accuracy of a simple semantic grammar authored manually for the MiPad ---
personal information management --- task.


title: Abstract Computability, Algebraic Specification and Initiality

abstract:
  computable functions are defined by abstract finite deterministic algorithms
on many-sorted algebras. We show that there exist finite universal algebraic
specifications that specify uniquely (up to isomorphism) (i) all abstract
computable functions on any many-sorted algebra; and (ii) all functions
effectively approximable by abstract computable functions on any metric
algebra.
  We show that there exist universal algebraic specifications for all the
classically computable functions on the set R of real numbers. The algebraic
specifications used are mainly bounded universal equations and conditional
equations. We investigate the initial algebra semantics of these
specifications, and derive situations where algebraic specifications define
precisely the computable functions.


title: Probabilistic asynchronous pi-calculus

abstract:
  We propose an extension of the asynchronous pi-calculus with a notion of
random choice. We define an operational semantics which distinguishes between
probabilistic choice, made internally by the process, and nondeterministic
choice, made externally by an adversary scheduler. This distinction will allow
us to reason about the probabilistic correctness of algorithms under certain
schedulers. We show that in this language we can solve the electoral problem,
which was proved not possible in the asynchronous $\pi$-calculus. Finally, we
show an implementation of the probabilistic asynchronous pi-calculus in a
Java-like language.


title: On the generalized dining philosophers problem

abstract:
  We consider a generalization of the dining philosophers problem to arbitrary
connection topologies. We focus on symmetric, fully distributed systems, and we
address the problem of guaranteeing progress and lockout-freedom, even in
presence of adversary schedulers, by using randomized algorithms. We show that
the well-known algorithms of Lehmann and Rabin do not work in the generalized
case, and we propose an alternative algorithm based on the idea of letting the
philosophers assign a random priority to their adjacent forks.


title: Parallel Computing on a PC Cluster

abstract:
  The tremendous advance in computer technology in the past decade has made it
possible to achieve the performance of a supercomputer on a very small budget.
We have built a multi-CPU cluster of Pentium PC capable of parallel
computations using the Message Passing Interface (MPI). We will discuss the
configuration, performance, and application of the cluster to our work in
physics.


title:
Architectural Framework for Large-Scale Multicast in Mobile Ad Hoc
  Networks

abstract:
  Emerging ad hoc networks are infrastructure-less networks consisting of
wireless devices with various power constraints, capabilities and mobility
characteristics. An essential capability in future ad hoc networks is the
ability to provide scalable multicast services. This paper presents a novel
adaptive architecture to support multicast services in large-scale wide-area ad
hoc networks. Existing works on multicast in ad hoc networks address only small
size networks. Our main design goals are scalability, robustness and
efficiency. We propose a self-configuring hierarchy extending zone-based
routing with the notion of contacts based on the small world graphs phenomenon
and new metrics of stability and mobility. We introduce a new geographic-based
multicast address allocation scheme coupled with adaptive anycast based on
group popularity. Our scheme is the first of its kind and promises efficient
and robust operation in the common case. Also, based on the new concept of
rendezvous regions, we provide a bootstrap mechanism for the multicast service;
a challenge generally ignored in previous work.


title: On Properties of Update Sequences Based on Causal Rejection

abstract:
  We consider an approach to update nonmonotonic knowledge bases represented as
extended logic programs under answer set semantics. New information is
incorporated into the current knowledge base subject to a causal rejection
principle enforcing that, in case of conflicts, more recent rules are preferred
and older rules are overridden. Such a rejection principle is also exploited in
other approaches to update logic programs, e.g., in dynamic logic programming
by Alferes et al. We give a thorough analysis of properties of our approach, to
get a better understanding of the causal rejection principle. We review
postulates for update and revision operators from the area of theory change and
nonmonotonic reasoning, and some new properties are considered as well. We then
consider refinements of our semantics which incorporate a notion of minimality
of change. As well, we investigate the relationship to other approaches,
showing that our approach is semantically equivalent to inheritance programs by
Buccafurri et al. and that it coincides with certain classes of dynamic logic
programs, for which we provide characterizations in terms of graph conditions.
Therefore, most of our results about properties of causal rejection principle
apply to these approaches as well. Finally, we deal with computational
complexity of our approach, and outline how the update semantics and its
refinements can be implemented on top of existing logic programming engines.


title: Voice vs Data: Estimates of Media Usage and Network Traffic

abstract:
  The popular conception is that data traffic nearly, if not already, exceeds
voice traffic on backbone networks. However, the results of research reported
in this paper imply that voice traffic greatly exceeds data traffic when real
users are asked to estimate their usage of a wide variety of media. Media usage
was surveyed for students in New York City and in Los Angeles. Other than
significant differences in radio listening, e-mails, and downloads, the usage
was quite similar. Telephone usage (wired and wireless) was nearly an hour per
day. When converted to bits, the telephone traffic was much greater than the
data traffic over the Internet. This paper reports on the details of the two
user studies. The traffic implications of the results are estimated. The
finding that voice exceeds data will then be reconciled with the popular
opposite conception.


title:
The Role of Incentives for Opening Monopoly Markets: Comparing GTE and
  BOC Cooperation with Local Entrants

abstract:
  While the 1996 Telecommunications Act requires all incumbent local telephone
companies to cooperate with local entrants, section 271 of the Act provides the
Bell companies (but not GTE) additional incentives to cooperate. Using an
original data set, I compare the negotiations of AT&T, as a local entrant, with
GTE and with the Bell companies in states where both operate. My results
suggest that the differential incentives matter: The Bells accommodate entry
more than does GTE, as evidenced in quicker agreements, less litigation, and
more favorable prices offered for network access. Consistent with this, there
is more entry into Bell territories


title: The Effect of Native Language on Internet Usage

abstract:
  Our goal is to distinguish between the following two hypotheses: (A) The
Internet will remain disproportionately in English and will, over time, cause
more people to learn English as second language and thus solidify the role of
English as a global language. This outcome will prevail even though there are
more native Chinese and Spanish speakers than there are native English
speakers. (B) As the Internet matures, it will more accurately reflect the
native languages spoken around the world (perhaps weighted by purchasing power)
and will not promote English as a global language.
  English's "early lead" on the web is more likely to persist if those who are
not native English speakers frequently access the large number of English
language web sites that are currently available. In that case, many existing
web sites will have little incentive to develop non-English versions of their
sites, and new sites will tend to gravitate towards English. The key empirical
question, therefore, is whether individuals whose native language is not
English use the Web, or certain types of Web sites, less than do native English
speakers. In order to examine this issue empirically, we employ a unique data
set on Internet use at the individual level in Canada from Media Metrix. Canada
provides an ideal setting to examine this issue because English is one of the
two official languages.
  Our preliminary results suggest that English web sites are not a barrier to
Internet use for French-speaking Quebecois. These preliminary results are
consistent with the scenario in which the Internet will promote English as a
global language.


title: Anaphora and Discourse Structure

abstract:
  We argue in this paper that many common adverbial phrases generally taken to
signal a discourse relation between syntactically connected units within
discourse structure, instead work anaphorically to contribute relational
meaning, with only indirect dependence on discourse structure. This allows a
simpler discourse structure to provide scaffolding for compositional semantics,
and reveals multiple ways in which the relational meaning conveyed by adverbial
connectives can interact with that associated with discourse structure. We
conclude by sketching out a lexicalised grammar for discourse that facilitates
discourse interpretation as a product of compositional rules, anaphor
resolution and inference.


title: Communication Complexity and Secure Function Evaluation

abstract:
  We suggest two new methodologies for the design of efficient secure
protocols, that differ with respect to their underlying computational models.
In one methodology we utilize the communication complexity tree (or branching
for f and transform it into a secure protocol. In other words, "any function f
that can be computed using communication complexity c can be can be computed
securely using communication complexity that is polynomial in c and a security
parameter". The second methodology uses the circuit computing f, enhanced with
look-up tables as its underlying computational model. It is possible to
simulate any RAM machine in this model with polylogarithmic blowup. Hence it is
possible to start with a computation of f on a RAM machine and transform it
into a secure protocol.
  We show many applications of these new methodologies resulting in protocols
efficient either in communication or in computation. In particular, we
exemplify a protocol for the "millionaires problem", where two participants
want to compare their values but reveal no other information. Our protocol is
more efficient than previously known ones in either communication or
computation.


title:
Is There a There There: Towards Greater Certainty for Internet
  Jurisdiction

abstract:
  The unique challenge presented by the Internet is that compliance with local
laws is rarely sufficient to assure a business that it has limited its exposure
to legal risk. The paper identifies why the challenge of adequately accounting
for the legal risk arising from Internet jurisdiction has been aggravated in
recent years by the adoption of the Zippo legal framework, commonly referred to
as the passive versus active test. The test provides parties with only limited
guidance and often results in detrimental judicial decisions from a policy
perspective. Given the inadequacies of the Zippo passive versus active test,
the paper argues that it is now fitting to identify a more effective standard
for determining when it is appropriate to assert jurisdiction in cases
involving predominantly Internet-based contacts. The solution submitted in the
paper is to move toward a targeting-based analysis. Unlike the Zippo approach,
a targeting analysis would seek to identify the intentions of the parties and
to assess the steps taken to either enter or avoid a particular jurisdiction.
Targeting would also lessen the reliance on effects-based analysis, the source
of considerable uncertainty since Internet-based activity can ordinarily be
said to create some effects in most jurisdictions. To identify the appropriate
criteria for a targeting test, the paper recommends returning to the core
jurisdictional principle -- foreseeability. Foreseeability in the targeting
context depends on three factors -- contracts, technology, and actual or
implied knowledge.


title: Conceptual Analysis of Lexical Taxonomies: The Case of WordNet Top-Level

abstract:
  In this paper we propose an analysis and an upgrade of WordNet's top-level
synset taxonomy. We briefly review WordNet and identify its main semantic
limitations. Some principles from a forthcoming OntoClean methodology are
applied to the ontological analysis of WordNet. A revised top-level taxonomy is
proposed, which is meant to be more conceptually rigorous, cognitively
transparent, and efficiently exploitable in several applications.


title:
Assigning Satisfaction Values to Constraints: An Algorithm to Solve
  Dynamic Meta-Constraints

abstract:
  The model of Dynamic Meta-Constraints has special activity constraints which
can activate other constraints. It also has meta-constraints which range over
other constraints. An algorithm is presented in which constraints can be
assigned one of five different satisfaction values, which leads to the
assignment of domain values to the variables in the CSP. An outline of the
model and the algorithm is presented, followed by some initial results for two
problems: a simple classic CSP and the Car Configuration Problem. The algorithm
is shown to perform few backtracks per solution, but to have overheads in the
form of historical records required for the implementation of state.


title: Boosting Trees for Anti-Spam Email Filtering

abstract:
  This paper describes a set of comparative experiments for the problem of
automatically filtering unwanted electronic mail messages. Several variants of
the AdaBoost algorithm with confidence-rated predictions [Schapire & Singer,
99] have been applied, which differ in the complexity of the base learners
considered. Two main conclusions can be drawn from our experiments: a) The
boosting-based methods clearly outperform the baseline learning algorithms
(Naive Bayes and Induction of Decision Trees) on the PU1 corpus, achieving very
high levels of the F1 measure; b) Increasing the complexity of the base
learners allows to obtain better ``high-precision'' classifiers, which is a
very important issue when misclassification costs are considered.


title:
Communications Convergence, Spectrum Use and Regulatory Constraints, Or
  Property Rights, Flexible Spectrum Use and Satellite v. Terrestrial Uses and
  Users

abstract:
  As far as many consumers and businessmen and women are concerned,
increasingly wireline and wireless services, including those provided by
terrestrial and satellite systems, are considered to be substitutes and
sometimes complements, regardless of the laws and regulations applicable to
them. At the same time, many writers and even government agencies (such as the
FCC) have suggested that users of the spectrum should be given more
property-like rights in the use of the spectrum and at a minimum should be
given much more flexibility in how they may use the spectrum. Two recent
developments have important implications with respect to "convergence,"
spectrum property rights and flexible use of the spectrum. The first
development involves several proposals to provide terrestrial wireless services
within spectrum in use or planned to be used to provide satellite services. The
second development is the passage of the 2000 ORBIT Act which specifically
forbids the use of license auctions to select among mutually exclusive
applicants to provide international or global satellite communications service.
The purpose of this paper is to discuss some of the questions raised by these
two events, but not necessarily to provide definitive answers or solutions.


title: Learning from the Success of MPI

abstract:
  The Message Passing Interface (MPI) has been extremely successful as a
portable way to program high-performance parallel computers. This success has
occurred in spite of the view of many that message passing is difficult and
that other approaches, including automatic parallelization and directive-based
parallelism, are easier to use. This paper argues that MPI has succeeded
because it addresses all of the important issues in providing a parallel
programming model.


title: Exact Complexity of Exact-Four-Colorability

abstract:
  Let $M_k \seq \nats$ be a given set that consists of $k$ noncontiguous
integers. Define $\exactcolor{M_k}$ to be the problem of determining whether
$\chi(G)$, the chromatic number of a given graph $G$, equals one of the $k$
elements of the set $M_k$ exactly. In 1987, Wagner \cite{wag:j:min-max} proved
that $\exactcolor{M_k}$ is $\bhlevel{2k}$-complete, where $M_k = \{6k+1, 6k+3,
>..., 8k-1 \}$ and $\bhlevel{2k}$ is the $2k$th level of the boolean hierarchy
over $\np$. In particular, for $k = 1$, it is DP-complete to determine whether
$\chi(G) = 7$, where $\DP = \bhlevel{2}$. Wagner raised the question of how
small the numbers in a $k$-element set $M_k$ can be chosen such that
$\exactcolor{M_k}$ still is $\bhlevel{2k}$-complete. In particular, for $k =
1$, he asked if it is DP-complete to determine whether $\chi(G) = 4$. In this
note, we solve this question of Wagner and determine the precise threshold $t
\in \{4, 5, 6, 7\}$ for which the problem $\exactcolor{\{t\}}$ jumps from NP to
DP-completeness: It is DP-complete to determine whether $\chi(G) = 4$, yet
$\exactcolor{\{3\}}$ is in $\np$. More generally, for each $k \geq 1$, we show
that $\exactcolor{M_k}$ is $\bhlevel{2k}$-complete for $M_k = \{3k+1, 3k+3,...,
5k-1\}$.


title: Tracing Execution of Software for Design Coverage

abstract:
  Test suites are designed to validate the operation of a system against
requirements. One important aspect of a test suite design is to ensure that
system operation logic is tested completely. A test suite should drive a system
through all abstract states to exercise all possible cases of its operation.
This is a difficult task. Code coverage tools support test suite designers by
providing the information about which parts of source code are covered during
system execution. Unfortunately, code coverage tools produce only source code
coverage information. For a test engineer it is often hard to understand what
the noncovered parts of the source code do and how they relate to requirements.
We propose a generic approach that provides design coverage of the executed
software simplifying the development of new test suites. We demonstrate our
approach on common design abstractions such as statecharts, activity diagrams,
message sequence charts and structure diagrams. We implement the design
coverage using Third Eye tracing and trace analysis framework. Using design
coverage, test suites could be created faster by focussing on untested design
elements.


title:
Modelling Semantic Association and Conceptual Inheritance for Semantic
  Analysis

abstract:
  Allowing users to interact through language borders is an interesting
challenge for information technology. For the purpose of a computer assisted
language learning system, we have chosen icons for representing meaning on the
input interface, since icons do not depend on a particular language. However, a
key limitation of this type of communication is the expression of articulated
ideas instead of isolated concepts. We propose a method to interpret sequences
of icons as complex messages by reconstructing the relations between concepts,
so as to build conceptual graphs able to represent meaning and to be used for
natural language sentence generation. This method is based on an electronic
dictionary containing semantic information.


title: Competing DNS Roots: Creative Destruction or Just Plain Destruction?

abstract:
  The Internet Domain Name System (DNS) is a hierarchical name space that
enables the assignment of unique, mnemonic identifiers to Internet hosts and
the consistent mapping of these names to IP addresses. The root of the domain
name system is the top of the hierarchy and is currently managed by a
quasi-private centralized regulatory authority, the Internet Corporation for
Assigned Names and Numbers (ICANN). This paper identifies and discusses the
economic and policy issues raised by competing DNS roots. The paper provides a
precise definition of root-competition and shows that multiple roots are a
species of standards competition, in which network externalities play a major
role. The paper performs a structural analysis of the different forms that
competing DNS roots can take and their effects on end-user compatibility. It
then explores the policy implications of the various forms of competition.
  The thesis of the paper is that root competition is caused by a severe
disjunction between the demand for and supply of top-level domain names. ICANN
has authorized a tiny number of new top-level domains (7) and subjected their
operators to excruciatingly slow and expensive contractual negotiations. The
growth of alternate DNS roots is an attempt to bypass that bottleneck. The
paper arrives at the policy conclusion that competition among DNS roots should
be permitted and is a healthy outlet for inefficiency or abuses of power by the
dominant root administrator.


title: Interactive Timetabling

abstract:
  Timetabling is a typical application of constraint programming whose task is
to allocate activities to slots in available resources respecting various
constraints like precedence and capacity. In this paper we present a basic
concept, a constraint model, and the solving algorithms for interactive
timetabling. Interactive timetabling combines automated timetabling (the
machine allocates the activities) with user interaction (the user can interfere
with the process of timetabling). Because the user can see how the timetabling
proceeds and can intervene this process, we believe that such approach is more
convenient than full automated timetabling which behaves like a black-box. The
contribution of this paper is twofold: we present a generic model to describe
timetabling (and scheduling in general) problems and we propose an interactive
algorithm for solving such problems.


title: Integrating Multiple Knowledge Sources for Robust Semantic Parsing

abstract:
  This work explores a new robust approach for Semantic Parsing of unrestricted
texts. Our approach considers Semantic Parsing as a Consistent Labelling
Problem (CLP), allowing the integration of several knowledge types (syntactic
and semantic) obtained from different sources (linguistic and statistic). The
current implementation obtains 95% accuracy in model identification and 72% in
case-role filling.


title: Verification of Timed Automata Using Rewrite Rules and Strategies

abstract:
  ELAN is a powerful language and environment for specifying and prototyping
deduction systems in a language based on rewrite rules controlled by
strategies. Timed automata is a class of continuous real-time models of
reactive systems for which efficient model-checking algorithms have been
devised. In this paper, we show that these algorithms can very easily be
prototyped in the ELAN system. This paper argues through this example that
rewriting based systems relying on rules and strategies are a good framework to
prototype, study and test rather efficiently symbolic model-checking
algorithms, i.e. algorithms which involve combination of graph exploration
rules, deduction rules, constraint solving techniques and decision procedures.


title: Dynamic Global Constraints: A First View

abstract:
  Global constraints proved themselves to be an efficient tool for modelling
and solving large-scale real-life combinatorial problems. They encapsulate a
set of binary constraints and using global reasoning about this set they filter
the domains of involved variables better than arc consistency among the set of
binary constraints. Moreover, global constraints exploit semantic information
to achieve more efficient filtering than generalised consistency algorithms for
n-ary constraints. Continued expansion of constraint programming (CP) to
various application areas brings new challenges for design of global
constraints. In particular, application of CP to advanced planning and
scheduling (APS) requires dynamic additions of new variables and constraints
during the process of constraint satisfaction and, thus, it would be helpful if
the global constraints could adopt new variables. In the paper, we give a
motivation for such dynamic global constraints and we describe a dynamic
version of the well-known alldifferent constraint.


title:
Conceptualising Regulatory Change - Explaining Shifts in
  Telecommunications Governance

abstract:
  Drawing on perspectives from telecommunications policy and neo-Gramscian
understandings of international political economy, this paper offers an
explanation and analysis of the shifting patterns of regulation which have been
evident in the telecommunications sector in recent years. It aims to illustrate
explain and explore the implications of the movement of regulatory sovereignty
away from the nation-state, through regional conduits, to global organisations
in the crystallisation of a world system of telecommunications governance.
  Our central argument is that telecommunications governance has evolved from a
regulatory arena characterised, in large part, by national diversity, to one
wherein a more convergent global multilayered system is emerging. We suggest
that the epicentre of this regulatory system is the relatively new World Trade
Organisation (WTO). Working in concert with the WTO are existing
well-established nodes regulation. In further complement, we see regional
regulatory projects, notably the European Union (EU), as important conduits and
nodes of regulation in the consolidation of a global regulatory regime.
  By way of procedure, we first explore the utility of a neo-Gramscian approach
for understanding the development of global regulatory frameworks. Second, we
survey something of the recent history - and, in extension, conventional wisdom
- of telecommunications regulation at national and regional levels. Third, we
demonstrate how a multilayered system of global telecommunications regulation
has emerged centred around the regulatory authority of the WTO. Finally, we
offer our concluding comments.


title: Routing Permutations in Partitioned Optical Passive Star Networks

abstract:
  It is shown that a POPS network with g groups and d processors per group can
efficiently route any permutation among the n=dg processors. The number of
slots used is optimal in the worst case, and is at most the double of the
optimum for all permutations p such that p(i)<>i for all i.


title: Random Walks in Routing Landscapes

abstract:
  In this paper we present a combinatorial optimisation view on the routing
problem for connectionless packet networks by using the metaphor of a
landscape. We examine the main properties of the routing landscapes as we
define them and how they can help us on the evaluation of the problem
difficulty and the generation of effective algorithms. We also present the
random walk statistical technique to evaluate the main properties of those
landscapes and a number of examples to demonstrate the use of the method.


title: Learning class-to-class selectional preferences

abstract:
  Selectional preference learning methods have usually focused on word-to-class
relations, e.g., a verb selects as its subject a given nominal class. This
papers extends previous statistical models to class-to-class preferences, and
presents a model that learns selectional preferences for classes of verbs. The
motivation is twofold: different senses of a verb may have different
preferences, and some classes of verbs can share preferences. The model is
tested on a word sense disambiguation task which uses subject-verb and
object-verb relationships extracted from a small sense-disambiguated corpus.


title: Knowledge Sources for Word Sense Disambiguation

abstract:
  Two kinds of systems have been defined during the long history of WSD:
principled systems that define which knowledge types are useful for WSD, and
robust systems that use the information sources at hand, such as, dictionaries,
light-weight ontologies or hand-tagged corpora. This paper tries to systematize
the relation between desired knowledge types and actual information sources. We
also compare the results for a wide range of algorithms that have been
evaluated on a common test setting in our research group. We hope that this
analysis will help change the shift from systems based on information sources
to systems based on knowledge sources. This study might also shed some light on
semi-automatic acquisition of desired knowledge types from existing resources.


title: Enriching WordNet concepts with topic signatures

abstract:
  This paper explores the possibility of enriching the content of existing
ontologies. The overall goal is to overcome the lack of topical links among
concepts in WordNet. Each concept is to be associated to a topic signature,
i.e., a set of related words with associated weights. The signatures can be
automatically constructed from the WWW or from sense-tagged corpora. Both
approaches are compared and evaluated on a word sense disambiguation task. The
results show that it is possible to construct clean signatures from the WWW
using some filtering techniques.


title:
The Internet, 1995-2000: Access, Civic Involvement, and Social
  Interaction

abstract:
  Our research, which began fielding surveys in 1995, and which have been
repeated with variation in 1996, 1997 and 2000, was apparently the first to use
national random telephone survey methods to track social and community aspects
of Internet use, and to compare users and non-users. It also seems to be among
the first that used these methods to compare users with non-users in regards to
communication, social and community issues. The work has been largely supported
by grants from the Markle Foundation of New York City as well as the Robert
Wood Johnson Foundation.
  Abridged, see full text for complete abstract.


title: CLP versus LS on Log-based Reconciliation Problems

abstract:
  Nomadic applications create replicas of shared objects that evolve
independently while they are disconnected. When reconnecting, the system has to
reconcile the divergent replicas. In the log-based approach to reconciliation,
such as in the IceCube system, the input is a common initial state and logs of
actions that were performed on each replica. The output is a consistent global
schedule that maximises the number of accepted actions. The reconciler merges
the logs according to the schedule, and replays the operations in the merged
log against the initial state, yielding to a reconciled common final state.
  In this paper, we show the NP-completeness of the log-based reconciliation
problem and present two programs for solving it. Firstly, a constraint logic
program (CLP) that uses integer constraints for expressing precedence
constraints, boolean constraints for expressing dependencies between actions,
and some heuristics for guiding the search. Secondly, a stochastic local search
method with Tabu heuristic (LS), that computes solutions in an incremental
fashion but does not prove optimality. One difficulty in the LS modeling lies
in the handling of both boolean variables and integer variables, and in the
handling of the objective function which differs from a max-CSP problem.
Preliminary evaluation results indicate better performance for the CLP program
which, on somewhat realistic benchmarks, finds nearly optimal solutions up to a
thousands of actions and proves optimality up to a hundreds of actions.


title:
Relevant Knowledge First - Reinforcement Learning and Forgetting in
  Knowledge Based Configuration

abstract:
  In order to solve complex configuration tasks in technical domains, various
knowledge based methods have been developed. However their applicability is
often unsuccessful due to their low efficiency. One of the reasons for this is
that (parts of the) problems have to be solved again and again, instead of
being "learnt" from preceding processes. However, learning processes bring with
them the problem of conservatism, for in technical domains innovation is a
deciding factor in competition. On the other hand a certain amount of
conservatism is often desired since uncontrolled innovation as a rule is also
detrimental. This paper proposes the heuristic RKF (Relevant Knowledge First)
for making decisions in configuration processes based on the so-called
relevance of objects in a knowledge base. The underlying relevance-function has
two components, one based on reinforcement learning and the other based on
forgetting (fading). Relevance of an object increases with its successful use
and decreases with age when it is not used. RKF has been developed to speed up
the configuration process and to improve the quality of the solutions relative
to the reward value that is given by users.


title:
Revenge of the Bell Heads: How the Net Heads Lost Control of the
  Internet

abstract:
  A dichotomy in regulatory treatment and corporate cultures exists between
Internet Service Providers (ISPs) and telecommunication carriers. Telephone
company executives (Bell Heads) may resent regulation, but they accept their
fate and work creatively to exploit anomalies and opportunities to secure a
regulation-conferred competitive advantage. Most ISP executives (Net Heads)
appear to embrace a libertarian attitude, strongly opposing any government
involvement. Despite the clash of cultures, the telecommunications and Internet
worlds have merged. Such convergence jeopardizes the ability of Net Heads to
avoid some degree of regulation, particularly when they offer services
functionally equivalent to what their Bell Head counterparts offer.
  This paper will assess the regulatory consequences when telecommunication and
Internet services converge in the marketplace and in terms of operating
technologies. The paper identifies commercial developments in the Internet to
support the view that the Internet has become more hierarchical and more like
telecommunication networks. The paper concludes that telecommunication carriers
will display superior skill in working the regulatory process to their
advantage. The paper suggests that Bell Heads will outmaneuver Net Heads
particularly when the revenue siphoning effect of Internet-mediated services
offsets the revenues generated from ISP leases of telecommunication
transmission capacity.


title: Competition and Price Dispersion in International Long Distance Calling

abstract:
  This paper examines the relationship between changes in telecommunications
provider concentration on international long distance routes and changes in
prices on those routes. Overall, decreased concentration is associated with
significantly lower prices to consumers of long distance services. However, the
relationship between concentration and price varies according to the type of
long distance plan considered. For the international flagship plans frequently
selected by more price-conscious consumers of international long distance,
increased competition on a route is associated with lower prices. In contrast,
for the basic international plans that are the default selection for consumers,
increased competition on a route is actually associated with higher prices.
Thus, somewhat surprisingly, price dispersion appears to increase as
competition increases.


title: Antitrust, Intellectual Property and Standard-Setting Organizations

abstract:
  Standard-setting organizations (SSOs) regularly encounter situations in which
one or more companies claim to own proprietary rights that cover a proposed
industry standard. The industry cannot adopt the standard without the
permission of the intellectual property owner (or owners).
  How SSOs respond to those who assert intellectual property rights is
critically important. Whether or not private companies retain intellectual
property rights in group standards will determine whether a standard is "open"
or "closed." It will determine who can sell compliant products, and it may well
influence whether the standard adopted in the market is one chosen by a group
or one offered by a single company. SSO rules governing intellectual property
rights will also affect how standards change as technology improves.
  Given the importance of SSO rules governing intellectual property rights,
there has been surprisingly little treatment of SSOs or their intellectual
property rules in the legal literature. My aim in this article is to fill that
void. To do so, I have surveyed the intellectual property policies of dozens of
SSOs, primarily but not exclusively in the computer networking and
telecommunications industries.


title: Crisis of Public Utility Deregulation and the Unrecognized Welfare State

abstract:
  Successful achievement of public policies requires satisfaction of conditions
affecting political feasibility for policy adoption and maintenance as well as
economic viability of the desired activity or enterprise. This paper discusses
the difficulties of satisfying these joint constraints given the legacy of the
common law doctrines of "just price" and "businesses affected with a public
interest." In this regard, it is helpful to view traditional public utility
regulation as a form of welfare state regulation, as it suffers from similar
political problems from policy retrenchment. The retrenchment problems are
examined in the context of the electricity crisis in California as well as the
passage and implementation of the Telecommunications Act of 1996. As expected,
retrenchment from low residential retail rates - the most universalistic
benefit for customers - faces the greatest political resistance. The societal
trade-offs between monopoly and competition must be reexamined in light of the
greater instability and political difficulties under a deregulatory regime.


title:
Testing for Mathematical Lineation in Jim Crace's "Quarantine" and T. S.
  Eliot's "Four Quartets"

abstract:
  The mathematical distinction between prose and verse may be detected in
writings that are not apparently lineated, for example in T. S. Eliot's "Burnt
Norton", and Jim Crace's "Quarantine". In this paper we offer comments on
appropriate statistical methods for such work, and also on the nature of formal
innovation in these two texts. Additional remarks are made on the roots of
lineation as a metrical form, and on the prose-verse continuum.


title: The Building of BODHI, a Bio-diversity Database System

abstract:
  We have recently built a database system called BODHI, intended to store
plant bio-diversity information. It is based on an object-oriented modeling
approach and is developed completely around public-domain software. The unique
feature of BODHI is that it seamlessly integrates diverse types of data,
including taxonomic characteristics, spatial distributions, and genetic
sequences, thereby spanning the entire range from molecular to organism-level
information. A variety of sophisticated indexing strategies are incorporated to
efficiently access the various types of data, and a rule-based query processor
is employed for optimizing query execution. In this paper, we report on our
experiences in building BODHI and on its performance characteristics for a
representative set of queries.


title: Open Access beyond cable: The case of Interactive TV

abstract:
  In this paper we analyze the development of interactive TV in the U.S. and
Western Europe. We argue that despite the nascent character of the market there
are important regulatory issues at stake, as exemplified by the AOL/TW merger
and the British Interactive Broadcasting case. Absent rules that provide for
non-discriminatory access to network components (including terminal equipment
specifications), dominant platform operators are likely to leverage ownership
of delivery infrastructure into market power over interactive TV services.
While integration between platform operator, service provider and terminal
vendor may facilitate the introduction of services in the short-term, the
lasting result will be a collection of fragmented "walled gardens" offering
limited content and applications. Would interactive TV develop under such
model, the exciting opportunities for broad-based innovation and extended
access to multiple information, entertainment and educational services opened
by the new generation of broadcasting technologies will be foregone


title:
Intelligent Search of Correlated Alarms from Database containing Noise
  Data

abstract:
  Alarm correlation plays an important role in improving the service and
reliability in modern telecommunications networks. Most previous research of
alarm correlation didn't consider the effect of noise data in Database. This
paper focuses on the method of discovering alarm correlation rules from
database containing noise data. We firstly define two parameters Win_freq and
Win_add as the measure of noise data and then present the Robust_search
algorithm to solve the problem. At different size of Win_freq and Win_add,
experiments with alarm data containing noise data show that the Robust_search
Algorithm can discover the more rules with the bigger size of Win_add. We also
experimentally compare two different interestingness measures of confidence and
correlation.


title:
PUC Autonomy and Policy Innovation: Local Telephone Competition in
  Arkansas and New York

abstract:
  In the pre-divestiture era, the regulatory environment in the U.S. was fairly
uniform and harmonious with the FCC setting the course and the accommodative
state PUCs making corresponding changes in their own policies. The divestiture
fractured this monolithic system as it forced the PUCs to respond to new forces
unleashed in their own backyards. Soon there was great diversity in the overall
regulatory landscape. Within this new environment, there is considerable
disparity among the PUCs in terms of their ability to implement new ideas. This
paper seeks to understand the structural factors that influence the latitude of
regulatory action by PUCs via a comparative study of local telephone
competition policy making in Arkansas and New York. The analysis suggests that
the presence or absence of countervailing forces determines the relative
autonomy the PUCs enjoy and thereby their ability to introduce new ideas into
their states.


title:
Analyzing ENUM Service and Administration from the Bottom Up: The
  addressing system for IP telephony and beyond

abstract:
  ENUM creates many new market opportunities and raises several important
policy issues related to the implementation and administration of the ENUM
database and services. Recent World Telecommunications Policy Forum 2001 dealt
with the emergence of ENUM as an important numbering issue of IP telephony.
This paper prepares some important emerging issues of ENUM administration and
policy by taking an empirical research approach from the bottom up.
  We will identify potential key ENUM services, and estimating the size of the
service market opportunities created by the availability of PSTN-IP addressing
and mapping mechanisms, particularly in the context of IP telephony. Also, we
analyze the possible administrative models and relationship scenarios among
different ENUM players such as Registry(ies), Registrars, Telephone Service
Providers, ENUM Application Service Providers, etc. Then, we will assess the
effects of various administrative model architectures of ENUM service by
looking at the market opportunities and motivations of the players. From the
empirical findings, we will draw the implications on transactions among
different kinds of ENUM service providers. Finally, the results of the model
analysis will be used for the discussion of policy related issues around the
ENUM and IP telephony services.
  Keywords: IP Telephony, ENUM, Internet Policy, Numbering and Addressing
System, Service and Market Study, Administration Model, Empirical Market Study.


title:
Product Cycle, Wintelism, and Cross-national Production Networks (CPN)
  for Developing Countries-- China's Telecom Manufacturing Industry as A Case

abstract:
  Focusing on the telecom manufacturing industry in China, this paper contends
that the existing literature needs to be expanded in order to explain the
Chinese case. First, product cycle theory could be applied to explain
multinational corporations' strategies of importing and localizing their
products in China in order to take advantage of lower labor costs and often
more significantly to break barriers to the Chinese market. Second, there are
no significant indicators pointing to local multinational subsidiaries and
indigenous manufacturers serving as a substantial part of the cross-national
production networks in the global telecom industry yet, although there are some
signs of potential development. Third, the success of "Wintelism" and the
maturity of cross-national production networks in the global market have had
significant impacts on China's indigenous industry.


title: Internet Radio: A New Engine for Content Diversity?

abstract:
  While traditional radio stations are subject to extensive government
regulations, Internet radio stations remain largely unregulated. As Internet
radio usage has increased certain stakeholders have begun to argue that these
Internet radio broadcasters are providing significant and diverse programming
to American audiences and that government regulation of spectrum-using radio
station ownership may be further relaxed.
  One of the primary justifications for regulation of ownership has been to
protect diversity in broadcasting. This study hypothesizes that Internet radio
broadcasting does add diversity to the radio broadcasting industry and that it
should be considered as relevant by regulators.
  This study evaluates the role of Internet radio broadcasters according to
five criteria intended to gauge the level of diversity being delivered to
listeners online. By measuring the levels of format, channel, ownership,
location and language diversity among Internet radio stations, it is possible
to draw benchmark lessons about the new medium's ability to provide Americans
with diverse broadcasting options.
  The study finds that Internet radio broadcasters are in fact adding
measurable diversity to the radio broadcasting industry. Internet broadcasters
are providing audiences with access to an increasing number of stations,
owners, formats, and language choices, and it is likely that technologies
aiding in the mobility of access as well as broadband evolution will reinforce
these findings.


title:
Between a rock and a hard place: assessing the application of domestic
  policy and South Africa's commitments under the WTO'S Basic
  Telecommunications Agreement

abstract:
  South Africa adopted the GATS Basic Agreement on Telecommunications and the
regulatory principles in 1998. Obligations undertaken by South Africa mirrored
the framework for the gradual telecommunications reform process that was begun
in 1996. In the light of two threatened actions for anti-competitive practices
in violation of the Agreement, this paper reviews the nature of the commitments
undertaken by South Africa and assesses the country's compliance to date. This
paper also seeks to explore the tension that arises between domestic policy
reforms and international trade aspirations. It is argued that the dynamic
produced through this tension affords domestic governments a mechanism with
which to balance the seemingly opposing goals of competition and development.
It is further argued that the broad regulatory principles, adopted by all
signatories and often criticized for lack of precision, facilitate this fine
balancing and affords domestic governments an opportunity to advance sovereign
concerns while pursuing international trade ideals.


title:
Competition and Commons: The Post-Telecom Act Public Interest, in and
  after the AOLTW Merger

abstract:
  In asserting a competitive market environment as a justification for
regulatory forbearance, the Telecommunications Act of 1996 finally articulated
a clear standard for the FCC's public interest standard, one of the most
protean concepts in communications. This seeming clarity has not, however,
inhibited intense political conflict over the term. This paper examines public
and regulatory debate over the AOL Time Warner merger as an example of the way
in which the linkage between competitions and commons policy becomes relevant
to communications policy, particularly in relation to mass media, and discusses
interpretations of the public interest in the current FCC. The paper proposes
that the Telecom Act's goal of fostering economic competition among information
service providers, and the democratic ideal of nurturing public relationships
and behaviors can be linked. Competition policy that creates the opportunity
for untrammeled interactivity also provides a sine qua non to nurture the
social phenomenon of the commons. The linked concepts of competition and
commons could also provide useful ways to interpret the public interest in
policy arenas as spectrum allocation and intellectual property.


title:
Signing Initiative Petitions Online: Possibilities, Problems and
  Prospects

abstract:
  Many people expect the Internet to change American politics, most likely in
the direction of increasing direct citizen participation and forcing government
officials to respond more quickly to voter concerns. A recent California
initiative with these objectives would authorize use of encrypted digital
signatures over the Internet to qualify candidates, initiatives, and other
ballot measures. Proponents of Internet signature gathering say it will
significantly lower the cost of qualifying initiatives and thereby reduce the
influence of organized, well-financed interest groups. They also believe it
will increase both public participation in the political process and public
understanding about specific measures. However, opponents question whether
Internet security is adequate to prevent widespread abuse and argue that the
measure would create disadvantages for those who lack access to the Internet.
Beyond issues of security, cost, and access lie larger questions about the
effects of Internet signature gathering on direct democracy. Would it encourage
greater and more informed public participation in the political process? Or
would it flood voters with ballot measures and generally worsen current
problems with the initiative process itself? Because we lack good data on these
questions, answers to them today are largely conjectural. We can be fairly
sure, however, that Internet petition signing, like Internet voting, will have
unintended consequences.


title:
A Framework for Assessing Universal Service Obligations: A Developing
  Country Perspective

abstract:
  A critical element of most national telecom policy objectives is advancing
universal service. In a multi-operator context, this is usually operationalized
through Universal Service Obligations (USO), by which various operators are
mandated to provide a part of their services to rural areas or to high cost to
serve customers at "affordable" prices.
  This paper highlights the various issues in USO from a developing country
perspective. The first part of this paper gives an overview of USO practices
and issues. The second part reviews the Telecom Regulatory Authority of India's
recommendations on USO cost estimation. In the third part, the paper analyzes
characteristics of rural exchanges with a view to evolve a framework for
assessing USO. This framework is applicable to developing countries as the
study carried out in this paper is in the context of a developing country
characterized by low telecom penetration and non-availability of data with
regulators.


title: Internet TV: Business Models and Program Content

abstract:
  Internet technology should eventually provide important improvements over
established media not only in the efficiency of broadband delivery, and of
particularimportance, in the efficiency of business models that can be used to
collect money for that programming. I identify five economic characteristics of
Internet technology that should lead to these greater efficiencies: (1) lower
delivery costs and reduced capacity constraints, (2) more efficient
interactivity, (3) more efficient advertising and sponsorship, (4) more
efficient direct pricing and bundling, and (5) lower costs of copying and
sharing.
  The most successful Internet TV business models are likely to involve
syndication to or from other media, and also international distribution. In the
broader context, Internet TV is another syndication outlet by which program
suppliers can segment their overall markets and thus support higher production
investments. Many innovative and more sharply focused programs will surely
prosper on Internet TV, but the attractiveness to audiences of high production
value programming will tend to advantage broad appeal programming, such as
Hollywood movies. Historical evidence about the performance of cable television
and videocassettes is presented to support these points.


title:
Globalization and Governance in Cyberspace: Mapping the Processes of
  Emergent Regime Formation in Global Information and Communications Policy

abstract:
  This paper develops a theoretical perspective on globalization and the
Information Society and combines it with a critical usage of international
regime theory as a heuristic for understanding the current historical period of
transition from an international telecommunicaitons regime (Cowhey, 1990; 1994)
to a new and complex regime aimed at providing governance for the Global
Information Infrastructure and Global Information Society (GII/GIS). In
analyzing the principles, values, norms, rules, collective decision-making
prdocedures, and enforcement mechanisms of the emergent GII/GIS regime, this
paper differentiates between three regime levels: (1) Macro-Regime--global; (2)
Mezzo-Regime--regional and sub-regional; and (3) Micro-Regime--national. The
paper employs a case-study approach to explore some of the specific national
responses (i.e. South Africa) to this regime transition, with an analysis of
potential best practices and lessons learned for other emerging economies. Key
findings in this paper are: (1) that a range of social, political, economic,
and technological factors are eroding the existing international
telecommunications regime (e.g., VOIP;, call-back, VSATs, accounting rate
restructuring, pressure for applicaitons development, and SMMEs); (2) a new
regime for global information and communicaitons policy is emerging, but is
being driven not by the broad possibilities of the Information Society, but by
the more specific interests of global and multi-national corporations related
to global e-commerce; (3) numerous strategic responses have been developed at
national, subregional, and regional levels to the challenges of this transition
in both developed and developing regions; and (4) without a collaborative
response, the developing world will be further marginalized by this new regime.


title: Price Increases from Online Privacy

abstract:
  Consumers value keeping some information about them private from potential
marketers. E-commerce dramatically increases the potential for marketers to
accumulate otherwise private information about potential customers. Online
marketers claim that this information enables them to better market their
products. Policy makers are currently drafting rules to regulate the way in
which these marketers can collect, store, and share this information. However,
there is little evidence yet either of consumers' valuation of their privacy or
of the benefits they might reap through better target marketing. We provide a
framework for measuring a portion of the benefits from allowing marketers to
make better use of consumer information. Target marketing is likely to reduce
consumer search costs, improve consumer product selection decisions, and lower
the marketing costs of goods sold. Our model allows us to estimate the value to
consumers of only the latter, price reductions from more efficient marketing.


title:
Monopoly Power on the Web - A Preliminary Investigation of Search
  Engines

abstract:
  E-Commerce challenges traditional approaches to assessing monopolistic
practices due to the rapid rate of growth, rapid change in technology,
difficulty in assessing market share for information products like web sites,
and high degree of interconnectivity and alliance formation among corporations.
This paper has provided a fundamental framework that integrates a network and
economic perspective to the search engine market.
  The findings indicate that (1) despite an increasing number of search
engines, barriers to entry seem high, largely due to the exponential growth in
the number of web sites and the non-scalability of the current search
technology and collective switching costs; (2) older search engine sites tend
typically to have more features to lock in users. Using standard economic
indicators (CR4=58% and HHI=1163), the industry looks close to being plagued by
anticompetitive practices. But based on a network adjusted HHI constructed in
this paper, its value, 870, suggests that there is less cause for concern.
  Based on all indicators, it suggests that Yahoo would be a contender. Other
possible contenders are MSN and Netscape. On the basis of results to date, some
search engines keep increasing their audience reach while others don't. The
trend shows that some search engines may dominate the search engine market. We
suggest conducting research in the coverage performance of search engines and
investigate "information search cost" as a performance indicator of search
techniques. In addition, we suggest paying attention to any anticompetitive
conduct (e.g. product bundling) that may lesson competition and reduce consumer
welfare. The combination of network theory and economic theory to study the
search engine market is a particularly powerful approach for E-Commerce.


title: Standardization versus Coverage in Wireless Telephone Networks

abstract:
  The issue of market-based versus mandated standards has been addressed in
many settings. In most settings in which network effects are present,
compatibility across platforms has been a key determinant of the success or
failure of a particular technology. In the case of wireless telecommunications,
however, interconnection and the availability of the relevant infrastructure
can be a substitute for compatibility.
  In this paper, we examine the tradeoff between mandated standards and
interconnection. We first provide institutional background; we then empirically
examine whether, other things being equal, penetration rates were lower (or
higher) for countries with multiple incompatible digital standards. We finally
discuss the implications of our results for the current debate about 3G
standards, in which CDMA2000, which is backed mainly by US firms, competes with
WCDMA, which is backed by the European Community.


title: Ideological and Policy Origins of the Internet, 1957-1969

abstract:
  This paper examines the ideological and policy consensus that shaped
computing research funded by the Information Processing Techniques Office
(IPTO) within the Department of Defense's Advanced Research Projects Agency
(ARPA). This historical case study of the period between Sputnik and the
creation of the ARPANET shows how military, scientific, and academic values
shaped the institutions and relations of a foundational period in the creation
of the Internet.
  The paper probes three areas: the ideology of the science policy consensus,
the institutional philosophy of IPTO under J. C. R. Licklider, and the ways
that this consensus and philosophy shaped IPTO research in the period leading
to the creation of the ARPANET. By examining the intellectual, cultural, and
institutional details of the consensus that governed IPTO research between 1957
and 1969, we can understand the ways that these values defined the range of
possibilities for network computing.
  The influence of the social values expressed by these actors was decisive:
that government had an obligation to support a broad base of scientific
research to promote both the public good and the national defense; that
IPTO-sponsored computing research would accomplish both military and scientific
objectives; and that IPTO could leverage its power within this consensus to
create a network to share resources and unite researchers over geographical
distance. A greater awareness of the ways that "consensus" worked in this
period -- the "pre-history" of the Internet -- provides a richer context for
evaluating the unique features of the Internet, such as its open architecture,
collegial culture, and standards-based governance.


title:
Do Switching Costs Make Markets More or Less Competitive?: The Case of
  800-Number Portability

abstract:
  Do switching costs reduce or intensify price competition in markets where
firms charge the same price to old and new consumers? Theoretically, the answer
could be either "yes" or "no," due to two opposing incentives in firms' pricing
decisions. The firm would like to charge a higher price to previous purchasers
who are "locked-in" and a lower price to unattached consumers who offer higher
future profitability. I demonstrate this ambiguity in an infinite-horizon
theoretical model.
  800- (toll-free) number portability provides empirical evidence to answer
this question. Before portability, a customer had to change numbers to change
service providers. This imposed significant switching costs on users, who
generally invested heavily to publicize these numbers. In May 1993 a new
database made 800-numbers portable. This drop in switching costs and
regulations that precluded price discrimination between old and new consumers
provide an empirical test of switching costs' effect on price competition.
  I use contracts for virtual private network (VPN) services to test how AT&T
adjusted its prices for toll-free services in response to portability.
Preliminarily (awaiting completion of data collection), I find that AT&T
reduced margins for VPN contracts containing toll-free services relative to
those that did not as the portability date approached. This implies that the
switching costs due to non-portability made the market less competitive. These
results suggest that, despite toll-free services growing rapidly during this
time period, AT&T's incentive to charge a higher price to "locked-in" consumers
exceeded its incentive to capture new consumers in the high switching costs era
of non-portability.


title:
Profiling Internet Users' Participation in Social Change Agendas: An
  application of Q methodology

abstract:
  New computer-mediated channels of communication are action oriented and have
the ability to deliver information and dialogue - moderated and unmoderated -
which can facilitate the bringing together of a series of society's
stakeholders, opinion leaders and change agents, who have the ability to
influence social action. However, existing online studies have been limited in
explaining Internet users' willingness to participate in social change agendas
online. They have relied predominately on basic demographic descriptors such as
age, education, income and access to technology and have ignored, social,
psychological and attitudinal variables that may explain online participation
and social change. The authors propose a Q methodology research approach better
evaluate Internet users participation in online social change agendas.


title: Bringing the Internet to Schools: US and EU policies

abstract:
  The Internet is changing rapidly the way people around the world communicate,
learn, and work. Yet the tremendous benefits of the Internet are not shared
equally by all. One way to close the gap of the "digital divide" is to ensure
Internet access to all schools from an early age. While both the USA and EU
have embraced the promotion of Internet access to schools, the two have decided
to finance it differently. This paper shows that the main costs of Internet
access to schools are not communications-related (telecommunications and
Internet services) but rather non-communications-related (hardware, educational
training, software). This paper goes on to discuss whether the identified costs
should be financed in any way by the universal service obligations funded by
the telecommunications industry/sector/consumers (sector specific) or a general
governmental budget (educational budget).


title: Branching: the Essence of Constraint Solving

abstract:
  This paper focuses on the branching process for solving any constraint
satisfaction problem (CSP). A parametrised schema is proposed that (with
suitable instantiations of the parameters) can solve CSP's on both finite and
infinite domains. The paper presents a formal specification of the schema and a
statement of a number of interesting properties that, subject to certain
conditions, are satisfied by any instances of the schema.
  It is also shown that the operational procedures of many constraint systems
including cooperative systems) satisfy these conditions.
  Moreover, the schema is also used to solve the same CSP in different ways by
means of different instantiations of its parameters.


title:
Geography and the Internet: Is the Internet a Substitute or a Complement
  for Cities?

abstract:
  By combining persons around the world into a single market, the Internet may
serve as a substitute for urban agglomeration. That is, the Internet may level
the consumption playing field between large, variety-laden and small,
variety-starved markets. However, if local content on the Internet is more
prevalent in larger markets, then the Internet may be a complement for urban
agglomeration. Characterizing the nature of available content using Media
Metrix web page visits by about 13,500 households, we document that
substantially more online local content is available in larger markets.
Combining this with CPS Internet use data, we find statistically significant
direct evidence of both complementarity and substitutability: Individuals are
more likely to connect in markets with more local online content; and holding
local online content constant, are less likely to connect in larger markets. We
also find that individuals connect to overcome local isolation: Blacks are more
likely to connect, relative to whites, when they comprise a smaller fraction of
local population, making the Internet is a substitute for agglomeration of
preference minorities within cities, if not cities themselves. On balance we
find that the substitution and complementarity effects offset each other so
that the Internet does not promote or discourage agglomeration in larger
markets.


title:
India Attempts to Give a Jump-start to its Derailed Telecommunications
  Liberalization Process

abstract:
  After the 1991 economic policy made a shift from a closed economic model to a
market-oriented model. The government invited private sector to participate in
reforming its telecom sector. However, the government took a half-hearted
approach in overhauling the legal and regulatory regime, suitable for
competitive regime or in framing the 1994 Telecom Policy.
  Competition was allowed in cellular and basis services. The ministry and the
incumbent (DOT) issued licenses to their competitors. Lack of transparency in
issuing licenses and unrealistic license fee derailed the reforms process and
led to wasteful litigation. The courts did not support the regulator and
virtually made its role redundant.


title:
Universal service, specific services on generic networks, some logic
  begins to emerge in the policy area

abstract:
  It has proved to be difficult to translate the lessons from the literature on
universal service into the policy framework because of political interests and
regulatory capture. Neither the USA or Europe has made a very good job of
devising a clean framework and the WTO agreement is sparing in this area. A
number of pressures in the European context have enabled a more systematic
approach to emerge, that exploits the academic work. They include the need for
the European regulatory framework to encompass E. European countries where
network development and income levels are much lower, the desire to encompass
Internet within the universal service regulatory framework, a willingness to
design a framework that covers all communications networks and remove the
telecommunications bias, thereby forcing issues of economic neutrality to the
fore. The paper systematically goes through a number of key areas and
principles of regulation and how they are being designed to deal with a range
of national situations. They include, defining the scope of universal service
and the principles by which it might be modified in the light of technological
and economic developments; incorporating latitude for intervention outside this
defined scope, defining incentive and designation methods to encourage the
efficient supply of elements of universal service obligations, interpreting
affordability in the context of price and income levels that diverge
considerably, requiring both allocative efficiency and competitive neutrality,
formulating alternative financing methods including general government
financing and value added tax type methods which can co-exist and provide
comparative policy yardsticks.


title: Commonalities: The R.E.A. and High-Speed Rural Internet Access

abstract:
  This paper explores commonalities between the creation of the Rural
Electrification Administration and the similar dilemma of providing an
affordable infrastructure for high-speed Internet access in places where profit
incentives do not exist. In the case of the R.E.A., the necessity for an
aggressive federal initiative to wire rural America, where the market for
electricity had failed, is revisited as the missing incentives are identified
and explored. We then examine the incentive-poor similarities between rural
electrification and rural high-speed Internet access through how consumers
currently and prospectively gain access to broadband Internet service. The
regulatory environment created by the Telecommunications Act of 1996 and the
Federal Communications Commission is considered. Although the FCC is required
(Section 254.b.3) to take regulatory measures to ensure comparable and
affordable access to the Internet for all Americans, the historical
similarities and comparative analysis of rural electrification and high-speed
Internet access suggests the goal of universal service is unlikely to be met in
the near future. Regulatory disincentives to build such networks are present,
driven in part by market realities and in part by competitive restrictions in
the Telecommunications Act of 1996. Finally, we pose the question of whether a
federal effort equivalent to the R.E.A. is needed to ensure that residents of
sparsely populated areas, like their predecessors in the 1930s, are not
comparatively disadvantaged in the first decades of the 21st century. The paper
concludes with a proposal to accelerate the deployment of broadband
infrastructure in rural America.


title:
On the Use of Vickrey Auctions for Spectrum Allocation in Developing
  Countries

abstract:
  In this paper, we assess the applicability of auctions based on the Vickrey
second price model for allocating wireless spectrum in developing countries. We
first provide an overview of auction models for allocating resources. We then
examine the experience of auctioning spectrum in different countries. Based on
this examination, we posit some axioms that seem to have to be satisfied when
allocating spectrum in most developing countries. In light of these axioms, we
provide a critical evaluation of using Vickrey second- price auctions to
allocate spectrum in developing countries. We suggest the use of a new auction
mechanism, the Vickrey "share auction" which will satisfy many of these axioms.


title: CLP Approaches to 2D Angle Placements

abstract:
  The paper presents two CLP approaches to 2D angle placements, implemented in
CHIP v.5.3. The first is based on the classical (rectangular) cumulative global
constraint, the second on the new trapezoidal cumulative global constraint.
Both approaches are applied to a specific presented.