bluuebunny/crossref_metadata_2025 huggingface dataset:
Error analysis of burst level modeling of active-idle sources
Authors: Wu Yujing , Gong Weibo
Published: July 2004

It is often not feasible to simulate high-speed networks at the packet level. One common technique for simulation speedup is to model traffic at coarser timescales, which we refer to as the
abstract simulation
. In this article, we analyze the sources for the accuracy degradation in abstract simulation. Specifically, we consider burst level modeling of active-idle sources and study a queue fed by such sources. The arrival rates vary during active periods. The burst level model assumes constant rates during each active period. Therefore, it can not track queue-length variations within an active period, which leads to the queue-length evaluation error. We study two scenarios. In the first scenario, the queue is always busy whenever the source is on. During each active period, the evolution of the queue length can be viewed as an integration process of the arrival rate. In this case, the error in the mean queue length shows nice properties. It is only determined by the traffic characteristics and does not change with the utilization. In the multiple-flow case, the error is the sum of the errors caused by abstraction on individual flows. We also show that the error does not propagate for tree-like networks or networks with probabilistic routing. In the first scenario, under very general conditions, burst level modeling does not cause significant underevaluation of the queue length. In the second scenario, the queue may empty during on periods of the source. We call these empty periods E intervals. We quantify the error in the mean queue length, which depends on the numbers, lengths, and positions of the E intervals. The burst level model significantly underevaluates the queue length if such intervals occur often. High utilizations, strong traffic burstiness at the active-idle level, and small arrival granularity tend to reduce such occurrences and the error in the mean queue length. This explains why these conditions favor traffic modeling at coarser timescales. Our findings are not limited to the specific traffic sources and the time-abstraction techniques. Instead, they shed light on the conditions needed for abstract models to deliver evaluation fidelity in a general context.
Scalable fluid models and simulations for large-scale IP networks
Authors: Liu Yong , Presti Francesco L. , Misra Vishal , Towsley Donald F. , Gu Yu
Published: July 2004

In this article we present a scalable model of a network of Active Queue Management (AQM) routers serving a large population of Transport Control Protocol (TCP) flows. We present efficient solution techniques that allow one to obtain the transient behavior of the average queue lengths and packet loss/mark probabilities of AQM routers, and average end-to-end throughput and latencies of TCP users. We model different versions of TCP as well as different implementations of RED Random Early Detection (RED), the most popular AQM scheme currently in use. Comparisons between the models and
ns
simulation show our models to be quite accurate while at the same time requiring substantially less time to solve than packet level simulations, especially when workloads and bandwidths are high.
Fighting the spam wars
Authors: Gburzynski Pawel , Maitan Jacek
Published: July 2004

We present an effective method of eliminating unsolicited electronic mail (so-called
spam
) and discuss its publicly accessible prototype implementation. A subscriber to our system is able to obtain an unlimited number of aliases of his/her permanent (protected) E-Mail address to be handed out to parties willing to communicate with the subscriber. It is also possible to set up publishable aliases, which can be used by human correspondents to contact the subscriber, while being useless to harvesting robots and spammers. The validity of an alias can be easily restricted to a specific duration in time, a specific number of received messages, a specific population of senders, and/or in other ways. The system is fully compatible with the existing E-Mail infrastructure and can be immediately accessed via any standard E-Mail client software (MUA). It can be easily deployed at any institution or organization running its private E-Mail server (MTA) with a trivial modification to that server. Our system offers a simple method to salvage the existing population of E-Mail addresses while eliminating all spam aimed at them.
Optimizing result prefetching in web search engines with segmented indices
Authors: Lempel Ronny , Moran Shlomo
Published: July 2004

We study the process in which search engines with segmented indices serve queries. In particular, we investigate the number of result pages that search engines should prepare during the query processing phase.Search engine users have been observed to browse through very few pages of results for queries that they submit. This behavior of users suggests that prefetching many results upon processing an initial query is not efficient, since most of the prefetched results will not be requested by the user who initiated the search. However, a policy that abandons result prefetching in favor of retrieving just the first page of search results might not make optimal use of system resources either.We argue that for a certain behavior of users, engines should prefetch a constant number of result pages per query. We define a concrete query processing model for search engines with segmented indices, and analyze the cost of such prefetching policies. Based on these costs, we show how to determine the constant that optimizes the prefetching policy. Our results are mostly applicable to
local index
partitions of the inverted files, but are also applicable to processing short queries in
global index
architectures.
Fine-grained control of security capabilities
Authors: Boneh Dan , Ding Xuhua , Tsudik Gene
Published: July 2004

We present a new approach for fine-grained control over users' security privileges (fast revocation of credentials) centered around the concept of an on-line semi-trusted mediator (SEM). The use of a SEM in conjunction with a simple threshold variant of the RSA cryptosystem (mediated RSA) offers a number of practical advantages over current revocation techniques. The benefits include simplified validation of digital signatures, efficient certificate revocation for legacy systems and fast revocation of signature and decryption capabilities. This paper discusses both the architecture and the implementation of our approach as well as its performance and compatibility with the existing infrastructure. Experimental results demonstrate its practical aspects.
Patterns within patterns
Authors: Marcus Aaron
Published: July 2004

Design patterns enable people to envision the future: not only developers, but all stakeholders.
Automatically detecting deceptive criminal identities
Authors: Wang Gang , Chen Hsinchun , Atabakhsh Homa
Published: July 2004

The criminal mind is no match for some of the latest technology designed to determine fact from fiction in suspect identities.
Questioning lawful access to traffic data
Authors: Escudero-Pascual Alberto , Hosein Ian
Published: July 2004

The path to technology-neutral policy is fraught with danger as more legislation is updated to deal with new communications infrastructures.
What causes stress in information system professionals?
Authors: Sethi Vikram , King Ruth C. , Quick James Campbell
Published: July 2004

Job stress can lead to burnout and turnover, costing IT organizations countless dollars in replacement costs, and making methods for measuring and minimizing stress a business benefit.
Superscaled security
Authors: Mercuri Rebecca T.
Published: July 2004

Exponential increases in computational speed, memory capacity, and bandwidth impose futuristic security demands and challenges.
Beware of counting LOC
Authors: Armour Phillip G.
Published: July 2004

Seeking a better method for estimating system size in an attempt to measure knowledge content.
How computer games affect CS (and other) students' school performance
Authors: Messerly John G.
Published: July 2004

Compulsive game playing, especially of the role-playing variety, risks failing grades and withdrawal of financial support from tuition-paying parents.
Countering terrorism through information technology
Authors: Popp Robert , Armour Thomas , Senator Ted , Numrych Kristen
Published: July 2004

Developing the information-analysis tools for an effective multi-agency information-sharing effort.
Graph-based technologies for intelligence analysis
Authors: Coffman Thayne , Greenblatt Seth , Marcus Sherry
Published: July 2004

Enhancing traditional algorithmic techniques for improved pattern analysis.
Lenses in arrangements of pseudo-circles and their applications
Authors: Agarwal Pankaj K. , Nevo Eran , Pach János , Pinchasi Rom , Sharir Micha , Smorodinsky Shakhar
Published: July 2004

A collection of simple closed Jordan curves in the plane is called a family of
pseudo-circles
if any two of its members intersect at most twice. A closed curve composed of two subarcs of distinct pseudo-circles is said to be an
empty lens
if the closed Jordan region that it bounds does not intersect any other member of the family. We establish a linear upper bound on the number of empty lenses in an arrangement of
n
pseudo-circles with the property that any two curves intersect precisely twice. We use this bound to show that any collection of
n
x
-monotone pseudo-circles can be cut into
O
(
n
8/5
) arcs so that any two intersect at most once; this improves a previous bound of
O
(
n
5/3
) due to Tamaki and Tokuyama. If, in addition, the given collection admits an algebraic representation by three real parameters that satisfies some simple conditions, then the number of cuts can be further reduced to
O
(
n
3/2
(log
n
)

O
(α(

s

(
n
))

), where α(
n
) is the inverse Ackermann function, and
s
is a constant that depends on the the representation of the pseudo-circles. For arbitrary collections of pseudo-circles, any two of which intersect exactly twice, the number of necessary cuts reduces still further to
O
(
n
4/3
). As applications, we obtain improved bounds for the number of incidences, the complexity of a single level, and the complexity of many faces in arrangements of circles, of pairwise intersecting pseudo-circles, of arbitrary
x
-monotone pseudo-circles, of parabolas, and of homothetic copies of any fixed simply shaped convex curve. We also obtain a variant of the Gallai--Sylvester theorem for arrangements of pairwise intersecting pseudo-circles, and a new lower bound on the number of distinct distances under any well-behaved norm.
Number-theoretic constructions of efficient pseudo-random functions
Authors: Naor Moni , Reingold Omer
Published: July 2004

We describe efficient constructions for various cryptographic primitives in private-key as well as public-key cryptography. Our main results are two new constructions of pseudo-random functions. We prove the pseudo-randomness of one construction under the assumption that
factoring
(Blum integers) is hard while the other construction is pseudo-random if the
decisional version of the Diffie--Hellman
assumption holds. Computing the value of our functions at any given point involves two subset products. This is much more efficient than previous proposals. Furthermore, these functions have the advantage of being in
TC
0
(the class of functions computable by constant depth circuits consisting of a polynomial number of threshold gates). This fact has several interesting applications. The simple algebraic structure of the functions implies additional features such as a zero-knowledge proof for statements of the form "
y
=
f

s

(
x
)" and "
y
≠
f

s

(
x
)" given a commitment to a key
s
of a pseudo-random function
f

s

.
On sufficient conditions for unsatisfiability of random formulas
Authors: Atserias Albert
Published: July 2004

A descriptive complexity approach to random 3-SAT is initiated. We show that unsatisfiability of any significant fraction of random 3-CNF formulas cannot be certified by any property that is expressible in Datalog. Combined with the known relationship between the complexity of constraint satisfaction problems and expressibility in Datalog, our result implies that any constraint propagation algorithm working with small constraints will fail to certify unsatisfiability almost always. Our result is a consequence of designing a winning strategy for one of the players in the existential pebble game. The winning strategy makes use of certain extension axioms that we introduce and hold almost surely on a random 3-CNF formula. The second contribution of our work is the connection between finite model theory and propositional proof complexity. To make this connection explicit, we establish a tight relationship between the number of pebbles needed to win the game and the width of the Resolution refutations. As a consequence to our result and the known size--width relationship in Resolution, we obtain new proofs of the exponential lower bounds for Resolution refutations of random 3-CNF formulas and the Pigeonhole Principle.
Improving graphical information system model use with elision and connecting lines
Authors: Huotari Jouni , Lyytinen Kalle , Niemelä Marketta
Published: July 2004

Graphical information system (IS) models are used to specify and design IS from several perspectives. Due to the growing size and complexity of modern information systems, critical design information is often distributed via multiple diagrams. This slows search performance and results in reading errors that later cause omissions and inconsistencies in the final designs. We study the impact of large screens and the two promising visual integration techniques of elision and connecting lines that can decrease the designers' cognitive efforts to read diagrams. We conduct a laboratory experiment using 84 computer science students to investigate the impact of these techniques on the accuracy of the subjects' search and recall with entity-relationship diagrams and data flow diagrams. The search tasks involve both vertical and horizontal searches on a moderately complex IS model that consists of multiple diagrams. We also examine the subjects' spatial visualization abilities as a possible covariant for observed search performance. These visual integration techniques significantly reduced errors in both the search and the recall of diagrams, especially with respect to individuals with low spatial visualization ability.
A fast and accurate framework to analyze and optimize cache memory behavior
Authors: Vera Xavier , Bermudo Nerina , Llosa Josep , González Antonio
Published: July 2004

The gap between processor and main memory performance increases every year. In order to overcome this problem, cache memories are widely used. However, they are only effective when programs exhibit sufficient data locality. Compile-time program transformations can significantly improve the performance of the cache. To apply most of these transformations, the compiler requires a precise knowledge of the locality of the different sections of the code, both before and after being transformed.Cache miss equations (CMEs) allow us to obtain an analytical and precise description of the cache memory behavior for loop-oriented codes. Unfortunately, a direct solution of the CMEs is computationally intractable due to its NP-complete nature.This article proposes a fast and accurate approach to estimate the solution of the CMEs. We use sampling techniques to approximate the absolute miss ratio of each reference by analyzing a small subset of the iteration space. The size of the subset, and therefore the analysis time, is determined by the accuracy selected by the user. In order to reduce the complexity of the algorithm to solve CMEs, effective mathematical techniques have been developed to analyze the subset of the iteration space that is being considered. These techniques exploit some properties of the particular polyhedra represented by CMEs.
Modular refinement of hierarchic reactive machines
Authors: Alur Rajeev , Grosu Radu
Published: July 2004

Scalable formal analysis of reactive programs demands integration of modular reasoning techniques with existing analysis tools. Modular reasoning principles such as abstraction, compositional refinement, and assume-guarantee reasoning are well understood for architectural hierarchy that describes the communication structure between component processes, and have been shown to be useful. In this paper, we develop the theory of modular reasoning for
behavior hierarchy
that describes control structure using hierarchic modes. From Statecharts to UML, behavior hierarchy has been an integral component of many software design languages, but only syntactically. We present the
hierarchic reactive modules
language that retains powerful features such as nested modes, mode reuse, exceptions, group transitions, history, and conjunctive modes, and yet has a
semantic
notion of mode hierarchy. We present an observational trace semantics for modes that provides the basis for mode refinement. We show the refinement to be compositional with respect to the mode constructors, and develop an assume-guarantee reasoning principle.
Combining importance sampling and temporal difference control variates to simulate Markov Chains
Authors: Randhawa R. S. , Juneja S.
Published: July 2004

It is well known that in estimating performance measures associated with a stochastic system a good importance sampling distribution (IS) can give orders of magnitude of variance reduction while a bad one may lead to large, even infinite, variance. In this paper we study how this sensitivity of the estimator variance to the importance sampling change of measure may be "dampened" by combining importance sampling with stochastic approximation based temporal difference (TD) method. We consider a finite state space discrete time Markov chain (DTMC) with one-step transition rewards and an absorbing set of states and focus on estimating the cumulative expected reward to absorption starting from any state. In this setting we develop sufficient conditions under which the estimate resulting from the combined approach has a mean square error that asymptotically equals zero even when the estimate formed by using only importance sampling change of measure has infinite variance. In particular, we consider the problem of estimating the small buffer overflow probability in a queuing network, where the change of measure suggested in literature is shown to have infinite variance under certain parameters and where the appropriate combination of IS and TD method can be empirically seen to have a much faster convergence rate compared to naive simulation.
To batch or not to batch?
Authors: Alexopoulos Christos , Goldsman David
Published: July 2004

When designing steady-state computer simulation experiments, one may be faced with the choice of batching observations in one long run or replicating a number of smaller runs. Both methods are potentially useful in the course of undertaking simulation output analysis. The tradeoffs between the two alternatives are well known: batching ameliorates the effects of initialization bias, but produces batch means that might be correlated; replication yields independent sample means, but may suffer from initialization bias at the beginning of each of the runs. We present several new results and specific examples to lend insight as to when one method might be preferred over the other. In steady-state, batching and replication perform similarly in terms of estimating the mean and variance parameter, but replication tends to do better than batching with regard to the performance of confidence intervals for the mean. Such a victory for replication may be hollow, for in the presence of an initial transient, batching often performs better than replication when it comes to point and confidence-interval estimation of the steady-state mean. We conclude---like other classic references---that in the context of estimation of the steady-state mean, batching is typically the wiser approach.
The surprise language exercises
Authors: Oard Douglas W.
Published: July 2004

For ten days in March and twenty-nine days in June of 2003, sixteen teams in two nations sought to develop language technologies for two previously unanticipated languages; Cebuano and Hindi. This introduction to a pair of special issues explains the motivation for those exercises, the approaches that were tried, and some of the lessons that were learned.
Linguistic resource creation for research and technology development
Authors: Strassel Stephanie , Maxwell Mike , Cieri Christopher
Published: July 2004

Advances in statistical machine learning encourage language-independent approaches to linguistic technology development. Experiments in "porting" technologies to handle new natural languages have revealed a great potential for multilingual computing, but also a frustrating lack of linguistic resources for most languages. Recent efforts to address the lack of available resources have focused either on intensive resource development for a small number of languages or development of technologies for rapid porting. The Linguistic Data Consortium recently participated in an experiment falling primarily under the first approach,
the surprise language exercise
. This article describes linguistic resource creation within this context, including the overall methodology for surveying and collecting language resources, as well as details of the resources developed during the exercise. The article concludes with discussion of a new approach to solving the problem of limited linguistic resources, one that has recently proven effective in identifying core linguistic resources for less common studied languages.
Experiments with a Hindi-to-English transfer-based MT system under a miserly data scenario
Authors: Lavie Alon , Vogel Stephan , Levin Lori , Peterson Erik , Probst Katharina , Llitjós Ariadna Font , Reynolds Rachel , Carbonell Jaime , Cohen Richard
Published: July 2004

We describe an experiment designed to evaluate the capabilities of our trainable transfer-based (Xfer) machine translation approach, as applied to the task of Hindi-to-English translation, and trained under an extremely limited data scenario. We compare the performance of the Xfer approach with two corpus-based approaches---Statistical MT (SMT) and Example-based MT (EBMT)---under the limited data scenario. The results indicate that the Xfer system significantly outperforms both EBMT and SMT in this scenario. Results also indicate that automatically learned transfer rules are effective in improving translation performance, compared with a baseline word-to-word translation version of the system. Xfer system performance with a limited number of manually written transfer rules is, however, still better than the current automatically inferred rules. Furthermore, a "multiengine" version of our system that combined the output of the Xfer and SMT systems and optimizes translation selection outperformed both individual systems.
Probabilistic wavelet synopses
Authors: Garofalakis Minos , Gibbons Phillip B.
Published: July 2004

Recent work has demonstrated the effectiveness of the wavelet decomposition in reducing large amounts of data to compact sets of wavelet coefficients (termed "wavelet synopses") that can be used to provide fast and reasonably accurate approximate query answers. A major shortcoming of these existing wavelet techniques is that the quality of the approximate answers they provide varies widely, even for identical queries on nearly identical values in distinct parts of the data. As a result, users have no way of knowing whether a particular approximate answer is highly-accurate or off by many orders of magnitude. In this article, we introduce
Probabilistic Wavelet Synopses
, the first wavelet-based data reduction technique optimized for guaranteed accuracy of individual approximate answers. Whereas previous approaches rely on
deterministic
thresholding for selecting the wavelet coefficients to include in the synopsis, our technique is based on a novel,
probabilistic
thresholding scheme that assigns each coefficient a probability of being included based on its importance to the reconstruction of individual data values, and then flips coins to select the synopsis. We show how our scheme avoids the above pitfalls of deterministic thresholding, providing
unbiased
, highly accurate answers for individual data values in a data vector. We propose several novel optimization algorithms for tuning our probabilistic thresholding scheme to minimize desired error metrics. Experimental results on real-world and synthetic data sets evaluate these algorithms, and demonstrate the effectiveness of our probabilistic wavelet synopses in providing fast, highly accurate answers with improved quality guarantees.
Accelerating XPath evaluation in any RDBMS
Authors: Grust Torsten , Keulen Maurice Van , Teubner Jens
Published: July 2004

This article is a proposal for a database index structure, the
XPath accelerator
, that has been specifically designed to support the evaluation of XPath path expressions. As such, the index is capable to support
all
XPath axes (including ancestor, following, preceding-sibling, descendant-or-self, etc.). This feature lets the index stand out among related work on XML indexing structures which had a focus on the child and descendant axes only. The index has been designed with a close eye on the XPath semantics as well as the desire to engineer its internals so that it can be supported well by
existing
relational database query processing technology: the index (a) permits set-oriented (or, rather, sequence-oriented) path evaluation, and (b) can be implemented and queried using well-established relational index structures, notably B-trees and R-trees.We discuss the implementation of the XPath accelerator on top of different database backends and show that the index performs well on all levels of the memory hierarchy, including disk-based and main-memory based database systems.
Selection conditions in main memory
Authors: Ross Kenneth A.
Published: July 2004

We consider the fundamental operation of applying a compound filtering condition to a set of records. With large main memories available cheaply, systems may choose to keep the data entirely in main memory, in order to improve query and/or update performance.The design of a data-intensive algorithm in main memory needs to take into account the architectural characteristics of modern processors, just as a disk-based method needs to consider the physical characteristics of disk devices. An important architectural feature that influences the performance of main memory algorithms is the branch misprediction penalty. We demonstrate that branch misprediction has a substantial impact on the performance of an algorithm for applying selection conditions.We describe a space of "query plans" that are logically equivalent, but differ in terms of performance due to variations in their branch prediction behavior. We propose a cost model that takes branch prediction into account, and develop a query optimization algorithm that chooses a plan with optimal estimated cost for conjunctive conditions. We also develop an efficient heuristic optimization algorithm. We also show how records can be ordered to further reduce branch misprediction effects.We provide experimental results for a case study based on an event notification system. Our results show the effectiveness of the proposed optimization techniques. Our results also demonstrate that significant improvements in performance can be obtained by applying a methodology that takes branch misprediction latency into account.
Characterizing memory requirements for queries over continuous data streams
Authors: Arasu Arvind , Babcock Brian , Babu Shivnath , McAlister Jon , Widom Jennifer
Published: July 2004

This article deals with continuous conjunctive queries with arithmetic comparisons and optional aggregation over multiple data streams. An algorithm is presented for determining whether or not any given query can be evaluated using a bounded amount of memory for all possible instances of the data streams. For queries that can be evaluated using bounded memory, an execution strategy based on constant-sized synopses of the data streams is proposed. For queries that cannot be evaluated using bounded memory, data stream scenarios are identified in which evaluating the queries requires memory linear in the size of the unbounded streams.
Two-step error estimators for implicit Runge--Kutta methods applied to stiff systems
Authors: González--Pinto S. , Montijano J. I. , Pérez--Rodríguez S.
Published: July 2004

This paper is concerned with local error estimation in the numerical integration of stiff systems of ordinary differential equations by means of Runge--Kutta methods. With implicit Runge--Kutta methods it is often difficult to embed a local error estimate with the appropriate order and stability properties. In this paper local error estimation based on the information from the last two integration steps (that are supposed to have the same steplength) is proposed. It is shown that this technique, applied to Radau IIA methods, lets us get estimators with proper order and stability properties. Numerical examples showing that the proposed estimate improves the efficiency of the integration codes are presented.
The design and implementation of a new out-of-core sparse cholesky factorization method
Authors: Rotkin Vladimir , Toledo Sivan
Published: July 2004

We describe a new out-of-core sparse Cholesky factorization method. The new method uses the elimination tree to partition the matrix, an advanced subtree-scheduling algorithm, and both right-looking and left-looking updates. The implementation of the new method is efficient and robust. On a 2 GHz personal computer with 768 MB of main memory, the code can easily factor matrices with factors of up to 48 GB, usually at rates above 1 Gflop/s. For example, the code can factor audikw, currenly the largest matrix in any matrix collection (factor size over 10 GB), in a little over an hour, and can factor a matrix whose graph is a 140-by-140-by-140 mesh in about 12 hours (factor size around 27 GB).
SIPAMPL
Authors: Vaz A. Ismael F. , Fernandes Edite M. G. P. , Gomes M. Paula S. F.
Published: July 2004

SIPAMPL is an environment for coding semi-infinite programming (SIP) problems. This environment includes a database containing a set of SIP problems that have been collected from the literature and a set of routines. It allows users to code their own SIP problems in AMPL, to use any problem already in the database, and to develop and test any SIP solver. The SIPAMPL routines support the interface between a potential SIP solver and test problems coded in AMPL. SIPAMPL also provides a tool that allows the selection of problems from the database with specified characteristics. As a concept demonstration, we show how MATLAB can use SIPAMPL to solve the problems in the database. The Linux and Microsoft Windows versions together with the database of coded problems are freely available via the web.
Vector reduction/transformation operators
Authors: Bartlett Roscoe A. , Waanders Bart G. Van Bloemen , Heroux Michael A.
Published: July 2004

Development of flexible linear algebra interfaces is an increasingly critical issue. Efficient and expressive interfaces are well established for some linear algebra abstractions, but not for vectors. Vectors differ from other abstractions in the diversity of necessary operations, sometimes requiring dozens for a given algorithm (e.g. interior-point methods for optimization). We discuss a new approach based on operator objects that are transported to the underlying data by the linear algebra library implementation, allowing developers of abstract numerical algorithms to easily extend the functionality regardless of computer architecture, application or data locality/organization. Numerical experiments demonstrate efficient implementation.
The domino effect of password reuse
Authors: Ives Blake , Walsh Kenneth R. , Schneider Helmut
Published: July 2004

One weak spot is all it takes to open secured digital doors and online accounts causing untold damage and consequences.
The economics of wireless networks
Authors: Nicopolitidis Petros , Papadimitriou Georgios , Obaidat Mohammed S. , Pomportsis Andreas S.
Published: July 2004

Assessing the rapidly changing economics of the wireless industry.
The social life of innovation
Authors: Denning Peter J.
Published: July 2004

Fostering a change of practice in a community is much more difficult than inventing a new technology. The practice of innovation can be learned---once you know what it is.
Etiquette equality
Authors: Nass Clifford
Published: July 2004

As much as people crave more human-like computers, experimental evidence shows that people do display polite behavior toward computers, perceiving human qualities they don't actually have.
Automatic generation of rule-based constraint solvers over finite domains
Authors: Abdennadher Slim , Rigotti Christophe
Published: July 2004

A general approach to implement propagation and simplification of constraints consists of applying rules over these constraints. However, a difficulty that arises frequently when writing a constraint solver is to determine the constraint propagation algorithm. In this article, we propose a method for generating propagation and simplification rules for constraints over finite domains defined extensionally by, for example, a truth table or their tuples. The generation of rules is performed in two steps. First, propagation rules are generated. Propagation rules do not rewrite constraints but add new ones. Thus, the constraint store may contain superfluous constraints. Removing these constraints not only allows saving of space but also decreases the cost of constraint solving. Constraints can be removed using simplification rules. Thus, in a second step, some propagation rules are transformed into simplification rules.Furthermore, we show that our approach performs well on various examples, including Boolean constraints, multivalued logic, and Allen's qualitative approach to temporal logic. Moreover, an application taken from the field of digital circuit design shows that our approach is of practical use.
Convergent approximate solving of first-order constraints by approximate quantifiers
Authors: Ratschan Stefan
Published: July 2004

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 article, we remove this obstacle 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.
Inflationary fixed points in modal logic
Authors: Dawar Anuj , Grädel Erich , Kreutzer Stephan
Published: July 2004

We consider an extension of modal logic with an operator for constructing inflationary fixed points, just as the modal μ-calculus extends basic modal logic with an operator for least fixed points. Least and inflationary fixed-point operators have been studied and compared in other contexts, particularly in finite model theory, where it is known that the logics IFP and LFP that result from adding such fixed-point operators to first-order logic have equal expressive power. As we show, the situation in modal logic is quite different, as the modal iteration calculus (MIC), we introduce has much greater expressive power than the μ-calculus. Greater expressive power comes at a cost: the calculus is algorithmically much less manageable.
Classes of term rewrite systems with polynomial confluence problems
Authors: Godoy Guillem , Nieuwenhuis Robert , Tiwari Ashish
Published: July 2004

The confluence property of ground (i.e., variable-free) term rewrite systems (TRS) is well known to be decidable. This was proved independently in Dauchet et al. [1987, 1990] and in Oyamaguchi [1987] using tree automata techniques and ground tree transducer techniques (originated from this problem), yielding EXPTIME decision procedures (PSPACE for strings). Since then, and until last year, the optimality of this bound had been a well-known longstanding open question (see, e.g., RTA-LOOP [2001]).In Comon et al. [2001], we gave the first polynomial-time algorithm for deciding the confluence of ground TRS. Later in Tiwari [2002] this result was extended, using abstract congruent closure techniques, to linear shallow TRS, that is, TRS where no variable occurs twice in the same rule nor at depth greater than one. Here, we give a new and much simpler proof of the latter result.
Some applications of logic to feasibility in higher types
Authors: Ignjatovic Aleksandar , Sharma Arun
Published: July 2004

While it is commonly accepted that computability on a Turing machine in polynomial time represents a correct formalization of the notion of a
feasibly computable
function, there is no similar agreement on how to extend this notion on
functionals
, that is, what functionals should be considered feasible. One possible paradigm was introduced by Mehlhorn, who extended Cobham's definition of feasible functions to type 2 functionals. Subsequently, this class of functionals (with inessential changes of the definition) was studied by Townsend who calls this class
POLY
, and by Kapron and Cook who call the same class
basic feasible functionals
. Kapron and Cook gave an oracle Turing machine model characterisation of this class. In this article, we demonstrate that the class of basic feasible functionals has recursion theoretic properties which naturally generalise the corresponding properties of the class of feasible functions, thus giving further evidence that the notion of feasibility of functionals mentioned above is correctly chosen. We also improve the Kapron and Cook result on machine representation.Our proofs are based on essential applications of logic. We introduce a weak fragment of second order arithmetic with second order variables ranging over functions from N
N
which suitably characterises basic feasible functionals, and show that it is a useful tool for investigating the properties of basic feasible functionals. In particular, we provide an example how one can extract feasible programs from mathematical proofs that use nonfeasible functions.
Hindi-english cross-lingual question-answering system
Authors: Sekine Satoshi , Grishman Ralph
Published: July 2004

We developed a cross-lingual, question-answering (CLQA) system for Hindi and English. It accepts questions in English, finds candidate answers in Hindi newspapers, and translates the answer candidates into English along with the context surrounding each answer. The system was developed as part of the surprise language exercise (SLE) within the TIDES program.
Cross-lingual C*ST*RD
Authors: Leuski Anton , Lin Chin-Yew , Zhou Liang , Germann Ulrich , Och Franz Josef , Hovy Eduard
Published: July 2004

We present C*ST*RD, a cross-language information delivery system that supports cross-language information retrieval, information space visualization and navigation, machine translation, and text summarization of single documents and clusters of documents. C*ST*RD was assembled and trained within 1 month, in the context of DARPA's Surprise Language Exercise, that selected as source a heretofore unstudied language, Hindi. Given the brief time, we could not create deep Hindi capabilities for all the modules, but instead experimented with combining shallow Hindi capabilities, or even English-only modules, into one integrated system. Various possible configurations, with different tradeoffs in processing speed and ease of use, enable the rapid deployment of C*ST*RD to new languages under various conditions.
Rapid customization of an information extraction system for a surprise language
Authors: Maynard Diana , Tablan Valentin , Bontcheva Kalina , Cunningham Hamish
Published: July 2004

This paper describes the rapid adaptation for surprise languages of a flexible and robust Information Extraction system based on GATE, a portable Natural Language Processing infrastructure. Our experiences show that even without a native speaker and in the absence of training data, we can quickly customize the system to a new language. We adapted the default English system for the Cebuano language in 10 days, achieving an F measure of 77.5%.
An unfold/fold transformation framework for definite logic programs
Authors: Roychoudhury Abhik , Kumar K. Narayan , Ramakrishnan C. R. , Ramakrishnan I. V.
Published: July 2004

Given a logic program
P
, an unfold/fold program transformation system derives a sequence of programs
P
=
P
0
,
P
1
, …,
P

n

, such that
P

i
+1

is derived from
P

i

by application of either an unfolding or a folding step. Unfold/fold transformations have been widely used for improving program efficiency and for reasoning about programs. Unfolding corresponds to a resolution step and hence is semantics-preserving. Folding, which replaces an occurrence of the right hand side of a clause with its head, may on the other hand produce a semantically different program. Existing unfold/fold transformation systems for logic programs restrict the application of folding by placing (usually syntactic) conditions that are sufficient to guarantee the correctness of folding. These restrictions are often too strong, especially when the transformations are used for reasoning about programs. In this article we develop a transformation system (called SCOUT) for definite logic programs that is provably more powerful (in terms of transformation sequences allowed) than existing transformation systems. This extra power is needed for a novel use of logic program transformations: for the verification of a specific class of concurrent systems, called
parameterized
concurrent systems.Our transformation system is constructed by developing a framework, which is parameterized by a "measure space" and associated measure functions. This framework places no syntactic restriction on the application of folding, and it can be used to derive transformation systems (by fixing the measure space and functions). The power of the system is determined by the choice of the measure space and functions; thus the relative power of different transformation systems can be compared by considering their measure spaces and functions. The correctness of these transformation systems follows from the correctness of the framework. We show that various existing transformation systems can be obtained as instances of our framework. We extend the unfold/fold transformation framework with a goal replacement transformation that allows semantically equivalent conjunctions of atoms to be interchanged. We then derive a new transformation system SCOUT as an instance of the framework and show its power relative to the existing transformation systems. SCOUT has been used to inductively prove temporal properties of parameterized concurrent systems (infinite families of finite state concurrent systems). We demonstrate the use of the additional power of SCOUT in constructing such induction proofs.
Natural semantics as a static program analysis framework
Authors: Glesner Sabine , Zimmermann Wolf
Published: July 2004

Natural semantics specifications have become mainstream in the formal specification of programming language semantics during the last 10 years. In this article, we set up sorted natural semantics as a specification framework which is able to express static semantic information of programming languages declaratively in a uniform way and allows one at the same time to generate corresponding analyses. Such static semantic information comprises context-sensitive properties which are checked in the semantic analysis phase of compilers as well as further static program analyses such as, for example, classical data and control flow analyses or type and effect systems. The latter require fixed-point analyses to determine their solutions. We show that, given a sorted natural semantics specification, we can generate the corresponding analysis. Therefore, we classify the solution of such an analysis by the notion of a proof tree. We show that a proof tree can be computed by solving an equivalent residuation problem. In case of the semantic analysis, this solution can be found by a basic algorithm. We show that its efficiency can be enhanced using solution strategies. We also demonstrate our prototype implementation of the basic algorithm which proves its applicability in practical situations. With the results of this article, we have established natural semantics as a framework which closes the gap between declarative and operational specification methods for static semantic properties as well as between specification frameworks for the semantic analysis. In particular, we show that natural semantics is expressive enough to define fixed-point program analyses.
JR
Authors: Keen Aaron W. , Ge Tingjian , Maris Justin T. , Olsson Ronald A.
Published: July 2004

Java provides a clean object-oriented programming model and allows for inherently system-independent programs. Unfortunately, Java has a limited concurrency model, providing only threads and remote method invocation (RMI).The JR programming language extends Java to provide a rich concurrency model, based on that of SR. JR provides dynamic remote virtual machine creation, dynamic remote object creation, remote method invocation, asynchronous communication, rendezvous, and dynamic process creation. JR's concurrency model stems from the addition of operations (a generalization of procedures) and JR supports the redefinition of operations through inheritance. JR programs are written in an extended Java and then translated into standard Java programs. The JR run-time support system is also written in standard Java.This paper describes the JR programming language and its implementation. Some initial measurements of the performance of the implementation are also included.
MarieSim
Authors: Null Linda , Lobur Julia
Published: July 2004

MarieSim is a computer architecture simulator based on the MARIE architecture and designed to teach beginning computer organization and architecture. It provides users with interactive tools and simulations to help them deepen their understanding of the operation of a simple computer.Through interaction with MarieSim's graphical environment, students can observe how assembly language statements affect the registers and memory of a computer system. The graphical environment for MarieSim and the accompanying data path simulator are written in Java Swing; the integrated MARIE assembler is written in Java. The software has proven useful in introductory computer organization and architecture classes. Students find MarieSim very easy to use, and anecdotal results indicate increased architectural understanding. In this article we compare MarieSim to various existing systems and explore the software's features in detail.