title: Generative Programming of Graphical User Interfaces

abstract: Generative Programming (GP) is a computing paradigm allowing automatic creation of entire software families utilizing the configuration of elementary and reusable components. GP can be projected on different technologies, e.g. C++-templates, Java-Beans, Aspect-Oriented Programming (AOP), or Frame technology. This paper focuses on Frame Technology, which aids the possible implementation and completion of software components. The purpose of this paper is to introduce the GP paradigm in the area of GUI application generation. It demonstrates how automatically customized executable applications with GUI parts can be generated from an abstract specification.


title: Higher-Order Concurrent Win32 Programming

abstract: We present a concurrent framework for Win32 programming based on Concurrent ML, a concurrent language with higher-order functions, static typing, lightweight threads and synchronous communication channels. The key points of the framework are the move from an event loop model to a threaded model for the processing of window messages, and the decoupling of controls notifications from the system messages. This last point allows us to derive a general way of writing controls that leads to easy composition, and can accommodate ActiveX Controls in a transparent way.


title: Reactive Programming in Standard ML

abstract: Reactive systems are systems that maintain an ongoing interaction with their environment, activated by receiving input events from the environment and producing output events in response. Modern programming languages designed to program such systems use a paradigm based on the notions of instants and activations. We describe a library for Standard ML that provides basic primitives for programming reactive systems. The library is a low-level system upon which more sophisticated reactive behaviors can be built, which provides a convenient framework for prototyping extensions to existing reactive languages.


title: An Analysis of Lambek's Production Machines

abstract: Lambek's production machines may be used to generate and recognize sentences in a subset of the language described by a production grammar. We determine in this paper the subset of the language of a grammar generated and recognized by such machines.


title: Aspects de la Programmation d'Applications Win32 avec un Langage Fonctionnel

abstract: A useful programming language needs to support writing programs that take advantage of services and communication mechanisms supplied by the operating system. We examine the problem of programming native Win32 applications under Windows with Standard ML. We introduce an framework based on the IDL interface language et a minimal foreign-functions interface to explore the Win32 API et COM in the context of Standard ML.


title: The Design of a COM-Oriented Module System

abstract: We present in this paper the preliminary design of a module system based on a notion of components such as they are found in COM. This module system is inspired from that of Standard ML, and features first-class instances of components, first-class interfaces, and interface-polymorphic functions, as well as allowing components to be both imported from the environment and exported to the environment using simple mechanisms. The module system automates the memory management of interfaces and hides the IUnknown interface and QueryInterface mechanisms from the programmer, favoring instead a higher-level approach to handling interfaces.


title: A Framework for Interoperability

abstract: Practical implementations of high-level languages must provide access to libraries and system services that have APIs specified in a low-level language (usually C). An important characteristic of such mechanisms is the foreign-interface policy that defines how to bridge the semantic gap between the high-level language and C. For example, IDL-based tools generate code to marshal data into and out of the high-level representation according to user annotations. The design space of foreign-interface policies is large and there are pros and cons to each approach. Rather than commit to a particular policy, we choose to focus on the problem of supporting a gamut of interoperability policies. In this paper, we describe a framework for language interoperability that is expressive enough to support very efficient implementations of a wide range of different foreign-interface policies. We describe two tools that implement substantially different policies on top of our framework and present benchmarks that demonstrate their efficiency.


title: On the Expressive Power of First-Order Boolean Functions in PCF

abstract: Recent results of Bucciarelli show that the semilattice of degrees of parallelism of first-order boolean functions in PCF has both infinite chains and infinite antichains. By considering a simple subclass of Sieber's sequentiality relations, we identify levels in the semilattice and derive inexpressibility results concerning functions on different levels. This allows us to further explore the structure of the semilattice of degrees of parallelism: we identify semilattices characterized by simple level properties, and show the existence of new infinite hierarchies which are in a certain sense natural with respect to the levels.


title: A New Dynamical Domain Decomposition Method for Parallel Molecular Dynamics Simulation on Grid

abstract: We develop a new Lagrangian material particle -- dynamical domain decomposition method (MPD^3) for large scale parallel molecular dynamics (MD) simulation of nonstationary heterogeneous systems on a heterogeneous computing net. MPD^3 is based on Voronoi decomposition of simulated matter. The map of Voronoi polygons is known as the Dirichlet tessellation and used for grid generation in computational fluid dynamics. From the hydrodynamics point of view the moving Voronoi polygon looks as a material particle (MP). MPs can exchange particles and information. To balance heterogeneous computing conditions the MP centers should be dependent on timing data. We propose a simple and efficient iterative algorithm which based on definition of the timing-dependent balancing displacement of MP center for next simulation step. The MPD^3 program was tested in various computing environments and physical problems. We have demonstrated that MPD^3 is a high-adaptive decomposition algorithm for MD simulation. It was shown that the well-balanced decomposition can result from dynamical Voronoi polygon tessellation. One would expect the similar approach can be successfully applied for other particle methods like Monte Carlo, particle-in-cell, and smooth-particle-hydrodynamics.


title: A Grid Information Infrastructure for Medical Image Analysis

abstract: The storage and manipulation of digital images and the analysis of the information held in those images are essential requirements for next-generation medical information systems. The medical community has been exploring collaborative approaches for managing image data and exchanging knowledge and Grid technology [1] is a promising approach to enabling distributed analysis across medical institutions and for developing new collaborative and cooperative approaches for image analysis without the necessity for clinicians to co-locate. The EU-funded MammoGrid project [2] is one example of this and it aims to develop a Europe-wide database of mammograms to support effective co-working between healthcare professionals across the EU. The MammoGrid prototype comprises a high-quality clinician visualization workstation (for data acquisition and inspection), a DICOM-compliant interface to a set of medical services (annotation, security, image analysis, data storage and querying services) residing on a so-called Grid-box and secure access to a network of other Grid-boxes connected through Grid middleware. One of the main deliverables of the project is a Grid-enabled infrastructure that manages federated mammogram databases across Europe. This paper outlines the MammoGrid Information Infrastructure (MII) for meta-data analysis and knowledge discovery in the medical imaging domain.


title: High-Level Networking With Mobile Code And First Order AND-Continuations

abstract: We describe a scheme for moving living code between a set of distributed processes coordinated with unification based Linda operations, and its application to building a comprehensive Logic programming based Internet programming framework. Mobile threads are implemented by capturing first order continuations in a compact data structure sent over the network. Code is fetched lazily from its original base turned into a server as the continuation executes at the remote site. Our code migration techniques, in combination with a dynamic recompilation scheme, ensure that heavily used code moves up smoothly on a speed hierarchy while volatile dynamic code is kept in a quickly updatable form. Among the examples, we describe how to build programmable client and server components (Web servers, in particular) and mobile agents.


title: Convex Hull of Planar H-Polyhedra

abstract: Suppose $<A_i, \vec{c}_i>$ are planar (convex) H-polyhedra, that is, $A_i \in \mathbb{R}^{n_i \times 2}$ and $\vec{c}_i \in \mathbb{R}^{n_i}$. Let $P_i = \{\vec{x} \in \mathbb{R}^2 \mid A_i\vec{x} \leq \vec{c}_i \}$ and $n = n_1 + n_2$. We present an $O(n \log n)$ algorithm for calculating an H-polyhedron $<A, \vec{c}>$ with the smallest $P = \{\vec{x} \in \mathbb{R}^2 \mid A\vec{x} \leq \vec{c} \}$ such that $P_1 \cup P_2 \subseteq P$.


title: Propositional Defeasible Logic has Linear Complexity

abstract: Defeasible logic is a rule-based nonmonotonic logic, with both strict and defeasible rules, and a priority relation on rules. We show that inference in the propositional form of the logic can be performed in linear time. This contrasts markedly with most other propositional nonmonotonic logics, in which inference is intractable.


title: CLAIRE: Combining Sets, Search And Rules To Better Express Algorithms

abstract: This paper presents a programming language which includes paradigms that are usually associated with declarative languages, such as sets, rules and search, into an imperative (functional) language. Although these paradigms are separately well known and are available under various programming environments, the originality of the CLAIRE language comes from the tight integration, which yields interesting run-time performances, and from the richness of this combination, which yields new ways in which to express complex algorithmic patterns with few elegant lines. To achieve the opposite goals of a high abstraction level (conciseness and readability) and run-time performance (CLAIRE is used as a C++ preprocessor), we have developed two kinds of compiler: first, a pattern pre-processor handles iterations over both concrete and abstract sets (data types and program fragments), in a completely user-extensible manner; secondly, an inference compiler transforms a set of logical rules into a set of functions (demons that are used through procedural attachment).


title: Learning Hybrid Algorithms for Vehicle Routing Problems

abstract: This paper presents a generic technique for improving hybrid algorithms through the discovery of and tuning of meta-heuristics. The idea is to represent a family of push/pull heuristics that are based upon inserting and removing tasks in a current solution, with an algebra. We then let a learning algorithm search for the best possible algebraic term, which represents a hybrid algorithm for a given set of problems and an optimization criterion. In a previous paper, we described this algebra in detail and provided a set of preliminary results demonstrating the utility of this approach, using vehicle routing with time windows (VRPTW) as a domain example. In this paper we expand upon our results providing a more robust experimental framework and learning algorithms, and report on some new results using the standard Solomon benchmarks. In particular, we show that our learning algorithm is able to achieve results similar to the best-published algorithms using only a fraction of the CPU time. We also show that the automatic tuning of the best hybrid combination of such techniques yields a better solution than hand tuning, with considerably less effort.


title: Computerized Face Detection and Recognition

abstract: This publication presents methods for face detection, analysis and recognition: fast normalized cross-correlation (fast correlation coefficient) between multiple templates based face pre-detection method, method for detection of exact face contour based on snakes and Generalized Gradient Vector Flow field, method for combining recognition algorithms based on Cumulative Match Characteristics in order to increase recognition speed and accuracy, and face recognition method based on Principal Component Analysis of the Wavelet Packet Decomposition allowing to use PCA - based recognition method with large number of training images. For all the methods are presented experimental results and comparisons of speed and accuracy with large face databases.


title: The Complexity of Maximum Matroid-Greedoid Intersection and Weighted Greedoid Maximization

abstract: The maximum intersection problem for a matroid and a greedoid, given by polynomial-time oracles, is shown $NP$-hard by expressing the satisfiability of boolean formulas in 3-conjunctive normal form as such an intersection. The corresponding approximation problems are shown $NP$-hard for certain approximation performance bounds. Moreover, some natural parameterized variants of the problem are shown $W[P]$-hard. The results are in contrast with the maximum matroid-matroid intersection which is solvable in polynomial time by an old result of Edmonds. We also prove that it is $NP$-hard to approximate the weighted greedoid maximization within $2^{n^{O(1)}}$ where $n$ is the size of the domain of the greedoid. A preliminary version ``The Complexity of Maximum Matroid-Greedoid Intersection'' appeared in Proc. FCT 2001, LNCS 2138, pp. 535--539, Springer-Verlag 2001.


title: Blind Detection and Compensation of Camera Lens Geometric Distortions

abstract: This paper presents a blind detection and compensation technique for camera lens geometric distortions. The lens distortion introduces higher-order correlations in the frequency domain and in turn it can be detected using higher-order spectral analysis tools without assuming any specific calibration target. The existing blind lens distortion removal method only considered a single-coefficient radial distortion model. In this paper, two coefficients are considered to model approximately the geometric distortion. All the models considered have analytical closed-form inverse formulae.


title: Developing Intellectual Network Management Facilities by Means of Pattern Recognition Theory

abstract: In this paper considered question of using pattern recognition methods in network equipment state identification.


title: A Coalgebraic Approach to Kleene Algebra with Tests

abstract: Kleene algebra with tests is an extension of Kleene algebra, the algebra of regular expressions, which can be used to reason about programs. We develop a coalgebraic theory of Kleene algebra with tests, along the lines of the coalgebraic theory of regular expressions based on deterministic automata. Since the known automata-theoretic presentation of Kleene algebra with tests does not lend itself to a coalgebraic theory, we define a new interpretation of Kleene algebra with tests expressions and a corresponding automata-theoretic presentation. One outcome of the theory is a coinductive proof principle, that can be used to establish equivalence of our Kleene algebra with tests expressions.


title: A Logic for Reasoning about Evidence

abstract: We introduce a logic for reasoning about evidence that essentially views evidence as a function from prior beliefs (before making an observation) to posterior beliefs (after making the observation). We provide a sound and complete axiomatization for the logic, and consider the complexity of the decision problem. Although the reasoning in the logic is mainly propositional, we allow variables representing numbers and quantification over them. This expressive power seems necessary to capture important properties of evidence.


title: Web search engine based on DNS

abstract: Now no web search engine can cover more than 60 percent of all the pages on Internet. The update interval of most pages database is almost one month. This condition hasn't changed for many years. Converge and recency problems have become the bottleneck problem of current web search engine. To solve these problems, a new system, search engine based on DNS is proposed in this paper. This system adopts the hierarchical distributed architecture like DNS, which is different from any current commercial search engine. In theory, this system can cover all the web pages on Internet. Its update interval could even be one day. The original idea, detailed content and implementation of this system all are introduced in this paper.


title: Typing constraint logic programs

abstract: We present a prescriptive type system with parametric polymorphism and subtyping for constraint logic programs. The aim of this type system is to detect programming errors statically. It introduces a type discipline for constraint logic programs and modules, while maintaining the capabilities of performing the usual coercions between constraint domains, and of typing meta-programming predicates, thanks to the flexibility of subtyping. The property of subject reduction expresses the consistency of a prescriptive type system w.r.t. the execution model: if a program is "well-typed", then all derivations starting from a "well-typed" goal are again "well-typed". That property is proved w.r.t. the abstract execution model of constraint programming which proceeds by accumulation of constraints only, and w.r.t. an enriched execution model with type constraints for substitutions. We describe our implementation of the system for type checking and type inference. We report our experimental results on type checking ISO-Prolog, the (constraint) libraries of Sicstus Prolog and other Prolog programs.


title: Worst-Case Groundness Analysis Using Definite Boolean Functions

abstract: This note illustrates theoretical worst-case scenarios for groundness analyses obtained through abstract interpretation over the abstract domains of definite (Def) and positive (Pos) Boolean functions. For Def, an example is given for which any Def-based abstract interpretation for groundness analysis follows a chain which is exponential in the number of argument positions as well as in the number of clauses but sub-exponential in the size of the program. For Pos, we strengthen a previous result by illustrating an example for which any Pos-based abstract interpretation for groundness analysis follows a chain which is exponential in the size of the program. It remains an open problem to determine if the worst case for Def is really as bad as that for Pos.


title: A Proof Theoretic Approach to Failure in Functional Logic Programming

abstract: How to extract negative information from programs is an important issue in logic programming. Here we address the problem for functional logic programs, from a proof-theoretic perspective. The starting point of our work is CRWL (Constructor based ReWriting Logic), a well established theoretical framework for functional logic programming, whose fundamental notion is that of non-strict non-deterministic function. We present a proof calculus, CRWLF, which is able to deduce negative information from CRWL-programs. In particular, CRWLF is able to prove finite failure of reduction within CRWL.


title: On model checking data-independent systems with arrays without reset

abstract: A system is data-independent with respect to a data type X iff the operations it can perform on values of type X are restricted to just equality testing. The system may also store, input and output values of type X. We study model checking of systems which are data-independent with respect to two distinct type variables X and Y, and may in addition use arrays with indices from X and values from Y . Our main interest is the following parameterised model-checking problem: whether a given program satisfies a given temporal-logic formula for all non-empty nite instances of X and Y . Initially, we consider instead the abstraction where X and Y are infinite and where partial functions with finite domains are used to model arrays. Using a translation to data-independent systems without arrays, we show that the u-calculus model-checking problem is decidable for these systems. From this result, we can deduce properties of all systems with finite instances of X and Y . We show that there is a procedure for the above parameterised model-checking problem of the universal fragment of the u-calculus, such that it always terminates but may give false negatives. We also deduce that the parameterised model-checking problem of the universal disjunction-free fragment of the u-calculus is decidable. Practical motivations for model checking data-independent systems with arrays include verification of memory and cache systems, where X is the type of memory addresses, and Y the type of storable values. As an example we verify a fault-tolerant memory interface over a set of unreliable memories.


title: Knowledge Reduction and Discovery based on Demarcation Information

abstract: Knowledge reduction, includes attribute reduction and value reduction, is an important topic in rough set literature. It is also closely relevant to other fields, such as machine learning and data mining. In this paper, an algorithm called TWI-SQUEEZE is proposed. It can find a reduct, or an irreducible attribute subset after two scans. Its soundness and computational complexity are given, which show that it is the fastest algorithm at present. A measure of variety is brought forward, of which algorithm TWI-SQUEEZE can be regarded as an application. The author also argues the rightness of this measure as a measure of information, which can make it a unified measure for "differentiation, a concept appeared in cognitive psychology literature. Value reduction is another important aspect of knowledge reduction. It is interesting that using the same algorithm we can execute a complete value reduction efficiently. The complete knowledge reduction, which results in an irreducible table, can therefore be accomplished after four scans of table. The byproducts of reduction are two classifiers of different styles. In this paper, various cases and models will be discussed to prove the efficiency and effectiveness of the algorithm. Some topics, such as how to integrate user preference to find a local optimal attribute subset will also be discussed.


title: Study of Pakistan Election System as Intelligent e-Election

abstract: The proposed election system lies in ensuring that it is transparent and impartial.Thus while the electoral system may vary from country to country, It has to take into account the peculiarities of every society while at the same time incorporating remedies to problems prevailing in the system. The Electoral process expressed serious concerns regarding the independence of the Election Commission of Pakistan, the restrictions on political parties and their candidates, the misuse of state resources, some unbalanced coverage in the state media, deficiencies in the compilation of the voting register and significant problems relating to the provision of ID cards. The holding of a general election does not in itself guarantee the restoration of democracy. The unjustified interference with electoral arrangements, as detailed above, irrespective of the alleged motivation, resulted in serious flaws being inflicted on the electoral process. Additionally, questions remain as to whether or not there will be a full transfer of power from a military to civilian administration. The Independent study research has following modules: Login/Subscription Module Candidate Subscription Module Vote casting Module Administration Module Intelligent decision data analysis Module


title: Pruning Search Space in Defeasible Argumentation

abstract: Defeasible argumentation has experienced a considerable growth in AI in the last decade. Theoretical results have been combined with development of practical applications in AI & Law, Case-Based Reasoning and various knowledge-based systems. However, the dialectical process associated with inference is computationally expensive. This paper focuses on speeding up this inference process by pruning the involved search space. Our approach is twofold. On one hand, we identify distinguished literals for computing defeat. On the other hand, we restrict ourselves to a subset of all possible conflicting arguments by introducing dialectical constraints.


title: A Framework for Combining Defeasible Argumentation with Labeled Deduction

abstract: In the last years, there has been an increasing demand of a variety of logical systems, prompted mostly by applications of logic in AI and other related areas. Labeled Deductive Systems (LDS) were developed as a flexible methodology to formalize such a kind of complex logical systems. Defeasible argumentation has proven to be a successful approach to formalizing commonsense reasoning, encompassing many other alternative formalisms for defeasible reasoning. Argument-based frameworks share some common notions (such as the concept of argument, defeater, etc.) along with a number of particular features which make it difficult to compare them with each other from a logical viewpoint. This paper introduces LDSar, a LDS for defeasible argumentation in which many important issues concerning defeasible argumentation are captured within a unified logical framework. We also discuss some logical properties and extensions that emerge from the proposed framework.


title: "User Interfaces" and the Social Negotiation of Availability

abstract: In current presence or availability systems, the method of presenting a user's state often supposes an instantaneous notion of that state - for example, a visualization is rendered or an inference is made about the potential actions that might be consistent with a user's state. Drawing on observational research on the use of existing communication technology, we argue (as have others in the past) that determination of availability is often a joint process, and often one that takes the form of a negotiation (whether implicit or explicit). We briefly describe our current research on applying machine learning to infer degrees of conversational engagement from observed conversational behavior. Such inferences can be applied to facilitate the implicit negotiation of conversational engagement - in effect, helping users to weave together the act of contact with the act of determining availability.


title: Conversation Analysis and the User Experience

abstract: We provide two case studies in the application of ideas drawn from conversation analysis to the design of technologies that enhance the experience of human conversation. We first present a case study of the design of an electronic guidebook, focusing on how conversation analytic principles played a role in the design process. We then discuss how the guidebook project has inspired our continuing work in social, mobile audio spaces. In particular, we describe some as yet unrealized concepts for adaptive audio spaces.


title: An analysis of a bounded resource search puzzle

abstract: Consider the commonly known puzzle, given $k$ glass balls, find an optimal algorithm to determine the lowest floor of a building of $n$ floors from which a thrown glass ball will break. This puzzle was originally posed in its original form in \cite{focs1980}and was later cited in the book \cite{algthc}. There are several internet sites that presents this puzzle and its solution to the special case of $k=2$ balls. This is the first such analysis of the puzzle in its general form. Several variations of this puzzle have been studied with applications in Network Loading \cite{cgstctl} which analyzes a case similar to a scenario where an adversary is changing the lowest floor with time. Although the algorithm specified in \cite{algthc} solves the problem, it is not an efficient algorithm. In this paper another algorithm for the same problem is analyzed. It is shown that if $m$ is the minimum number of attempts required then for $k \geq m$ we have $m = \log (n+1)$ and for $k < m$ we have, $1 + \sum_{i=1}^{k}{{m-1}\choose{i}} < n \leq \sum_{i=1}^{k}{{m}\choose{i}}$


title: Attrition Defenses for a Peer-to-Peer Digital Preservation System

abstract: In peer-to-peer systems, attrition attacks include both traditional, network-level denial of service attacks as well as application-level attacks in which malign peers conspire to waste loyal peers' resources. We describe several defenses for LOCKSS, a peer-to-peer digital preservation system, that help ensure that application-level attacks even from powerful adversaries are less effective than simple network-level attacks, and that network-level attacks must be intense, wide-spread, and prolonged to impair the system.


title: Really Straight Graph Drawings

abstract: This paper has been withdrawn by the authors. It has been replaced by the papers: "Drawings of Planar Graphs with Few Slopes and Segments" (math/0606450) and "Graph Drawings with Few Slopes" (math/0606446).


title: A proposal to design expert system for the calculations in the domain of QFT

abstract: Main purposes of the paper are followings: 1) To show examples of the calculations in domain of QFT via ``derivative rules'' of an expert system; 2) To consider advantages and disadvantage that technology of the calculations; 3) To reflect about how one would develop new physical theories, what knowledge would be useful in their investigations and how this problem can be connected with designing an expert system.


title: Side-Information Coding with Turbo Codes and its Application to Quantum Key Distribution

abstract: Turbo coding is a powerful class of forward error correcting codes, which can achieve performances close to the Shannon limit. The turbo principle can be applied to the problem of side-information source coding, and we investigate here its application to the reconciliation problem occurring in a continuous-variable quantum key distribution protocol.


title: A novel approach to symbolic algebra

abstract: A prototype for an extensible interactive graphical term manipulation system is presented that combines pattern matching and nondeterministic evaluation to provide a convenient framework for doing tedious algebraic manipulations that so far had to be done manually in a semi-automatic fashion.


title: Algorithms for weighted multi-tape automata

abstract: This report defines various operations for weighted multi-tape automata (WMTAs) and describes algorithms that have been implemented for those operations in the WFSC toolkit. Some algorithms are new, others are known or similar to known algorithms. The latter will be recalled to make this report more complete and self-standing. We present a new approach to multi-tape intersection, meaning the intersection of a number of tapes of one WMTA with the same number of tapes of another WMTA. In our approach, multi-tape intersection is not considered as an atomic operation but rather as a sequence of more elementary ones, which facilitates its implementation. We show an example of multi-tape intersection, actually transducer intersection, that can be compiled with our approach but not with several other methods that we analysed. To show the practical relavance of our work, we include an example of application: the preservation of intermediate results in transduction cascades.


title: Application of Business Intelligence In Banks (Pakistan)

abstract: The financial services industry is rapidly changing. Factors such as globalization, deregulation, mergers and acquisitions, competition from non-financial institutions, and technological innovation, have forced companies to re-think their business.Many large companies have been using Business Intelligence (BI) computer software for some years to help them gain competitive advantage. With the introduction of cheaper and more generalized products to the market place BI is now in the reach of smaller and medium sized companies. Business Intelligence is also known as knowledge management, management information systems (MIS), Executive information systems (EIS) and On-line analytical Processing (OLAP).


title: Microreboot -- A Technique for Cheap Recovery

abstract: A significant fraction of software failures in large-scale Internet systems are cured by rebooting, even when the exact failure causes are unknown. However, rebooting can be expensive, causing nontrivial service disruption or downtime even when clusters and failover are employed. In this work we separate process recovery from data recovery to enable microrebooting -- a fine-grain technique for surgically recovering faulty application components, without disturbing the rest of the application. We evaluate microrebooting in an Internet auction system running on an application server. Microreboots recover most of the same failures as full reboots, but do so an order of magnitude faster and result in an order of magnitude savings in lost work. This cheap form of recovery engenders a new approach to high availability: microreboots can be employed at the slightest hint of failure, prior to node failover in multi-node clusters, even when mistakes in failure detection are likely; failure and recovery can be masked from end users through transparent call-level retries; and systems can be rejuvenated by parts, without ever being shut down.


title: Dichotomy Theorems for Alternation-Bounded Quantified Boolean Formulas

abstract: In 1978, Schaefer proved his famous dichotomy theorem for generalized satisfiability problems. He defined an infinite number of propositional satisfiability problems, showed that all these problems are either in P or NP-complete, and gave a simple criterion to determine which of the two cases holds. This result is surprising in light of Ladner's theorem, which implies that there are an infinite number of complexity classes between P and NP-complete (under the assumption that P is not equal to NP). Schaefer also stated a dichotomy theorem for quantified generalized Boolean formulas, but this theorem was only recently proven by Creignou, Khanna, and Sudan, and independently by Dalmau: Determining truth of quantified Boolean formulas is either PSPACE-complete or in P. This paper looks at alternation-bounded quantified generalized Boolean formulas. In their unrestricted forms, these problems are the canonical problems complete for the levels of the polynomial hierarchy. In this paper, we prove dichotomy theorems for alternation-bounded quantified generalized Boolean formulas, by showing that these problems are either $\Sigma_i^p$-complete or in P, and we give a simple criterion to determine which of the two cases holds. This is the first result that obtains dichotomy for an infinite number of classes at once.


title: Parallel Mixed Bayesian Optimization Algorithm: A Scaleup Analysis

abstract: Estimation of Distribution Algorithms have been proposed as a new paradigm for evolutionary optimization. This paper focuses on the parallelization of Estimation of Distribution Algorithms. More specifically, the paper discusses how to predict performance of parallel Mixed Bayesian Optimization Algorithm (MBOA) that is based on parallel construction of Bayesian networks with decision trees. We determine the time complexity of parallel Mixed Bayesian Optimization Algorithm and compare this complexity with experimental results obtained by solving the spin glass optimization problem. The empirical results fit well the theoretical time complexity, so the scalability and efficiency of parallel Mixed Bayesian Optimization Algorithm for unknown instances of spin glass benchmarks can be predicted. Furthermore, we derive the guidelines that can be used to design effective parallel Estimation of Distribution Algorithms with the speedup proportional to the number of variables in the problem.


title: Image compression by rectangular wavelet transform

abstract: We study image compression by a separable wavelet basis $\big\{\psi(2^{k_1}x-i)\psi(2^{k_2}y-j),$ $\phi(x-i)\psi(2^{k_2}y-j),$ $\psi(2^{k_1}(x-i)\phi(y-j),$ $\phi(x-i)\phi(y-i)\big\},$ where $k_1, k_2 \in \mathbb{Z}_+$; $i,j\in\mathbb{Z}$; and $\phi,\psi$ are elements of a standard biorthogonal wavelet basis in $L_2(\mathbb{R})$. Because $k_1\ne k_2$, the supports of the basis elements are rectangles, and the corresponding transform is known as the {\em rectangular wavelet transform}. We prove that if one-dimensional wavelet basis has $M$ dual vanishing moments then the rate of approximation by $N$ coefficients of rectangular wavelet transform is $\mathcal{O}(N^{-M}\log^C N)$ for functions with mixed derivative of order $M$ in each direction. The square wavelet transform yields the approximation rate is $\mathcal{O}(N^{-M/2})$ for functions with all derivatives of the total order $M$. Thus, the rectangular wavelet transform can outperform the square one if an image has a mixed derivative. We provide experimental comparison of image compression which shows that rectangular wavelet transform outperform the square one.


title: Implementation of Logical Functions in the Game of Life

abstract: The Game of Life cellular automaton is a classical example of a massively parallel collision-based computing device. The automaton exhibits mobile patterns, gliders, and generators of the mobile patterns, glider guns, in its evolution. We show how to construct the basic logical operations, AND, OR, NOT in space-time configurations of the cellular automaton. Also decomposition of complicated Boolean functions is discussed. Advantages of our technique are demonstrated on an example of binary adder, realized via collision of glider streams.


title: Another Proof of an Extension of a Curious Identity

abstract: Based on Jensen formulae and the second kind of Chebyshev polynomials, another proof is presented for an extension of a curious binomial identity due to Z. W. Sun and K. J. Wu.


title: Blind Construction of Optimal Nonlinear Recursive Predictors for Discrete Sequences

abstract: We present a new method for nonlinear prediction of discrete random sequences under minimal structural assumptions. We give a mathematical construction for optimal predictors of such processes, in the form of hidden Markov models. We then describe an algorithm, CSSR (Causal-State Splitting Reconstruction), which approximates the ideal predictor from data. We discuss the reliability of CSSR, its data requirements, and its performance in simulations. Finally, we compare our approach to existing methods using variable-length Markov models and cross-validated hidden Markov models, and show theoretically and experimentally that our method delivers results superior to the former and at least comparable to the latter.

categories: cs.LG math.ST nlin.CD physics.data-an stat.TH


title: Secure Prolog-Based Mobile Code

abstract: LogicWeb mobile code consists of Prolog-like rules embedded in Web pages, thereby adding logic programming behaviour to those pages. Since LogicWeb programs are downloaded from foreign hosts and executed locally, there is a need to protect the client from buggy or malicious code. A security model is crucial for making LogicWeb mobile code safe to execute. This paper presents such a model, which supports programs of varying trust levels by using different resource access policies. The implementation of the model derives from an extended operational semantics for the LogicWeb language, which provides a precise meaning of safety.


title: Optimization of Bound Disjunctive Queries with Constraints

abstract: "To Appear in Theory and Practice of Logic Programming (TPLP)" This paper presents a technique for the optimization of bound queries over disjunctive deductive databases with constraints. The proposed approach is an extension of the well-known Magic-Set technique and is well-suited for being integrated in current bottom-up (stable) model inference engines. More specifically, it is based on the exploitation of binding propagation techniques which reduce the size of the data relevant to answer the query and, consequently, reduces both the complexity of computing a single model and the number of models to be considered. The motivation of this work stems from the observation that traditional binding propagation optimization techniques for bottom-up model generator systems, simulating the goal driven evaluation of top-down engines, are only suitable for positive (disjunctive) queries, while hard problems are expressed using unstratified negation. The main contribution of the paper consists in the extension of a previous technique, defined for positive disjunctive queries, to queries containing both disjunctive heads and constraints (a simple and expressive form of unstratified negation). As the usual way of expressing declaratively hard problems is based on the guess-and-check technique, where the guess part is expressed by means of disjunctive rules and the check part is expressed by means of constraints, the technique proposed here is highly relevant for the optimization of queries expressing hard problems. The value of the technique has been proved by several experiments.


title: O(1) Reversible Tree Navigation Without Cycles

abstract: Imperative programmers often use cyclically linked trees in order to achieve O(1) navigation time to neighbours. Some logic programmers believe that cyclic terms are necessary to achieve the same in logic-based languages. An old but little-known technique provides O(1) time and space navigation without cyclic links, in the form of reversible predicates. A small modification provides O(1) amortised time and space editing.


title: Zipf's law and the creation of musical context

abstract: This article discusses the extension of the notion of context from linguistics to the domain of music. In language, the statistical regularity known as Zipf's law -which concerns the frequency of usage of different words- has been quantitatively related to the process of text generation. This connection is established by Simon's model, on the basis of a few assumptions regarding the accompanying creation of context. Here, it is shown that the statistics of note usage in musical compositions are compatible with the predictions of Simon's model. This result, which gives objective support to the conceptual likeness of context in language and music, is obtained through automatic analysis of the digital versions of several compositions. As a by-product, a quantitative measure of context definiteness is introduced and used to compare tonal and atonal works.


title: Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams

abstract: We introduce an extension of the XQuery language, FluX, that supports event-based query processing and the conscious handling of main memory buffers. Purely event-based queries of this language can be executed on streaming XML data in a very direct way. We then develop an algorithm that allows to efficiently rewrite XQueries into the event-based FluX language. This algorithm uses order constraints from a DTD to schedule event handlers and to thus minimize the amount of buffering required for evaluating a query. We discuss the various technical aspects of query optimization and query evaluation within our framework. This is complemented with an experimental evaluation of our approach.


title: Using Self-Organising Mappings to Learn the Structure of Data Manifolds

abstract: In this paper it is shown how to map a data manifold into a simpler form by progressively discarding small degrees of freedom. This is the key to self-organising data fusion, where the raw data is embedded in a very high-dimensional space (e.g. the pixel values of one or more images), and the requirement is to isolate the important degrees of freedom which lie on a low-dimensional manifold. A useful advantage of the approach used in this paper is that the computations are arranged as a feed-forward processing chain, where all the details of the processing in each stage of the chain are learnt by self-organisation. This approach is demonstrated using hierarchically correlated data, which causes the processing chain to split the data into separate processing channels, and then to progressively merge these channels wherever they are correlated with each other. This is the key to self-organising data fusion.


title: Effects of wireless computing technology

abstract: Wireless technology can provide many benefits to computing including faster response to queries, reduced time spent on paperwork, increased online time for users, just-in-time and real time control, tighter communications between clients and hosts. Wireless Computing is governed by two general forces: Technology, which provides a set of basic building blocks and User Applications, which determine a set of operations that must be carried out efficiently on demand. This paper summarizes technological changes that are underway and describes their impact on wireless computing development and implementation. It also describes the applications that influence the development and implementation of wireless computing and shows what current systems offer.


title: Providing Service Guarantees in High-Speed Switching Systems with Feedback Output Queuing

abstract: We consider the problem of providing service guarantees in a high-speed packet switch. As basic requirements, the switch should be scalable to high speeds per port, a large number of ports and a large number of traffic flows with independent guarantees. Existing scalable solutions are based on Virtual Output Queuing, which is computationally complex when required to provide service guarantees for a large number of flows. We present a novel architecture for packet switching that provides support for such service guarantees. A cost-effective fabric with small external speedup is combined with a feedback mechanism that enables the fabric to be virtually lossless, thus avoiding packet drops indiscriminate of flows. Through analysis and simulation, we show that this architecture provides accurate support for service guarantees, has low computational complexity and is scalable to very high port speeds.


title: Algorithms for Drawing Media

abstract: We describe algorithms for drawing media, systems of states, tokens and actions that have state transition graphs in the form of partial cubes. Our algorithms are based on two principles: embedding the state transition graph in a low-dimensional integer lattice and projecting the lattice onto the plane, or drawing the medium as a planar graph with centrally symmetric faces.


title: A direct formulation for sparse PCA using semidefinite programming

abstract: We examine the problem of approximating, in the Frobenius-norm sense, a positive, semidefinite symmetric matrix by a rank-one matrix, with an upper bound on the cardinality of its eigenvector. The problem arises in the decomposition of a covariance matrix into sparse factors, and has wide applications ranging from biology to finance. We use a modification of the classical variational representation of the largest eigenvalue of a symmetric matrix, where cardinality is constrained, and derive a semidefinite programming based relaxation for our problem. We also discuss Nesterov's smooth minimization technique applied to the SDP arising in the direct sparse PCA method.


title: Uncovering the epistemological and ontological assumptions of software designers

abstract: The ontological and epistemological positions adopted by information systems design methods are incommensur-able when pushed to their extremes. Information systems research has therefore tended to focus on the similarities between different positions, usually in search of a single, unifying position. However, by focusing on the similari-ties, the clarity of argument provided by any one philoso-phical position is necessarily diminished. Consequently, researchers often treat the philosophical foundations of design methods as being of only minor importance. In this paper, we have deliberately chosen to focus on the differences between various philosophical positions. From this focus, we believe we can offer a clearer under-standing of the empirical behaviour of software as viewed from particular philosophical positions. Since the em-pirical evidence does not favour any single position, we conclude by arguing for the validity of ad hoc approaches to software design which we believe provides a stronger and more theoretically grounded approach to software design.


title: Notions of Equivalence in Software Design

abstract: Design methods in information systems frequently create software descriptions using formal languages. Nonetheless, most software designers prefer to describe software using natural languages. This distinction is not simply a matter of convenience. Natural languages are not the same as formal languages; in particular, natural languages do not follow the notions of equivalence used by formal languages. In this paper, we show both the existence and coexistence of different notions of equivalence by extending the no-tion of oracles used in formal languages. This allows distinctions to be made between the trustworthy oracles assumed by formal languages and the untrust-worthy oracles used by natural languages. By examin-ing the notion of equivalence, we hope to encourage designers of software to rethink the place of ambiguity in software design.


title: Layout of Graphs with Bounded Tree-Width

abstract: A \emph{queue layout} of a graph consists of a total order of the vertices, and a partition of the edges into \emph{queues}, such that no two edges in the same queue are nested. The minimum number of queues in a queue layout of a graph is its \emph{queue-number}. A \emph{three-dimensional (straight-line grid) drawing} of a graph represents the vertices by points in $\mathbb{Z}^3$ and the edges by non-crossing line-segments. This paper contributes three main results: (1) It is proved that the minimum volume of a certain type of three-dimensional drawing of a graph $G$ is closely related to the queue-number of $G$. In particular, if $G$ is an $n$-vertex member of a proper minor-closed family of graphs (such as a planar graph), then $G$ has a $O(1)\times O(1)\times O(n)$ drawing if and only if $G$ has O(1) queue-number. (2) It is proved that queue-number is bounded by tree-width, thus resolving an open problem due to Ganley and Heath (2001), and disproving a conjecture of Pemmaraju (1992). This result provides renewed hope for the positive resolution of a number of open problems in the theory of queue layouts. (3) It is proved that graphs of bounded tree-width have three-dimensional drawings with O(n) volume. This is the most general family of graphs known to admit three-dimensional drawings with O(n) volume. The proofs depend upon our results regarding \emph{track layouts} and \emph{tree-partitions} of graphs, which may be of independent interest.


title: Directional Consistency for Continuous Numerical Constraints

abstract: Bounds consistency is usually enforced on continuous constraints by first decomposing them into binary and ternary primitives. This decomposition has long been shown to drastically slow down the computation of solutions. To tackle this, Benhamou et al. have introduced an algorithm that avoids formally decomposing constraints. Its better efficiency compared to the former method has already been experimentally demonstrated. It is shown here that their algorithm implements a strategy to enforce on a continuous constraint a consistency akin to Directional Bounds Consistency as introduced by Dechter and Pearl for discrete problems. The algorithm is analyzed in this framework, and compared with algorithms that enforce bounds consistency. These theoretical results are eventually contrasted with new experimental results on standard benchmarks from the interval constraint community.


title: Improving Prolog Programs: Refactoring for Prolog

abstract: Refactoring is an established technique from the OO-community to restructure code: it aims at improving software readability, maintainability and extensibility. Although refactoring is not tied to the OO-paradigm in particular, its ideas have not been applied to Logic Programming until now. This paper applies the ideas of refactoring to Prolog programs. A catalogue is presented listing refactorings classified according to scope. Some of the refactorings have been adapted from the OO-paradigm, while others have been specifically designed for Prolog. Also the discrepancy between intended and operational semantics in Prolog is addressed by some of the refactorings. In addition, ViPReSS, a semi-automatic refactoring browser, is discussed and the experience with applying \vipress to a large Prolog legacy system is reported. Our main conclusion is that refactoring is not only a viable technique in Prolog but also a rather desirable one.


title: Fluctuation in Peer-to-Peer Networks: Mitigating Its Effect on DHT Performance

abstract: Due to the transient nature of peers, any Peer-to-Peer network is in peril to falling apart if peers do not receive routing table updates periodically. To this end, maintenance, which affects every peer, ensures connectedness and sustained data operation performance. However, a high rate of change in peer population usually incurs lots of network maintenance messages and can severely degrade overall performance. We discuss three methods how to tackle and mitigate the effect of peer fluctuation on a tree-based distributed hash table.


title: Ramsey-type theorems for metric spaces with applications to online problems

abstract: A nearly logarithmic lower bound on the randomized competitive ratio for the metrical task systems problem is presented. This implies a similar lower bound for the extensively studied k-server problem. The proof is based on Ramsey-type theorems for metric spaces, that state that every metric space contains a large subspace which is approximately a hierarchically well-separated tree (and in particular an ultrametric). These Ramsey-type theorems may be of independent interest.


title: Subset Queries in Relational Databases

abstract: In this paper, we motivated the need for relational database systems to support subset query processing. We defined new operators in relational algebra, and new constructs in SQL for expressing subset queries. We also illustrated the applicability of subset queries through different examples expressed using extended SQL statements and relational algebra expressions. Our aim is to show the utility of subset queries for next generation applications.


title: Abstract Canonical Inference

abstract: An abstract framework of canonical inference is used to explore how different proof orderings induce different variants of saturation and completeness. Notions like completion, paramodulation, saturation, redundancy elimination, and rewrite-system reduction are connected to proof orderings. Fairness of deductive mechanisms is defined in terms of proof orderings, distinguishing between (ordinary) "fairness," which yields completeness, and "uniform fairness," which yields saturation.


title: A Public Reference Implementation of the RAP Anaphora Resolution Algorithm

abstract: This paper describes a standalone, publicly-available implementation of the Resolution of Anaphora Procedure (RAP) given by Lappin and Leass (1994). The RAP algorithm resolves third person pronouns, lexical anaphors, and identifies pleonastic pronouns. Our implementation, JavaRAP, fills a current need in anaphora resolution research by providing a reference implementation that can be benchmarked against current algorithms. The implementation uses the standard, publicly available Charniak (2000) parser as input, and generates a list of anaphora-antecedent pairs as output. Alternately, an in-place annotation or substitution of the anaphors with their antecedents can be produced. Evaluation on the MUC-6 co-reference task shows that JavaRAP has an accuracy of 57.9%, similar to the performance given previously in the literature (e.g., Preiss 2002).


title: A Dynamic Clustering-Based Markov Model for Web Usage Mining

abstract: Markov models have been widely utilized for modelling user web navigation behaviour. In this work we propose a dynamic clustering-based method to increase a Markov model's accuracy in representing a collection of user web navigation sessions. The method makes use of the state cloning concept to duplicate states in a way that separates in-links whose corresponding second-order probabilities diverge. In addition, the new method incorporates a clustering technique which determines an effcient way to assign in-links with similar second-order probabilities to the same clone. We report on experiments conducted with both real and random data and we provide a comparison with the N-gram Markov concept. The results show that the number of additional states induced by the dynamic clustering method can be controlled through a threshold parameter, and suggest that the method's performance is linear time in the size of the model.


title: Randomized k-server algorithms for growth-rate bounded graphs

abstract: The paper referred to in the title is withdrawn.


title: Better algorithms for unfair metrical task systems and applications

abstract: Unfair metrical task systems are a generalization of online metrical task systems. In this paper we introduce new techniques to combine algorithms for unfair metrical task systems and apply these techniques to obtain improved randomized online algorithms for metrical task systems on arbitrary metric spaces.


title: Optimal Free-Space Management and Routing-Conscious Dynamic Placement for Reconfigurable Devices

abstract: We describe algorithmic results for two crucial aspects of allocating resources on computational hardware devices with partial reconfigurability. By using methods from the field of computational geometry, we derive a method that allows correct maintainance of free and occupied space of a set of n rectangular modules in optimal time Theta(n log n); previous approaches needed a time of O(n^2) for correct results and O(n) for heuristic results. We also show that finding an optimal feasible communication-conscious placement (which minimizes the total weighted Manhattan distance between the new module and existing demand points) can be computed in Theta(n log n). Both resulting algorithms are practically easy to implement and show convincing experimental behavior.


title: Online Companion Caching

abstract: This paper is concerned with online caching algorithms for the (n,k)-companion cache, defined by Brehob et. al. In this model the cache is composed of two components: a k-way set-associative cache and a companion fully-associative cache of size n. We show that the deterministic competitive ratio for this problem is (n+1)(k+1)-1, and the randomized competitive ratio is O(\log n \log k) and \Omega(\log n +\log k).


title: Propositional Computability Logic II

abstract: Computability logic is a formal theory of computational tasks and resources. Its formulas represent interactive computational problems, logical operators stand for operations on computational problems, and validity of a formula is understood as being a scheme of problems that always have algorithmic solutions. A comprehensive online source on the subject is available at http://www.cis.upenn.edu/~giorgi/cl.html . The earlier article "Propositional computability logic I" proved soundness and completeness for the (in a sense) minimal nontrivial fragment CL1 of computability logic. The present paper extends that result to the significantly more expressive propositional system CL2. What makes CL2 more expressive than CL1 is the presence of two sorts of atoms in its language: elementary atoms, representing elementary computational problems (i.e. predicates), and general atoms, representing arbitrary computational problems. CL2 conservatively extends CL1, with the latter being nothing but the general-atom-free fragment of the former.


title: A New Approach to Draw Detection by Move Repetition in Computer Chess Programming

abstract: We will try to tackle both the theoretical and practical aspects of a very important problem in chess programming as stated in the title of this article - the issue of draw detection by move repetition. The standard approach that has so far been employed in most chess programs is based on utilising positional matrices in original and compressed format as well as on the implementation of the so-called bitboard format. The new approach that we will be trying to introduce is based on using variant strings generated by the search algorithm (searcher) during the tree expansion in decision making. We hope to prove that this approach is more efficient than the standard treatment of the issue, especially in positions with few pieces (endgames). To illustrate what we have in mind a machine language routine that implements our theoretical assumptions is attached. The routine is part of the Axon chess program, developed by the authors. Axon, in its current incarnation, plays chess at master strength (ca. 2400-2450 Elo, based on both Axon vs computer programs and Axon vs human masters in over 3000 games altogether).


title: Long Nonbinary Codes Exceeding the Gilbert - Varshamov Bound for any Fixed Distance

abstract: Let A(q,n,d) denote the maximum size of a q-ary code of length n and distance d. We study the minimum asymptotic redundancy \rho(q,n,d)=n-log_q A(q,n,d) as n grows while q and d are fixed. For any d and q<=d-1, long algebraic codes are designed that improve on the BCH codes and have the lowest asymptotic redundancy \rho(q,n,d) <= ((d-3)+1/(d-2)) log_q n known to date. Prior to this work, codes of fixed distance that asymptotically surpass BCH codes and the Gilbert-Varshamov bound were designed only for distances 4,5 and 6.


title: Alchemistry of the P versus NP question

abstract: Are P and NP provably inseparable ? Take a look at some unorthodox, guilty mentioned folklore and related unpublished results.


title: Non-Termination Inference of Logic Programs

abstract: We present a static analysis technique for non-termination inference of logic programs. Our framework relies on an extension of the subsumption test, where some specific argument positions can be instantiated while others are generalized. We give syntactic criteria to statically identify such argument positions from the text of a program. Atomic left looping queries are generated bottom-up from selected subsets of the binary unfoldings of the program of interest. We propose a set of correct algorithms for automating the approach. Then, non-termination inference is tailored to attempt proofs of optimality of left termination conditions computed by a termination inference tool. An experimental evaluation is reported. When termination and non-termination analysis produce complementary results for a logic procedure, then with respect to the leftmost selection rule and the language used to describe sets of atomic queries, each analysis is optimal and together, they induce a characterization of the operational behavior of the logic procedure.


title: Business Process Measures

abstract: The paper proposes a new methodology for defining business process measures and their computation. The approach is based on metamodeling according to MOF. Especially, a metamodel providing precise definitions of typical process measures for UML activity diagram-like notation is proposed, including precise definitions how measures should be aggregated for composite process elements. The proposed approach allows defining values in a natural way, and measurement of data, which are of interest to business, without deep investigation into specific technical solutions. This provides new possibilities for business process measurement, decreasing the gap between technical solutions and asset management methodologies.


title: The Computational Complexity of Orientation Search Problems in Cryo-Electron Microscopy

abstract: In this report we study the problem of determining three-dimensional orientations for noisy projections of randomly oriented identical particles. The problem is of central importance in the tomographic reconstruction of the density map of macromolecular complexes from electron microscope images and it has been studied intensively for more than 30 years. We analyze the computational complexity of the orientation problem and show that while several variants of the problem are $NP$-hard, inapproximable and fixed-parameter intractable, some restrictions are polynomial-time approximable within a constant factor or even solvable in logarithmic space. The orientation search problem is formalized as a constrained line arrangement problem that is of independent interest. The negative complexity results give a partial justification for the heuristic methods used in orientation search, and the positive complexity results on the orientation search have some positive implications also to the problem of finding functionally analogous genes. A preliminary version ``The Computational Complexity of Orientation Search in Cryo-Electron Microscopy'' appeared in Proc. ICCS 2004, LNCS 3036, pp. 231--238. Springer-Verlag 2004.


title: On the Computational Complexity of the Forcing Chromatic Number

abstract: We consider vertex colorings of graphs in which adjacent vertices have distinct colors. A graph is $s$-chromatic if it is colorable in $s$ colors and any coloring of it uses at least $s$ colors. The forcing chromatic number $F(G)$ of an $s$-chromatic graph $G$ is the smallest number of vertices which must be colored so that, with the restriction that $s$ colors are used, every remaining vertex has its color determined uniquely. We estimate the computational complexity of $F(G)$ relating it to the complexity class US introduced by Blass and Gurevich. We prove that recognizing if $F(G)\le 2$ is US-hard with respect to polynomial-time many-one reductions. Moreover, this problem is coNP-hard even under the promises that $F(G)\le 3$ and $G$ is 3-chromatic. On the other hand, recognizing if $F(G)\le k$, for each constant $k$, is reducible to a problem in US via disjunctive truth-table reduction. Similar results are obtained also for forcing variants of the clique and the domination numbers of a graph.


title: Online Searching with Turn Cost

abstract: We consider the problem of searching for an object on a line at an unknown distance OPT from the original position of the searcher, in the presence of a cost of d for each time the searcher changes direction. This is a generalization of the well-studied linear-search problem. We describe a strategy that is guaranteed to find the object at a cost of at most 9*OPT + 2d, which has the optimal competitive ratio 9 with respect to OPT plus the minimum corresponding additive term. Our argument for upper and lower bound uses an infinite linear program, which we solve by experimental solution of an infinite series of approximating finite linear programs, estimating the limits, and solving the resulting recurrences. We feel that this technique is interesting in its own right and should help solve other searching problems. In particular, we consider the star search or cow-path problem with turn cost, where the hidden object is placed on one of m rays emanating from the original position of the searcher. For this problem we give a tight bound of (1+(2(m^m)/((m-1)^(m-1))) OPT + m ((m/(m-1))^(m-1) - 1) d. We also discuss tradeoff between the corresponding coefficients, and briefly consider randomized strategies on the line.


title: Cheap Recovery: A Key to Self-Managing State

abstract: Cluster hash tables (CHTs) are a key persistent-storage component of many large-scale Internet services due to their high performance and scalability. We show that a correctly-designed CHT can also be as easy to manage as a farm of stateless servers. Specifically, we trade away some consistency to obtain reboot-based recovery that is simple, maintains full data availability, and only has modest impact on performance. This simplifies management in two ways. First, it simplifies failure detection by lowering the cost of acting on false positives, allowing us to use simple but aggressive statistical techniques to quickly detect potential failures and node degradations; even when a false alarm is raised or when rebooting will not fix the problem, attempting recovery by rebooting is relatively non-intrusive to system availability and performance. Second, it allows us to re-cast online repartitioning as failure plus recovery, simplifying dynamic scaling and capacity planning. These properties make it possible for the system to be continuously self-adjusting, a key property of self-managing, autonomic systems.


title: Self-organizing neural networks in classification and image recognition

abstract: Self-organizing neural networks are used for brick finding in OPERA experiment. Self-organizing neural networks and wavelet analysis used for recognition and extraction of car numbers from images.


title: On Expanders Graphs: Parameters and Applications

abstract: We give a new lower bound on the expansion coefficient of an edge-vertex graph of a $d$-regular graph. As a consequence, we obtain an improvement on the lower bound on relative minimum distance of the expander codes constructed by Sipser and Spielman. We also derive some improved results on the vertex expansion of graphs that help us in improving the parameters of the expander codes of Alon, Bruck, Naor, Naor, and Roth.


title: A Fast, Vectorizable Algorithm for Producing Single-Precision Sine-Cosine Pairs

abstract: This paper presents an algorithm for computing Sine-Cosine pairs to modest accuracy, but in a manner which contains no conditional tests or branching, making it highly amenable to vectorization. An exemplary implementation for PowerPC AltiVec processors is included, but the algorithm should be easily portable to other achitectures, such as Intel SSE.


title: Finite-Length Scaling for Iteratively Decoded LDPC Ensembles

abstract: In this paper we investigate the behavior of iteratively decoded low-density parity-check codes over the binary erasure channel in the so-called ``waterfall region." We show that the performance curves in this region follow a very basic scaling law. We conjecture that essentially the same scaling behavior applies in a much more general setting and we provide some empirical evidence to support this conjecture. The scaling law, together with the error floor expressions developed previously, can be used for fast finite-length optimization.


title: Stable Outcomes for Two-Sided Contract Choice Problems

abstract: We show, that a simple generalization of the Deferred Acceptance Procedure with firms proposing due to Gale and Shapley(1962), yeild outcomes for a two-sided contract choice problem, which necessarily belong to the core and are Weakly Pareto Optimal for firms. Under additional assumptions: (a) given any two distinct workers, the set of yields acheivable by a firm with the first worker is disjoint from the set of yields acheivable by it with the second, and (b) the contract choice problem is pair-wise efficient, we prove that there is no stable outcome at which a firm can get more than what it gets at the unique outcome of our procedure.


title: NoSEBrEaK - Attacking Honeynets

abstract: It is usually assumed that Honeynets are hard to detect and that attempts to detect or disable them can be unconditionally monitored. We scrutinize this assumption and demonstrate a method how a host in a honeynet can be completely controlled by an attacker without any substantial logging taking place.


title: Approximation Algorithms for Minimum PCR Primer Set Selection with Amplification Length and Uniqueness Constraints

abstract: A critical problem in the emerging high-throughput genotyping protocols is to minimize the number of polymerase chain reaction (PCR) primers required to amplify the single nucleotide polymorphism loci of interest. In this paper we study PCR primer set selection with amplification length and uniqueness constraints from both theoretical and practical perspectives. We give a greedy algorithm that achieves a logarithmic approximation factor for the problem of minimizing the number of primers subject to a given upperbound on the length of PCR amplification products. We also give, using randomized rounding, the first non-trivial approximation algorithm for a version of the problem that requires unique amplification of each amplification target. Empirical results on randomly generated testcases as well as testcases extracted from the from the National Center for Biotechnology Information's genomic databases show that our algorithms are highly scalable and produce better results compared to previous heuristics.


title: Building a linguistic corpus from bee dance data

abstract: This paper discusses the problems and possibility of collecting bee dance data in a linguistic \textit{corpus} and use linguistic instruments such as Zipf's law and entropy statistics to decide on the question whether the dance carries information of any kind. We describe this against the historical background of attempts to analyse non-human communication systems.


title: Web Services: A Process Algebra Approach

abstract: It is now well-admitted that formal methods are helpful for many issues raised in the Web service area. In this paper we present a framework for the design and verification of WSs using process algebras and their tools. We define a two-way mapping between abstract specifications written using these calculi and executable Web services written in BPEL4WS. Several choices are available: design and correct errors in BPEL4WS, using process algebra verification tools, or design and correct in process algebra and automatically obtaining the corresponding BPEL4WS code. The approaches can be combined. Process algebra are not useful only for temporal logic verification: we remark the use of simulation/bisimulation both for verification and for the hierarchical refinement design method. It is worth noting that our approach allows the use of any process algebra depending on the needs of the user at different levels (expressiveness, existence of reasoning tools, user expertise).


title: P=NP

abstract: We claim to resolve the P=?NP problem via a formal argument for P=NP.


title: Modelling the costs and benefits of Honeynets

abstract: For many IT-security measures exact costs and benefits are not known. This makes it difficult to allocate resources optimally to different security measures. We present a model for costs and benefits of so called Honeynets. This can foster informed reasoning about the deployment of honeynet technology.


title: Proofs of Zero Knowledge

abstract: We present a protocol for verification of ``no such entry'' replies from databases. We introduce a new cryptographic primitive as the underlying structure, the keyed hash tree, which is an extension of Merkle's hash tree. We compare our scheme to Buldas et al.'s Undeniable Attesters and Micali et al.'s Zero Knowledge Sets.


title: Ermittlung von Verwundbarkeiten mit elektronischen Koedern

abstract: Electronic bait (honeypots) are network resources whose value consists of being attacked and compromised. These are often computers which do not have a task in the network, but are otherwise indestinguishable from regular computers. Such bait systems could be interconnected (honeynets). These honeynets are equipped with special software, facilitating forensic anylisis of incidents. Taking average of the wide variety of recorded data it is possible to learn considerable more about the behaviour of attackers in networks than with traditional methods. This article is an introduction into electronic bait and a description of the setup and first experiences of such a network deployed at RWTH Aachen University. ----- Als elektronische Koeder (honeypots) bezeichnet man Netzwerkressourcen, deren Wert darin besteht, angegriffen und kompromittiert zu werden. Oft sind dies Computer, die keine spezielle Aufgabe im Netzwerk haben, aber ansonsten nicht von regulaeren Rechnern zu unterscheiden sind. Koeder koennen zu Koeder-Netzwerken (honeynets) zusammengeschlossen werden. Sie sind mit spezieller Software ausgestattet, die die Forensik einer eingetretenen Schutzzielverletzung erleichtert. Durch die Vielfalt an mitgeschnittenen Daten kann man deutlich mehr ueber das Verhalten von Angreifern in Netzwerken lernen als mit herkoemmlichen forensischen Methoden. Dieser Beitrag stellt die Philosophie der Koeder-Netzwerke vor und beschreibt die ersten Erfahrungen, die mit einem solchen Netzwerk an der RWTH Aachen gemacht wurden.


title: Well-Definedness and Semantic Type-Checking in the Nested Relational Calculus and XQuery

abstract: Two natural decision problems regarding the XML query language XQuery are well-definedness and semantic type-checking. We study these problems in the setting of a relational fragment of XQuery. We show that well-definedness and semantic type-checking are undecidable, even in the positive-existential case. Nevertheless, for a ``pure'' variant of XQuery, in which no identification is made between an item and the singleton containing that item, the problems become decidable. We also consider the analogous problems in the setting of the nested relational calculus.


title: The Complexity of Agreement

abstract: A celebrated 1976 theorem of Aumann asserts that honest, rational Bayesian agents with common priors will never "agree to disagree": if their opinions about any topic are common knowledge, then those opinions must be equal. Economists have written numerous papers examining the assumptions behind this theorem. But two key questions went unaddressed: first, can the agents reach agreement after a conversation of reasonable length? Second, can the computations needed for that conversation be performed efficiently? This paper answers both questions in the affirmative, thereby strengthening Aumann's original conclusion. We first show that, for two agents with a common prior to agree within epsilon about the expectation of a [0,1] variable with high probability over their prior, it suffices for them to exchange order 1/epsilon^2 bits. This bound is completely independent of the number of bits n of relevant knowledge that the agents have. We then extend the bound to three or more agents; and we give an example where the economists' "standard protocol" (which consists of repeatedly announcing one's current expectation) nearly saturates the bound, while a new "attenuated protocol" does better. Finally, we give a protocol that would cause two Bayesians to agree within epsilon after exchanging order 1/epsilon^2 messages, and that can be simulated by agents with limited computational resources. By this we mean that, after examining the agents' knowledge and a transcript of their conversation, no one would be able to distinguish the agents from perfect Bayesians. The time used by the simulation procedure is exponential in 1/epsilon^6 but not in n.


title: Global Grids and Software Toolkits: A Study of Four Grid Middleware Technologies

abstract: Grid is an infrastructure that involves the integrated and collaborative use of computers, networks, databases and scientific instruments owned and managed by multiple organizations. Grid applications often involve large amounts of data and/or computing resources that require secure resource sharing across organizational boundaries. This makes Grid application management and deployment a complex undertaking. Grid middlewares provide users with seamless computing ability and uniform access to resources in the heterogeneous Grid environment. Several software toolkits and systems have been developed, most of which are results of academic research projects, all over the world. This chapter will focus on four of these middlewares--UNICORE, Globus, Legion and Gridbus. It also presents our implementation of a resource broker for UNICORE as this functionality was not supported in it. A comparison of these systems on the basis of the architecture, implementation model and several other features is included.


title: Annotating Predicate-Argument Structure for a Parallel Treebank

abstract: We report on a recently initiated project which aims at building a multi-layered parallel treebank of English and German. Particular attention is devoted to a dedicated predicate-argument layer which is used for aligning translationally equivalent sentences of the two languages. We describe both our conceptual decisions and aspects of their technical realisation. We discuss some selected problems and conclude with a few remarks on how this project relates to similar projects in the field.


title: Insertion Sort is O(n log n)

abstract: Traditional Insertion Sort runs in O(n^2) time because each insertion takes O(n) time. When people run Insertion Sort in the physical world, they leave gaps between items to accelerate insertions. Gaps help in computers as well. This paper shows that Gapped Insertion Sort has insertion times of O(log n) with high probability, yielding a total running time of O(n log n) with high probability.


title: Zero-error communication over networks

abstract: Zero-Error communication investigates communication without any error. By defining channels without probabilities, results from Elias can be used to completely characterize which channel can simulate which other channels. We introduce the ambiguity of a channel, which completely characterizes the possibility in principle of a channel to simulate any other channel. In the second part we will look at networks of players connected by channels, while some players may be corrupted. We will show how the ambiguity of a virtual channel connecting two arbitrary players can be calculated. This means that we can exactly specify what kind of zero-error communication is possible between two players in any network of players connected by channels.


title: Statistical Machine Translation by Generalized Parsing

abstract: Designers of statistical machine translation (SMT) systems have begun to employ tree-structured translation models. Systems involving tree-structured translation models tend to be complex. This article aims to reduce the conceptual complexity of such systems, in order to make them easier to design, implement, debug, use, study, understand, explain, modify, and improve. In service of this goal, the article extends the theory of semiring parsing to arrive at a novel abstract parsing algorithm with five functional parameters: a logic, a grammar, a semiring, a search strategy, and a termination condition. The article then shows that all the common algorithms that revolve around tree-structured translation models, including hierarchical alignment, inference for parameter estimation, translation, and structured evaluation, can be derived by generalizing two of these parameters -- the grammar and the logic. The article culminates with a recipe for using such generalized parsers to train, apply, and evaluate an SMT system that is driven by tree-structured translation models.


title: Predicate Abstraction with Indexed Predicates

abstract: Predicate abstraction provides a powerful tool for verifying properties of infinite-state systems using a combination of a decision procedure for a subset of first-order logic and symbolic methods originally developed for finite-state model checking. We consider models containing first-order state variables, where the system state includes mutable functions and predicates. Such a model can describe systems containing arbitrarily large memories, buffers, and arrays of identical processes. We describe a form of predicate abstraction that constructs a formula over a set of universally quantified variables to describe invariant properties of the first-order state variables. We provide a formal justification of the soundness of our approach and describe how it has been used to verify several hardware and software designs, including a directory-based cache coherence protocol.


title: The semijoin algebra and the guarded fragment

abstract: The semijoin algebra is the variant of the relational algebra obtained by replacing the join operator by the semijoin operator. We discuss some interesting connections between the semijoin algebra and the guarded fragment of first-order logic. We also provide an Ehrenfeucht-Fraisse game, characterizing the discerning power of the semijoin algebra. This game gives a method for showing that certain queries are not expressible in the semijoin algebra.


title: Autogenic Training With Natural Language Processing Modules: A Recent Tool For Certain Neuro Cognitive Studies

abstract: Learning to respond to voice-text input involves the subject's ability in understanding the phonetic and text based contents and his/her ability to communicate based on his/her experience. The neuro-cognitive facility of the subject has to support two important domains in order to make the learning process complete. In many cases, though the understanding is complete, the response is partial. This is one valid reason why we need to support the information from the subject with scalable techniques such as Natural Language Processing (NLP) for abstraction of the contents from the output. This paper explores the feasibility of using NLP modules interlaced with Neural Networks to perform the required task in autogenic training related to medical applications.


title: Search Using N-gram Technique Based Statistical Analysis for Knowledge Extraction in Case Based Reasoning Systems

abstract: Searching techniques for Case Based Reasoning systems involve extensive methods of elimination. In this paper, we look at a new method of arriving at the right solution by performing a series of transformations upon the data. These involve N-gram based comparison and deduction of the input data with the case data, using Morphemes and Phonemes as the deciding parameters. A similar technique for eliminating possible errors using a noise removal function is performed. The error tracking and elimination is performed through a statistical analysis of obtained data, where the entire data set is analyzed as sub-categories of various etymological derivatives. A probability analysis for the closest match is then performed, which yields the final expression. This final expression is referred to the Case Base. The output is redirected through an Expert System based on best possible match. The threshold for the match is customizable, and could be set by the Knowledge-Architect.


title: Improved error bounds for the erasure/list scheme: the binary and spherical cases

abstract: We derive improved bounds on the error and erasure rate for spherical codes and for binary linear codes under Forney's erasure/list decoding scheme and prove some related results.


title: Distance distribution of binary codes and the error probability of decoding

abstract: We address the problem of bounding below the probability of error under maximum likelihood decoding of a binary code with a known distance distribution used on a binary symmetric channel. An improved upper bound is given for the maximum attainable exponent of this probability (the reliability function of the channel). In particular, we prove that the ``random coding exponent'' is the true value of the channel reliability for code rate $R$ in some interval immediately below the critical rate of the channel. An analogous result is obtained for the Gaussian channel.


title: A Taxonomy and Survey of Grid Resource Planning and Reservation Systems for Grid Enabled Analysis Environment

abstract: The concept of coupling geographically distributed resources for solving large scale problems is becoming increasingly popular forming what is popularly called grid computing. Management of resources in the Grid environment becomes complex as the resources are geographically distributed, heterogeneous in nature and owned by different individuals and organizations each having their own resource management policies and different access and cost models. There have been many projects that have designed and implemented the resource management systems with a variety of architectures and services. In this paper we have presented the general requirements that a Resource Management system should satisfy. The taxonomy has also been defined based on which survey of resource management systems in different existing Grid projects has been conducted to identify the key areas where these systems lack the desired functionality.


title: Distributed Analysis and Load Balancing System for Grid Enabled Analysis on Hand-held devices using Multi-Agents Systems

abstract: Handheld devices, while growing rapidly, are inherently constrained and lack the capability of executing resource hungry applications. This paper presents the design and implementation of distributed analysis and load-balancing system for hand-held devices using multi-agents system. This system enables low resource mobile handheld devices to act as potential clients for Grid enabled applications and analysis environments. We propose a system, in which mobile agents will transport, schedule, execute and return results for heavy computational jobs submitted by handheld devices. Moreover, in this way, our system provides high throughput computing environment for hand-held devices.


title: A Grid-enabled Interface to Condor for Interactive Analysis on Handheld and Resource-limited Devices

abstract: This paper was withdrawn by the authors.


title: Resource Bounded Immunity and Simplicity

abstract: Revisiting the thirty years-old notions of resource-bounded immunity and simplicity, we investigate the structural characteristics of various immunity notions: strong immunity, almost immunity, and hyperimmunity as well as their corresponding simplicity notions. We also study limited immunity and simplicity, called k-immunity and feasible k-immunity, and their simplicity notions. Finally, we propose the k-immune hypothesis as a working hypothesis that guarantees the existence of simple sets in NP.


title: Learning for Adaptive Real-time Search

abstract: Real-time heuristic search is a popular model of acting and learning in intelligent autonomous agents. Learning real-time search agents improve their performance over time by acquiring and refining a value function guiding the application of their actions. As computing the perfect value function is typically intractable, a heuristic approximation is acquired instead. Most studies of learning in real-time search (and reinforcement learning) assume that a simple value-function-greedy policy is used to select actions. This is in contrast to practice, where high-performance is usually attained by interleaving planning and acting via a lookahead search of a non-trivial depth. In this paper, we take a step toward bridging this gap and propose a novel algorithm that (i) learns a heuristic function to be used specifically with a lookahead-based policy, (ii) selects the lookahead depth adaptively in each state, (iii) gives the user control over the trade-off between exploration and exploitation. We extensively evaluate the algorithm in the sliding tile puzzle testbed comparing it to the classical LRTA* and the more recent weighted LRTA*, bounded LRTA*, and FALCONS. Improvements of 5 to 30 folds in convergence speed are observed.


title: A Low Cost Distributed Computing Approach to Pulsar Searches at a Small College

abstract: We describe a distributed processing cluster of inexpensive Linux machines developed jointly by the Astronomy and Computer Science departments at Haverford College which has been successfully used to search a large volume of data from a recent radio pulsar survey. Analysis of radio pulsar surveys requires significant computational resources to handle the demanding data storage and processing needs. One goal of this project was to explore issues encountered when processing a large amount of pulsar survey data with limited computational resources. This cluster, which was developed and activated in only a few weeks by supervised undergraduate summer research students, used existing decommissioned computers, the campus network, and a script-based, client-oriented, self-scheduled data distribution approach to process the data. This setup provided simplicity, efficiency, and "on-the-fly" scalability at low cost. The entire 570 GB data set from the pulsar survey was processed at Haverford over the course of a ten-week summer period using this cluster. We conclude that this cluster can serve as a useful computational model in cases where data processing must be carried out on a limited budget. We have also constructed a DVD archive of the raw survey data in order to investigate the feasibility of using DVD as an inexpensive and easily accessible raw data storage format for pulsar surveys. DVD-based storage has not been widely explored in the pulsar community, but it has several advantages. The DVD archive we have constructed is reliable, portable, inexpensive, and can be easily read by any standard modern machine.


title: An algorithm for two-dimensional mesh generation based on the pinwheel tiling

abstract: We propose a new two-dimensional meshing algorithm called PINW able to generate meshes that accurately approximate the distance between any two domain points by paths composed only of cell edges. This technique is based on an extension of pinwheel tilings proposed by Radin and Conway. We prove that the algorithm produces triangles of bounded aspect ratio. This kind of mesh would be useful in cohesive interface finite element modeling when the crack propagation pathis an outcome of a simulation process.


title: Stochastic fuzzy controller

abstract: A standard approach to building a fuzzy controller based on stochastic logic uses binary random signals with an average (expected value of a random variable) in the range [0, 1]. A different approach is presented, founded on a representation of the membership functions with the probability density functions.


title: Minimum Enclosing Polytope in High Dimensions

abstract: We study the problem of covering a given set of $n$ points in a high, $d$-dimensional space by the minimum enclosing polytope of a given arbitrary shape. We present algorithms that work for a large family of shapes, provided either only translations and no rotations are allowed, or only rotation about a fixed point is allowed; that is, one is allowed to only scale and translate a given shape, or scale and rotate the shape around a fixed point. Our algorithms start with a polytope guessed to be of optimal size and iteratively moves it based on a greedy principle: simply move the current polytope directly towards any outside point till it touches the surface. For computing the minimum enclosing ball, this gives a simple greedy algorithm with running time $O(nd/\eps)$ producing a ball of radius $1+\eps$ times the optimal. This simple principle generalizes to arbitrary convex shape when only translations are allowed, requiring at most $O(1/\eps^2)$ iterations. Our algorithm implies that {\em core-sets} of size $O(1/\eps^2)$ exist not only for minimum enclosing ball but also for any convex shape with a fixed orientation. A {\em Core-Set} is a small subset of $poly(1/\eps)$ points whose minimum enclosing polytope is almost as large as that of the original points. Although we are unable to combine our techniques for translations and rotations for general shapes, for the min-cylinder problem, we give an algorithm similar to the one in \cite{HV03}, but with an improved running time of $2^{O(\frac{1}{\eps^2}\log \frac{1}{\eps})} nd$.


title: Multi-agent coordination using nearest neighbor rules: revisiting the Vicsek model

abstract: Recently, Jadbabaie, Lin, and Morse (IEEE TAC, 48(6)2003:988-1001) offered a mathematical analysis of the discrete time model of groups of mobile autonomous agents raised by Vicsek et al. in 1995. In their paper, Jadbabaie et al. showed that all agents shall move in the same heading, provided that these agents are periodically linked together. This paper sharpens this result by showing that coordination will be reached under a very weak condition that requires all agents are finally linked together. This condition is also strictly weaker than the one Jadbabaie et al. desired.


title: Solving Elliptic Finite Element Systems in Near-Linear Time with Support Preconditioners

abstract: We consider linear systems arising from the use of the finite element method for solving scalar linear elliptic problems. Our main result is that these linear systems, which are symmetric and positive semidefinite, are well approximated by symmetric diagonally dominant matrices. Our framework for defining matrix approximation is support theory. Significant graph theoretic work has already been developed in the support framework for preconditioners in the diagonally dominant case, and in particular it is known that such systems can be solved with iterative methods in nearly linear time. Thus, our approximation result implies that these graph theoretic techniques can also solve a class of finite element problems in nearly linear time. We show that the support number bounds, which control the number of iterations in the preconditioned iterative solver, depend on mesh quality measures but not on the problem size or shape of the domain.