title: Top-Down Unsupervised Image Segmentation (it sounds like oxymoron, but actually it is not)

abstract: Pattern recognition is generally assumed as an interaction of two inversely directed image-processing streams: the bottom-up information details gathering and localization (segmentation) stream, and the top-down information features aggregation, association and interpretation (recognition) stream. Inspired by recent evidence from biological vision research and by the insights of Kolmogorov Complexity theory, we propose a new, just top-down evolving, procedure of initial image segmentation. We claim that traditional top-down cognitive reasoning, which is supposed to guide the segmentation process to its final result, is not at all a part of the image information content evaluation. And that initial image segmentation is certainly an unsupervised process. We present some illustrative examples, which support our claims.


title: Local and Global Analysis: Complementary Activities for Increasing the Effectiveness of Requirements Verification and Validation

abstract: This paper presents a unique approach to connecting requirements engineering (RE) activities into a process framework that can be employed to obtain quality requirements with reduced expenditures of effort and cost. We propose a two-phase model that is novel in that it introduces the concept of verification and validation (V&V) early in the requirements life cycle. In the first phase, we perform V&V immediately following the elicitation of requirements for each individually distinct system function. Because the first phase focuses on capturing smaller sets of related requirements iteratively, each corresponding V&V activity is better focused for detecting and correcting errors in each requirement set. In the second phase, a complementary verification activity is initiated; the corresponding focus is on the quality of linkages between requirements sets rather than on the requirements within the sets. Consequently, this approach reduces the effort in verification and enhances the focus on the verification task. Our approach, unlike other models, has a minimal time delay between the elicitation of requirements and the execution of the V&V activities. Because of this short time gap, the stakeholders have a clearer recollection of the requirements, their context and rationale; this enhances the stakeholder feedback. Furthermore, our model includes activities that closely align with the effective RE processes employed in the software industry. Thus, our approach facilitates a better understanding of the flow of requirements, and provides guidance for the implementation of the RE process.


title: An Objectives-Driven Process for Selecting Methods to Support Requirements Engineering Activities

abstract: This paper presents a framework that guides the requirements engineer in the implementation and execution of an effective requirements generation process. We achieve this goal by providing a well-defined requirements engineering model and a criteria based process for optimizing method selection for attendant activities. Our model, unlike other models, addresses the complete requirements generation process and consists of activities defined at more adequate levels of abstraction. Additionally, activity objectives are identified and explicitly stated - not implied as in the current models. Activity objectives are crucial as they drive the selection of methods for each activity. Our model also incorporates a unique approach to verification and validation that enhances quality and reduces the cost of generating requirements. To assist in the selection of methods, we have mapped commonly used methods to activities based on their objectives. In addition, we have identified method selection criteria and prescribed a reduced set of methods that optimize these criteria for each activity defined by our requirements generation process. Thus, the defined approach assists in the task of selecting methods by using selection criteria to reduce a large collection of potential methods to a smaller, manageable set. The model and the set of methods, taken together, provide the much needed guidance for the effective implementation and execution of the requirements generation process.


title: Effective Requirements Generation: Synchronizing Early Verification & Validation, Methods and Method Selection Criteria

abstract: This paper presents an approach for the implementation and execution of an effective requirements generation process. We achieve this goal by providing a well-defined requirements engineering model that includes verification and validation (V&V), and analysis. In addition, we identify focused activity objectives and map popular methods to lower-level activities, and define a criterion based process for optimizing method selection for attendant activities. Our model, unlike other models, addresses the complete requirements generation process and consists of activities defined at more adequate levels of abstraction. Furthermore, our model also incorporates a unique approach to V&V that enhances quality and reduces the cost of generating requirements. Additionally, activity objectives are identified and explicitly stated - not implied as in the current models. To assist in the selection of an appropriate set of methods, we have mapped commonly used methods to activities based on their objectives. Finally, we have identified method selection criteria and prescribed a reduced set of methods that optimize these criteria for each activity in our model. Thus, our approach assists in the task of selecting methods by using selection criteria to reduce a large collection of potential methods to a smaller, manageable set. The model, clear mapping of methods to activity objectives, and the criteria based process, taken together, provide the much needed guidance for the effective implementation and execution of the requirements generation process.


title: High efficiency and low absorption Fresnel compound zone plates for hard X-ray focusing

abstract: Circular and linear zone plates have been fabricated on the surface of silicon crystals for the energy of 8 keV by electron beam lithography and deep ion plasma etching methods. Various variants of compound zone plates with first, second, third diffraction orders have been made. The zone relief height is about 10 mkm, the outermost zone width of the zone plate is 0.4 mkm. The experimental testing of the zone plates has been conducted on SPring-8 and ESRF synchrotron radiation sources. A focused spot size and diffraction efficiency measured by knife-edge scanning are accordingly 0.5 mkm and 39% for the first order circular zone plate.


title: A New Non-Iterative Decoding Algorithm for the Erasure Channel : Comparisons with Enhanced Iterative Methods

abstract: This paper investigates decoding of binary linear block codes over the binary erasure channel (BEC). Of the current iterative decoding algorithms on this channel, we review the Recovery Algorithm and the Guess Algorithm. We then present a Multi-Guess Algorithm extended from the Guess Algorithm and a new algorithm -- the In-place Algorithm. The Multi-Guess Algorithm can push the limit to break the stopping sets. However, the performance of the Guess and the Multi-Guess Algorithm depend on the parity-check matrix of the code. Simulations show that we can decrease the frame error rate by several orders of magnitude using the Guess and the Multi-Guess Algorithms when the parity-check matrix of the code is sparse. The In-place Algorithm can obtain better performance even if the parity check matrix is dense. We consider the application of these algorithms in the implementation of multicast and broadcast techniques on the Internet. Using these algorithms, a user does not have to wait until the entire transmission has been received.


title: Toward alternative metrics of journal impact: A comparison of download and citation data

abstract: We generated networks of journal relationships from citation and download data, and determined journal impact rankings from these networks using a set of social network centrality metrics. The resulting journal impact rankings were compared to the ISI IF. Results indicate that, although social network metrics and ISI IF rankings deviate moderately for citation-based journal networks, they differ considerably for journal networks derived from download data. We believe the results represent a unique aspect of general journal impact that is not captured by the ISI IF. These results furthermore raise questions regarding the validity of the ISI IF as the sole assessment of journal impact, and suggest the possibility of devising impact metrics based on usage information in general.


title: Approximation of dynamical systems using S-systems theory : application to biological systems

abstract: In this paper we propose a new symbolic-numeric algorithm to find positive equilibria of a n-dimensional dynamical system. This algorithm implies a symbolic manipulation of ODE in order to give a local approximation of differential equations with power-law dynamics (S-systems). A numerical calculus is then needed to converge towards an equilibrium, giving at the same time a S-system approximating the initial system around this equilibrium. This algorithm is applied to a real biological example in 14 dimensions which is a subsystem of a metabolic pathway in Arabidopsis Thaliana.


title: Minimal chordal sense of direction and circulant graphs

abstract: A sense of direction is an edge labeling on graphs that follows a globally consistent scheme and is known to considerably reduce the complexity of several distributed problems. In this paper, we study a particular instance of sense of direction, called a chordal sense of direction (CSD). In special, we identify the class of k-regular graphs that admit a CSD with exactly k labels (a minimal CSD). We prove that connected graphs in this class are Hamiltonian and that the class is equivalent to that of circulant graphs, presenting an efficient (polynomial-time) way of recognizing it when the graphs' degree k is fixed.


title: Optimized network structure and routing metric in wireless multihop ad hoc communication

abstract: Inspired by the Statistical Physics of complex networks, wireless multihop ad hoc communication networks are considered in abstracted form. Since such engineered networks are able to modify their structure via topology control, we search for optimized network structures, which maximize the end-to-end throughput performance. A modified version of betweenness centrality is introduced and shown to be very relevant for the respective modeling. The calculated optimized network structures lead to a significant increase of the end-to-end throughput. The discussion of the resulting structural properties reveals that it will be almost impossible to construct these optimized topologies in a technologically efficient distributive manner. However, the modified betweenness centrality also allows to propose a new routing metric for the end-to-end communication traffic. This approach leads to an even larger increase of throughput capacity and is easily implementable in a technologically relevant manner.


title: Shuffling a Stacked Deck: The Case for Partially Randomized Ranking of Search Engine Results

abstract: In-degree, PageRank, number of visits and other measures of Web page popularity significantly influence the ranking of search results by modern search engines. The assumption is that popularity is closely correlated with quality, a more elusive concept that is difficult to measure directly. Unfortunately, the correlation between popularity and quality is very weak for newly-created pages that have yet to receive many visits and/or in-links. Worse, since discovery of new content is largely done by querying search engines, and because users usually focus their attention on the top few results, newly-created but high-quality pages are effectively ``shut out,'' and it can take a very long time before they become popular. We propose a simple and elegant solution to this problem: the introduction of a controlled amount of randomness into search result ranking methods. Doing so offers new pages a chance to prove their worth, although clearly using too much randomness will degrade result quality and annul any benefits achieved. Hence there is a tradeoff between exploration to estimate the quality of new pages and exploitation of pages already known to be of high quality. We study this tradeoff both analytically and via simulation, in the context of an economic objective function based on aggregate result quality amortized over time. We show that a modest amount of randomness leads to improved search results.


title: First-order Complete and Computationally Complete Query Languages for Spatio-Temporal Databases

abstract: We address a fundamental question concerning spatio-temporal database systems: ``What are exactly spatio-temporal queries?'' We define spatio-temporal queries to be computable mappings that are also generic, meaning that the result of a query may only depend to a limited extent on the actual internal representation of the spatio-temporal data. Genericity is defined as invariance under groups of geometric transformations that preserve certain characteristics of spatio-temporal data (e.g., collinearity, distance, velocity, acceleration, ...). These groups depend on the notions that are relevant in particular spatio-temporal database applications. These transformations also have the distinctive property that they respect the monotone and unidirectional nature of time. We investigate different genericity classes with respect to the constraint database model for spatio-temporal databases and we identify sound and complete languages for the first-order and the computable queries in these genericity classes. We distinguish between genericity determined by time-invariant transformations, genericity notions concerning physical quantities and genericity determined by time-dependent transformations.


title: Pr\'{e}diction de Performances pour les Communications Collectives

abstract: Des travaux r\'{e}cents visent l'optimisation des op\'{e}rations de communication collective dans les environnements de type grille de calcul. La solution la plus r\'{e}pandue est la s\'{e}paration des communications internes et externes \`{a} chaque grappe, mais cela n'exclut pas le d\'{e}coupage des communications en plusieurs couches, pratique efficace d\'{e}montr\'{e}e par Karonis et al. [10]. Dans les deux cas, la pr\'{e}diction des performances est un facteur essentiel, soit pour le r\'{e}glage fin des param\`{e}tres de communication, soit pour le calcul de la distribution et de la hi\'{e}rarchie des communications. Pour cela, il est tr\`{e}s important d'avoir des mod\`{e}les pr\'{e}cis des communications collectives, lesquels seront utilis\'{e}s pour pr\'{e}dire ces performances. Cet article d\'{e}crit notre exp\'{e}rience sur la mod\'{e}lisation des op\'{e}rations de communication collective. Nous pr\'{e}sentons des mod\`{e}les de communication pour diff\'{e}rents patrons de communication collective comme un vers plusieurs, un vers plusieurs personnalis\'{e} et plusieurs vers plusieurs. Pour \'{e}valuer la pr\'{e}cision des mod\`{e}les, nous comparons les pr\'{e}dictions obtenues avec les r\'{e}sultats des exp\'{e}rimentations effectu\'{e}es sur deux environnements r\'{e}seaux diff\'{e}rents, Fast Ethernet et Myrinet.


title: ADF95: Tool for automatic differentiation of a FORTRAN code designed for large numbers of independent variables

abstract: ADF95 is a tool to automatically calculate numerical first derivatives for any mathematical expression as a function of user defined independent variables. Accuracy of derivatives is achieved within machine precision. ADF95 may be applied to any FORTRAN 77/90/95 conforming code and requires minimal changes by the user. It provides a new derived data type that holds the value and derivatives and applies forward differencing by overloading all FORTRAN operators and intrinsic functions. An efficient indexing technique leads to a reduced memory usage and a substantially increased performance gain over other available tools with operator overloading. This gain is especially pronounced for sparse systems with large number of independent variables. A wide class of numerical simulations, e.g., those employing implicit solvers, can profit from ADF95.


title: A Systematic Aspect-Oriented Refactoring and Testing Strategy, and its Application to JHotDraw

abstract: Aspect oriented programming aims at achieving better modularization for a system's crosscutting concerns in order to improve its key quality attributes, such as evolvability and reusability. Consequently, the adoption of aspect-oriented techniques in existing (legacy) software systems is of interest to remediate software aging. The refactoring of existing systems to employ aspect-orientation will be considerably eased by a systematic approach that will ensure a safe and consistent migration. In this paper, we propose a refactoring and testing strategy that supports such an approach and consider issues of behavior conservation and (incremental) integration of the aspect-oriented solution with the original system. The strategy is applied to the JHotDraw open source project and illustrated on a group of selected concerns. Finally, we abstract from the case study and present a number of generic refactorings which contribute to an incremental aspect-oriented refactoring process and associate particular types of crosscutting concerns to the model and features of the employed aspect language. The contributions of this paper are both in the area of supporting migration towards aspect-oriented solutions and supporting the development of aspect languages that are better suited for such migrations.


title: File-based storage of Digital Objects and constituent datastreams: XMLtapes and Internet Archive ARC files

abstract: This paper introduces the write-once/read-many XMLtape/ARC storage approach for Digital Objects and their constituent datastreams. The approach combines two interconnected file-based storage mechanisms that are made accessible in a protocol-based manner. First, XML-based representations of multiple Digital Objects are concatenated into a single file named an XMLtape. An XMLtape is a valid XML file; its format definition is independent of the choice of the XML-based complex object format by which Digital Objects are represented. The creation of indexes for both the identifier and the creation datetime of the XML-based representation of the Digital Objects facilitates OAI-PMH-based access to Digital Objects stored in an XMLtape. Second, ARC files, as introduced by the Internet Archive, are used to contain the constituent datastreams of the Digital Objects in a concatenated manner. An index for the identifier of the datastream facilitates OpenURL-based access to an ARC file. The interconnection between XMLtapes and ARC files is provided by conveying the identifiers of ARC files associated with an XMLtape as administrative information in the XMLtape, and by including OpenURL references to constituent datastreams of a Digital Object in the XML-based representation of that Digital Object.


title: A Fast Combined Decimal Adder/Subtractor

abstract: This paper has been withdrawn.


title: Probabilistic Algorithmic Knowledge

abstract: The framework of algorithmic knowledge assumes that agents use deterministic knowledge algorithms to compute the facts they explicitly know. We extend the framework to allow for randomized knowledge algorithms. We then characterize the information provided by a randomized knowledge algorithm when its answers have some probability of being incorrect. We formalize this information in terms of evidence; a randomized knowledge algorithm returning ``Yes'' to a query about a fact \phi provides evidence for \phi being true. Finally, we discuss the extent to which this evidence can be used as a basis for decisions.


title: Duality Bounds on the Cut-Off Rate with Applications to Ricean Fading

abstract: We propose a technique to derive upper bounds on Gallager's cost-constrained random coding exponent function. Applying this technique to the non-coherent peak-power or average-power limited discrete time memoryless Ricean fading channel, we obtain the high signal-to-noise ratio (SNR) expansion of this channel's cut-off rate. At high SNR the gap between channel capacity and the cut-off rate approaches a finite limit. This limit is approximately 0.26 nats per channel-use for zero specular component (Rayleigh) fading and approaches 0.39 nats per channel-use for very large specular components. We also compute the asymptotic cut-off rate of a Rayleigh fading channel when the receiver has access to some partial side information concerning the fading. It is demonstrated that the cut-off rate does not utilize the side information as efficiently as capacity, and that the high SNR gap between the two increases to infinity as the imperfect side information becomes more and more precise.


title: Earlier Web Usage Statistics as Predictors of Later Citation Impact

abstract: The use of citation counts to assess the impact of research articles is well established. However, the citation impact of an article can only be measured several years after it has been published. As research articles are increasingly accessed through the Web, the number of times an article is downloaded can be instantly recorded and counted. One would expect the number of times an article is read to be related both to the number of times it is cited and to how old the article is. This paper analyses how short-term Web usage impact predicts medium-term citation impact. The physics e-print archive (arXiv.org) is used to test this.


title: Fast-Forward on the Green Road to Open Access: The Case Against Mixing Up Green and Gold

abstract: This article is a critique of: "The 'Green' and 'Gold' Roads to Open Access: The Case for Mixing and Matching" by Jean-Claude Guedon (in Serials Review 30(4) 2004). Open Access (OA) means: free online access to all peer-reviewed journal articles. Jean-Claude Guedon argues against the efficacy of author self-archiving of peer-reviewed journal articles (the "Green" road to OA). He suggests instead that we should convert to Open Access Publishing (the "Golden" road to OA) by "mixing and matching" Green and Gold as follows: o First, self-archive dissertations (not published, peer-reviewed journal articles). o Second, identify and tag how those dissertations have been evaluated and reviewed. o Third, self-archive unrefereed preprints (not published, peer-reviewed journal articles). o Fourth, develop new mechanisms for evaluating and reviewing those unrefereed preprints, at multiple levels. The result will be OA Publishing (Gold). I argue that rather than yet another 10 years of speculation like this, what is actually needed (and imminent) is for OA self-archiving to be mandated by research funders and institutions so that the self-archiving of published, peer-reviewed journal articles (Green) can be fast-forwarded to 100% OA.


title: Theory and Practice of Transactional Method Caching

abstract: Nowadays, tiered architectures are widely accepted for constructing large scale information systems. In this context application servers often form the bottleneck for a system's efficiency. An application server exposes an object oriented interface consisting of set of methods which are accessed by potentially remote clients. The idea of method caching is to store results of read-only method invocations with respect to the application server's interface on the client side. If the client invokes the same method with the same arguments again, the corresponding result can be taken from the cache without contacting the server. It has been shown that this approach can considerably improve a real world system's efficiency. This paper extends the concept of method caching by addressing the case where clients wrap related method invocations in ACID transactions. Demarcating sequences of method calls in this way is supported by many important application server standards. In this context the paper presents an architecture, a theory and an efficient protocol for maintaining full transactional consistency and in particular serializability when using a method cache on the client side. In order to create a protocol for scheduling cached method results, the paper extends a classical transaction formalism. Based on this extension, a recovery protocol and an optimistic serializability protocol are derived. The latter one differs from traditional transactional cache protocols in many essential ways. An efficiency experiment validates the approach: Using the cache a system's performance and scalability are considerably improved.


title: The Weighted Maximum-Mean Subtree and Other Bicriterion Subtree Problems

abstract: We consider problems in which we are given a rooted tree as input, and must find a subtree with the same root, optimizing some objective function of the nodes in the subtree. When this function is the sum of constant node weights, the problem is trivially solved in linear time. When the objective is the sum of weights that are linear functions of a parameter, we show how to list all optima for all possible parameter values in O(n log n) time; this parametric optimization problem can be used to solve many bicriterion optimizations problems, in which each node has two values xi and yi associated with it, and the objective function is a bivariate function f(SUM(xi),SUM(yi)) of the sums of these two values. A special case, when f is the ratio of the two sums, is the Weighted Maximum-Mean Subtree Problem, or equivalently the Fractional Prize-Collecting Steiner Tree Problem on Trees; for this special case, we provide a linear time algorithm for this problem when all weights are positive, improving a previous O(n log n) solution, and prove that the problem is NP-complete when negative weights are allowed.


title: Fine-Grained Word Sense Disambiguation Based on Parallel Corpora, Word Alignment, Word Clustering and Aligned Wordnets

abstract: The paper presents a method for word sense disambiguation based on parallel corpora. The method exploits recent advances in word alignment and word clustering based on automatic extraction of translation equivalents and being supported by available aligned wordnets for the languages in the corpus. The wordnets are aligned to the Princeton Wordnet, according to the principles established by EuroWordNet. The evaluation of the WSD system, implementing the method described herein showed very encouraging results. The same system used in a validation mode, can be used to check and spot alignment errors in multilingually aligned wordnets as BalkaNet and EuroWordNet.


title: A Taxonomy of Workflow Management Systems for Grid Computing

abstract: With the advent of Grid and application technologies, scientists and engineers are building more and more complex applications to manage and process large data sets, and execute scientific experiments on distributed resources. Such application scenarios require means for composing and executing complex workflows. Therefore, many efforts have been made towards the development of workflow management systems for Grid computing. In this paper, we propose a taxonomy that characterizes and classifies various approaches for building and executing workflows on Grids. We also survey several representative Grid workflow systems developed by various projects world-wide to demonstrate the comprehensiveness of the taxonomy. The taxonomy not only highlights the design and engineering similarities and differences of state-of-the-art in Grid workflow systems, but also identifies the areas that need further research.


title: On Generalized Computable Universal Priors and their Convergence

abstract: Solomonoff unified Occam's razor and Epicurus' principle of multiple explanations to one elegant, formal, universal theory of inductive inference, which initiated the field of algorithmic information theory. His central result is that the posterior of the universal semimeasure M converges rapidly to the true sequence generating posterior mu, if the latter is computable. Hence, M is eligible as a universal predictor in case of unknown mu. The first part of the paper investigates the existence and convergence of computable universal (semi)measures for a hierarchy of computability classes: recursive, estimable, enumerable, and approximable. For instance, M is known to be enumerable, but not estimable, and to dominate all enumerable semimeasures. We present proofs for discrete and continuous semimeasures. The second part investigates more closely the types of convergence, possibly implied by universality: in difference and in ratio, with probability 1, in mean sum, and for Martin-Loef random sequences. We introduce a generalized concept of randomness for individual sequences and use it to exhibit difficulties regarding these issues. In particular, we show that convergence fails (holds) on generalized-random sequences in gappy (dense) Bernoulli classes.


title: Authentication with Distortion Criteria

abstract: In a variety of applications, there is a need to authenticate content that has experienced legitimate editing in addition to potential tampering attacks. We develop one formulation of this problem based on a strict notion of security, and characterize and interpret the associated information-theoretic performance limits. The results can be viewed as a natural generalization of classical approaches to traditional authentication. Additional insights into the structure of such systems and their behavior are obtained by further specializing the results to Bernoulli and Gaussian cases. The associated systems are shown to be substantially better in terms of performance and/or security than commonly advocated approaches based on data hiding and digital watermarking. Finally, the formulation is extended to obtain efficient layered authentication system constructions.


title: Stabilization of Cooperative Information Agents in Unpredictable Environment: A Logic Programming Approach

abstract: An information agent is viewed as a deductive database consisting of 3 parts: an observation database containing the facts the agent has observed or sensed from its surrounding environment, an input database containing the information the agent has obtained from other agents, and an intensional database which is a set of rules for computing derived information from the information stored in the observation and input databases. Stabilization of a system of information agents represents a capability of the agents to eventually get correct information about their surrounding despite unpredictable environment changes and the incapability of many agents to sense such changes causing them to have temporary incorrect information. We argue that the stabilization of a system of cooperative information agents could be understood as the convergence of the behavior of the whole system toward the behavior of a "superagent", who has the sensing and computing capabilities of all agents combined. We show that unfortunately, stabilization is not guaranteed in general, even if the agents are fully cooperative and do not hide any information from each other. We give sufficient conditions for stabilization and discuss the consequences of our results.


title: The Effect of Use and Access on Citations

abstract: It has been shown (S. Lawrence, 2001, Nature, 411, 521) that journal articles which have been posted without charge on the internet are more heavily cited than those which have not been. Using data from the NASA Astrophysics Data System (ads.harvard.edu) and from the ArXiv e-print archive at Cornell University (arXiv.org) we examine the causes of this effect.


title: A Suffix Tree Approach to Email Filtering

abstract: We present an approach to email filtering based on the suffix tree data structure. A method for the scoring of emails using the suffix tree is developed and a number of scoring and score normalisation functions are tested. Our results show that the character level representation of emails and classes facilitated by the suffix tree can significantly improve classification accuracy when compared with the currently popular methods, such as naive Bayes. We believe the method can be extended to the classification of documents in other domains.


title: On the Scalability of Cooperative Time Synchronization in Pulse-Connected Networks

abstract: The problem of time synchronization in dense wireless networks is considered. Well established synchronization techniques suffer from an inherent scalability problem in that synchronization errors grow with an increasing number of hops across the network. In this work, a model for communication in wireless networks is first developed, and then the model is used to define a new time synchronization mechanism. A salient feature of the proposed method is that, in the regime of asymptotically dense networks, it can average out all random errors and maintain global synchronization in the sense that all nodes in the multi-hop network can see identical timing signals. This is irrespective of the distance separating any two nodes.


title: Complexity and Approximation of Fixing Numerical Attributes in Databases Under Integrity Constraints

abstract: Consistent query answering is the problem of computing the answers from a database that are consistent with respect to certain integrity constraints that the database as a whole may fail to satisfy. Those answers are characterized as those that are invariant under minimal forms of restoring the consistency of the database. In this context, we study the problem of repairing databases by fixing integer numerical values at the attribute level with respect to denial and aggregation constraints. We introduce a quantitative definition of database fix, and investigate the complexity of several decision and optimization problems, including DFP, i.e. the existence of fixes within a given distance from the original instance, and CQA, i.e. deciding consistency of answers to aggregate conjunctive queries under different semantics. We provide sharp complexity bounds, identify relevant tractable cases; and introduce approximation algorithms for some of those that are intractable. More specifically, we obtain results like undecidability of existence of fixes for aggregation constraints; MAXSNP-hardness of DFP, but a good approximation algorithm for a relevant special case; and intractability but good approximation for CQA for aggregate queries for one database atom denials (plus built-ins).


title: An Introduction to the Summarization of Evolving Events: Linear and Non-linear Evolution

abstract: This paper examines the summarization of events that evolve through time. It discusses different types of evolution taking into account the time in which the incidents of an event are happening and the different sources reporting on the specific event. It proposes an approach for multi-document summarization which employs ``messages'' for representing the incidents of an event and cross-document relations that hold between messages according to certain conditions. The paper also outlines the current version of the summarization system we are implementing to realize this approach.


title: Comment on "Some non-conventional ideas about algorithmic complexity"

abstract: We comment on a recent paper by D'Abramo [Chaos, Solitons & Fractals, 25 (2005) 29], focusing on the author's statement that an algorithm can produce a list of strings containing at least one string whose algorithmic complexity is greater than that of the entire list. We show that this statement, although perplexing, is not as paradoxical as it seems when the definition of algorithmic complexity is applied correctly.


title: The egalitarian sharing rule in provision of public projects

abstract: In this note we consider a society that partitions itself into disjoint jurisdictions, each choosing a location of its public project and a taxation scheme to finance it. The set of public project is multi-dimensional, and their costs could vary from jurisdiction to jurisdiction. We impose two principles, egalitarianism, that requires the equalization of the total cost for all agents in the same jurisdiction, and efficiency, that implies the minimization of the aggregate total cost within jurisdiction. We show that these two principles always yield a core-stable partition but a Nash stable partition may fail to exist.


title: Timed Analysis of Security Protocols

abstract: We propose a method for engineering security protocols that are aware of timing aspects. We study a simplified version of the well-known Needham Schroeder protocol and the complete Yahalom protocol, where timing information allows the study of different attack scenarios. We model check the protocols using UPPAAL. Further, a taxonomy is obtained by studying and categorising protocols from the well known Clark Jacob library and the Security Protocol Open Repository (SPORE) library. Finally, we present some new challenges and threats that arise when considering time in the analysis, by providing a novel protocol that uses time challenges and exposing a timing attack over an implementation of an existing security protocol.


title: Mining Top-k Approximate Frequent Patterns

abstract: Frequent pattern (itemset) mining in transactional databases is one of the most well-studied problems in data mining. One obstacle that limits the practical usage of frequent pattern mining is the extremely large number of patterns generated. Such a large size of the output collection makes it difficult for users to understand and use in practice. Even restricting the output to the border of the frequent itemset collection does not help much in alleviating the problem. In this paper we address the issue of overwhelmingly large output size by introducing and studying the following problem: mining top-k approximate frequent patterns. The union of the power sets of these k sets should satisfy the following conditions: (1) including itemsets with larger support as many as possible and (2) including itemsets with smaller support as less as possible. An integrated objective function is designed to combine these two objectives. Consequently, we derive the upper bounds on objective function and present an approximate branch-and-bound method for finding the feasible solution. We give empirical evidence showing that our formulation and approximation methods work well in practice.


title: On a Kronecker products sum distance bounds

abstract: A binary linear error correcting codes represented by two code families Kronecker products sum are considered. The dimension and distance of new code is investigated. Upper and lower bounds of distance are obtained. Some examples are given. It is shown that some classic constructions are the private cases of considered one. The subclass of codes with equal lower and upper distance bounds is allocated.


title: Notes for Miscellaneous Lectures

abstract: Here I share a few notes I used in various course lectures, talks, etc. Some may be just calculations that in the textbooks are more complicated, scattered, or less specific; others may be simple observations I found useful or curious.


title: Uplink Throughput in a Single-Macrocell/Single-Microcell CDMA System, with Application to Data Access Points

abstract: This paper studies a two-tier CDMA system in which the microcell base is converted into a data access point (DAP), i.e., a limited-range base station that provides high-speed access to one user at a time. The microcell (or DAP) user operates on the same frequency as the macrocell users and has the same chip rate. However, it adapts its spreading factor, and thus its data rate, in accordance with interference conditions. By contrast, the macrocell serves multiple simultaneous data users, each with the same fixed rate. The achieveable throughput for individual microcell users is examined and a simple, accurate approximation for its probability distribution is presented. Computations for average throughputs, both per-user and total, are also presented. The numerical results highlight the impact of a desensitivity parameter used in the base-selection process.


title: Soft Handoff and Uplink Capacity in a Two-Tier CDMA System

abstract: This paper examines the effect of soft handoff on the uplink user capacity of a CDMA system consisting of a single macrocell in which a single hotspot microcell is embedded. The users of these two base stations operate over the same frequency band. In the soft handoff scenario studied here, both macrocell and microcell base stations serve each system user and the two received copies of a desired user's signal are summed using maximal ratio combining. Exact and approximate analytical methods are developed to compute uplink user capacity. Simulation results demonstrate a 20% increase in user capacity compared to hard handoff. In addition, simple, approximate methods are presented for estimating soft handoff capacity and are shown to be quite accurate.


title: Uplink User Capacity in a CDMA System with Hotspot Microcells: Effects of Finite Transmit Power and Dispersion

abstract: This paper examines the uplink user capacity in a two-tier code division multiple access (CDMA) system with hotspot microcells when user terminal power is limited and the wireless channel is finitely-dispersive. A finitely-dispersive channel causes variable fading of the signal power at the output of the RAKE receiver. First, a two-cell system composed of one macrocell and one embedded microcell is studied and analytical methods are developed to estimate the user capacity as a function of a dimensionless parameter that depends on the transmit power constraint and cell radius. Next, novel analytical methods are developed to study the effect of variable fading, both with and without transmit power constraints. Finally, the analytical methods are extended to estimate uplink user capacity for multicell CDMA systems, composed of multiple macrocells and multiple embedded microcells. In all cases, the analysis-based estimates are compared with and confirmed by simulation results.


title: Complexity Issues in Finding Succinct Solutions of PSPACE-Complete Problems

abstract: We study the problem of deciding whether some PSPACE-complete problems have models of bounded size. Contrary to problems in NP, models of PSPACE-complete problems may be exponentially large. However, such models may take polynomial space in a succinct representation. For example, the models of a QBF are explicitely represented by and-or trees (which are always of exponential size) but can be succinctely represented by circuits (which can be polynomial or exponential). We investigate the complexity of deciding the existence of such succinct models when a bound on size is given.


title: Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively

abstract: To test incomplete search algorithms for constraint satisfaction problems such as 3-SAT, we need a source of hard, but satisfiable, benchmark instances. A simple way to do this is to choose a random truth assignment A, and then choose clauses randomly from among those satisfied by A. However, this method tends to produce easy problems, since the majority of literals point toward the ``hidden'' assignment A. Last year, Achlioptas, Jia and Moore proposed a problem generator that cancels this effect by hiding both A and its complement. While the resulting formulas appear to be just as hard for DPLL algorithms as random 3-SAT formulas with no hidden assignment, they can be solved by WalkSAT in only polynomial time. Here we propose a new method to cancel the attraction to A, by choosing a clause with t > 0 literals satisfied by A with probability proportional to q^t for some q < 1. By varying q, we can generate formulas whose variables have no bias, i.e., which are equally likely to be true or false; we can even cause the formula to ``deceptively'' point away from A. We present theoretical and experimental results suggesting that these formulas are exponentially hard both for DPLL algorithms and for incomplete algorithms such as WalkSAT.


title: Contextual Constraint Modeling in Grid Application Workflows

abstract: This paper introduces a new mechanism for specifying constraints in distributed workflows. By introducing constraints in a contextual form, it is shown how different people and groups within collaborative communities can cooperatively constrain workflows. A comparison with existing state-of-the-art workflow systems is made. These ideas are explored in practice with an illustrative example from High Energy Physics.


title: Hiding Satisfying Assignments: Two are Better than One

abstract: The evaluation of incomplete satisfiability solvers depends critically on the availability of hard satisfiable instances. A plausible source of such instances consists of random k-SAT formulas whose clauses are chosen uniformly from among all clauses satisfying some randomly chosen truth assignment A. Unfortunately, instances generated in this manner tend to be relatively easy and can be solved efficiently by practical heuristics. Roughly speaking, as the formula's density increases, for a number of different algorithms, A acts as a stronger and stronger attractor. Motivated by recent results on the geometry of the space of satisfying truth assignments of random k-SAT and NAE-k-SAT formulas, we introduce a simple twist on this basic model, which appears to dramatically increase its hardness. Namely, in addition to forbidding the clauses violated by the hidden assignment A, we also forbid the clauses violated by its complement, so that both A and complement of A are satisfying. It appears that under this "symmetrization'' the effects of the two attractors largely cancel out, making it much harder for algorithms to find any truth assignment. We give theoretical and experimental evidence supporting this assertion.

categories: cs.AI cond-mat.dis-nn cond-mat.stat-mech cs.CC


title: On Multiflows in Random Unit-Disk Graphs, and the Capacity of Some Wireless Networks

abstract: We consider the capacity problem for wireless networks. Networks are modeled as random unit-disk graphs, and the capacity problem is formulated as one of finding the maximum value of a multicommodity flow. In this paper, we develop a proof technique based on which we are able to obtain a tight characterization of the solution to the linear program associated with the multiflow problem, to within constants independent of network size. We also use this proof method to analyze network capacity for a variety of transmitter/receiver architectures, for which we obtain some conclusive results. These results contain as a special case (and strengthen) those of Gupta and Kumar for random networks, for which a new derivation is provided using only elementary counting and discrete probability tools.


title: Is entanglement necessary to have unconditional security in quantum bit commitment ?

abstract: A simple un-entanglement based quantum bit commitment scheme is presented. Although commitment is unconditionally secure but concealment is not.


title: Enforcing and Defying Associativity, Commutativity, Totality, and Strong Noninvertibility for One-Way Functions in Complexity Theory

abstract: Rabi and Sherman [RS97,RS93] proved that the hardness of factoring is a sufficient condition for there to exist one-way functions (i.e., p-time computable, honest, p-time noninvertible functions; this paper is in the worst-case model, not the average-case model) that are total, commutative, and associative but not strongly noninvertible. In this paper we improve the sufficient condition to ``P does not equal NP.'' More generally, in this paper we completely characterize which types of one-way functions stand or fall together with (plain) one-way functions--equivalently, stand or fall together with P not equaling NP. We look at the four attributes used in Rabi and Sherman's seminal work on algebraic properties of one-way functions (see [RS97,RS93]) and subsequent papers--strongness (of noninvertibility), totality, commutativity, and associativity--and for each attribute, we allow it to be required to hold, required to fail, or ``don't care.'' In this categorization there are 3^4 = 81 potential types of one-way functions. We prove that each of these 81 feature-laden types stand or fall together with the existence of (plain) one-way functions.


title: Systematic Method for Path-Complete White Box Testing

abstract: A systematic, language-independent method of finding a minimal set of paths covering the code of a sequential program is proposed for application in White Box testing. Execution of all paths from the set ensures also statement coverage. Execution fault marks problematic areas of the code. The method starts from a UML activity diagram of a program. The diagram is transformed into a directed graph: graph's nodes substitute decision and action points; graph's directed edges substitute action arrows. The number of independent paths equals easy-to-compute cyclomatic complexity of the graph. Association of a vector to each path creates a path vector space. Independence of the paths is equivalent to linear independence of the vectors. It is sufficient to test any base of the path space to complete the procedure. An effective algorithm for choosing the base paths is presented.


title: Construction of Small Worlds in the Physical Topology of Wireless Networks

abstract: The concept of small worlds is introduced into the physical topology of wireless networks in this work. A. Helmy provided two con- struction schemes of small worlds for the wireless networks, link rewiring and link addition, but he mainly focused on the virtual topology. Based on the broadcasting nature of the radio transmission, we propose a con- struction scheme of small worlds for the physical topology of Multiple- Input Multiple-Output (MIMO) wireless networks. Besides the topology- related topics, we also evaluate the reduction of the power required by a request.


title: Zeta-Dimension

abstract: The zeta-dimension of a set A of positive integers is the infimum s such that the sum of the reciprocals of the s-th powers of the elements of A is finite. Zeta-dimension serves as a fractal dimension on the positive integers that extends naturally usefully to discrete lattices such as the set of all integer lattice points in d-dimensional space. This paper reviews the origins of zeta-dimension (which date to the eighteenth and nineteenth centuries) and develops its basic theory, with particular attention to its relationship with algorithmic information theory. New results presented include extended connections between zeta-dimension and classical fractal dimensions, a gale characterization of zeta-dimension, and a theorem on the zeta-dimensions of pointwise sums and products of sets of positive integers.


title: A hybrid MLP-PNN architecture for fast image superresolution

abstract: Image superresolution methods process an input image sequence of a scene to obtain a still image with increased resolution. Classical approaches to this problem involve complex iterative minimization procedures, typically with high computational costs. In this paper is proposed a novel algorithm for super-resolution that enables a substantial decrease in computer load. First, a probabilistic neural network architecture is used to perform a scattered-point interpolation of the image sequence data. The network kernel function is optimally determined for this problem by a multi-layer perceptron trained on synthetic data. Network parameters dependence on sequence noise level is quantitatively analyzed. This super-sampled image is spatially filtered to correct finite pixel size effects, to yield the final high-resolution estimate. Results on a real outdoor sequence are presented, showing the quality of the proposed method.


title: Analytic Definition of Curves and Surfaces by Parabolic Blending

abstract: A procedure for interpolating between specified points of a curve or surface is described. The method guarantees slope continuity at all junctions. A surface panel divided into p x q contiguous patches is completely specified by the coordinates of (p+1) x (q+1) points. Each individual patch, however, depends parametrically on the coordinates of 16 points, allowing shape flexibility and global conformity.


title: Optimality in Goal-Dependent Analysis of Sharing

abstract: We face the problems of correctness, optimality and precision for the static analysis of logic programs, using the theory of abstract interpretation. We propose a framework with a denotational, goal-dependent semantics equipped with two unification operators for forward unification (calling a procedure) and backward unification (returning from a procedure). The latter is implemented through a matching operation. Our proposal clarifies and unifies many different frameworks and ideas on static analysis of logic programming in a single, formal setting. On the abstract side, we focus on the domain Sharing by Jacobs and Langen and provide the best correct approximation of all the primitive semantic operators, namely, projection, renaming, forward and backward unification. We show that the abstract unification operators are strictly more precise than those in the literature defined over the same abstract domain. In some cases, our operators are more precise than those developed for more complex domains involving linearity and freeness. To appear in Theory and Practice of Logic Programming (TPLP)


title: Semi-automatic vectorization of linear networks on rasterized cartographic maps

abstract: A system for semi-automatic vectorization of linear networks (roads, rivers, etc.) on rasterized cartographic maps is presented. In this system, human intervention is limited to a graphic, interactive selection of the color attributes of the information to be obtained. Using this data, the system performs a preliminary extraction of the linear network, which is subsequently completed, refined and vectorized by means of an automatic procedure. Results on maps of different sources and scales are included. ----- Se presenta un sistema semi-automatico de vectorizacion de redes de objetos lineales (carreteras, rios, etc.) en mapas cartograficos digitalizados. En este sistema, la intervencion humana queda reducida a la seleccion grafica interactiva de los atributos de color de la informacion a obtener. Con estos datos, el sistema realiza una extraccion preliminar de la red lineal, que se completa, refina y vectoriza mediante un procedimiento automatico. Se presentan resultados de la aplicacion del sistema sobre imagenes digitalizadas de mapas de distinta procedencia y escala.


title: Exact and Approximation Algorithms for DNA Tag Set Design

abstract: In this paper we propose new solution methods for designing tag sets for use in universal DNA arrays. First, we give integer linear programming formulations for two previous formalizations of the tag set design problem, and show that these formulations can be solved to optimality for instance sizes of practical interest by using general purpose optimization packages. Second, we note the benefits of periodic tags, and establish an interesting connection between the tag design problem and the problem of packing the maximum number of vertex-disjoint directed cycles in a given graph. We show that combining a simple greedy cycle packing algorithm with a previously proposed alphabetic tree search strategy yields an increase of over 40% in the number of tags compared to previous methods.


title: On the Stopping Distance and the Stopping Redundancy of Codes

abstract: It is now well known that the performance of a linear code $C$ under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for $C$. Several recent papers refer to this parameter as the \emph{stopping distance} $s$ of $C$. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for $C$ depends on the corresponding choice of a parity-check matrix. It is easy to see that $s \le d$, where $d$ is the minimum Hamming distance of $C$, and we show that it is always possible to choose a parity-check matrix for $C$ (with sufficiently many dependent rows) such that $s = d$. We thus introduce a new parameter, termed the \emph{stopping redundancy} of $C$, defined as the minimum number of rows in a parity-check matrix $H$ for $C$ such that the corresponding stopping distance $s(H)$ attains its largest possible value, namely $s(H) = d$. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 35 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes.


title:
Les repr\'{e}sentations g\'{e}n\'{e}tiques d'objets : simples analogies ou mod\`{e}les pertinents ? Le point de vue de l' "\'{e}volutique".
–––
Genetic representations of objects : simple analogies or efficient models ? The "evolutic" point of view

abstract: Depuis une trentaine d'ann\'{e}es, les ing\'{e}nieurs utilisent couramment des analogies avec l'\'{e}volution naturelle pour optimiser des dispositifs techniques. Le plus souvent, ces m\'{e}thodes "g\'{e}n\'{e}tiques" ou "\'{e}volutionnaires" sont consid\'{e}r\'{e}es uniquement du point de vue pratique, comme des m\'{e}thodes d'optimisation performantes, qu'on peut utiliser \`{a} la place d'autres m\'{e}thodes (gradients, simplexes, ...). Dans cet article, nous essayons de montrer que les sciences et les techniques, mais aussi les organisations humaines, et g\'{e}n\'{e}ralement tous les syst\`{e}mes complexes, ob\'{e}issent \`{a} des lois d'\'{e}volution dont la g\'{e}n\'{e}tique est un bon mod\`{e}le repr\'{e}sentatif, m\^{e}me si g\^{e}nes et chromosomes sont "virtuels" : ainsi loin d'\^{e}tre seulement un outil ponctuel d'aide \`{a} la synth\`{e}se de solutions technologiques, la repr\'{e}sentation g\'{e}n\'{e}tique est-elle un mod\`{e}le dynamique global de l'\'{e}volution du monde fa\c{c}onn\'{e} par l'agitation humaine.––––For thirty years, engineers commonly use analogies with natural evolution to optimize technical devices. More often that not, these "genetic" or "evolutionary" methods are only view as efficient tools, which could replace other optimization techniques (gradient methods, simplex, ...). In this paper, we try to show that sciences, techniques, human organizations, and more generally all complex systems, obey to evolution rules, whose the genetic is a good representative model, even if genes and chromosomes are "virtual". Thus, the genetic representation is not only a specific tool helping for the design of technological solutions, but also a global and dynamic model for the action of the human agitation on our world.


title: Multi-Dimensional Hash Chains and Application to Micropayment Schemes

abstract: One-way hash chains have been used in many micropayment schemes due to their simplicity and efficiency. In this paper we introduce the notion of multi-dimensional hash chains, which is a new generalization of traditional one-way hash chains. We show that this construction has storage-computational complexity of O(logN) per chain element, which is comparable with the best result reported in recent literature. Based on multi-dimensional hash chains, we then propose two cash-like micropayment schemes, which have a number of advantages in terms of efficiency and security. We also point out some possible improvements to PayWord and similar schemes by using multi-dimensional hash chains


title: Integrity Constraints in Trust Management

abstract: We introduce the use, monitoring, and enforcement of integrity constraints in trust management-style authorization systems. We consider what portions of the policy state must be monitored to detect violations of integrity constraints. Then we address the fact that not all participants in a trust management system can be trusted to assist in such monitoring, and show how many integrity constraints can be monitored in a conservative manner so that trusted participants detect and report if the system enters a policy state from which evolution in unmonitored portions of the policy could lead to a constraint violation.


title: On the Complexity of Nonrecursive XQuery and Functional Query Languages on Complex Values

abstract: This paper studies the complexity of evaluating functional query languages for complex values such as monad algebra and the recursion-free fragment of XQuery. We show that monad algebra with equality restricted to atomic values is complete for the class TA[2^{O(n)}, O(n)] of problems solvable in linear exponential time with a linear number of alternations. The monotone fragment of monad algebra with atomic value equality but without negation is complete for nondeterministic exponential time. For monad algebra with deep equality, we establish TA[2^{O(n)}, O(n)] lower and exponential-space upper bounds. Then we study a fragment of XQuery, Core XQuery, that seems to incorporate all the features of a query language on complex values that are traditionally deemed essential. A close connection between monad algebra on lists and Core XQuery (with ``child'' as the only axis) is exhibited, and it is shown that these languages are expressively equivalent up to representation issues. We show that Core XQuery is just as hard as monad algebra w.r.t. combined complexity, and that it is in TC0 if the query is assumed fixed.


title: Randomly Spread CDMA: Asymptotics via Statistical Physics

abstract: This paper studies randomly spread code-division multiple access (CDMA) and multiuser detection in the large-system limit using the replica method developed in statistical physics. Arbitrary input distributions and flat fading are considered. A generic multiuser detector in the form of the posterior mean estimator is applied before single-user decoding. The generic detector can be particularized to the matched filter, decorrelator, linear MMSE detector, the jointly or the individually optimal detector, and others. It is found that the detection output for each user, although in general asymptotically non-Gaussian conditioned on the transmitted symbol, converges as the number of users go to infinity to a deterministic function of a "hidden" Gaussian statistic independent of the interferers. Thus the multiuser channel can be decoupled: Each user experiences an equivalent single-user Gaussian channel, whose signal-to-noise ratio suffers a degradation due to the multiple-access interference. The uncoded error performance (e.g., symbol-error-rate) and the mutual information can then be fully characterized using the degradation factor, also known as the multiuser efficiency, which can be obtained by solving a pair of coupled fixed-point equations identified in this paper. Based on a general linear vector channel model, the results are also applicable to MIMO channels such as in multiantenna systems.


title: Minimum-Cost Multicast over Coded Packet Networks

abstract: We consider the problem of establishing minimum-cost multicast connections over coded packet networks, i.e. packet networks where the contents of outgoing packets are arbitrary, causal functions of the contents of received packets. We consider both wireline and wireless packet networks as well as both static multicast (where membership of the multicast group remains constant for the duration of the connection) and dynamic multicast (where membership of the multicast group changes in time, with nodes joining and leaving the group). For static multicast, we reduce the problem to a polynomial-time solvable optimization problem, and we present decentralized algorithms for solving it. These algorithms, when coupled with existing decentralized schemes for constructing network codes, yield a fully decentralized approach for achieving minimum-cost multicast. By contrast, establishing minimum-cost static multicast connections over routed packet networks is a very difficult problem even using centralized computation, except in the special cases of unicast and broadcast connections. For dynamic multicast, we reduce the problem to a dynamic programming problem and apply the theory of dynamic programming to suggest how it may be solved.


title: Data-Structure Rewriting

abstract: We tackle the problem of data-structure rewriting including pointer redirections. We propose two basic rewrite steps: (i) Local Redirection and Replacement steps the aim of which is redirecting specific pointers determined by means of a pattern, as well as adding new information to an existing data ; and (ii) Global Redirection steps which are aimed to redirect all pointers targeting a node towards another one. We define these two rewriting steps following the double pushout approach. We define first the category of graphs we consider and then define rewrite rules as pairs of graph homomorphisms of the form "L <- K ->R". Unfortunately, inverse pushouts (complement pushouts) are not unique in our setting and pushouts do not always exist. Therefore, we define rewriting steps so that a rewrite rule can always be performed once a matching is found.


title: A Practical Approach for Circuit Routing on Dynamic Reconfigurable Devices

abstract: Management of communication by on-line routing in new FPGAs with a large amount of logic resources and partial reconfigurability is a new challenging problem. A Network-on-Chip (NoC) typically uses packet routing mechanism, which has often unsafe data transfers, and network interface overhead. In this paper, circuit routing for such dynamic NoCs is investigated, and a practical 1-dimensional network with an efficient routing algorithm is proposed and implemented. Also, this concept has been extended to the 2-dimensional case. The implementation results show the low area overhead and high performance of this network.


title: Contextual equivalence for higher-order pi-calculus revisited

abstract: The higher-order pi-calculus is an extension of the pi-calculus to allow communication of abstractions of processes rather than names alone. It has been studied intensively by Sangiorgi in his thesis where a characterisation of a contextual equivalence for higher-order pi-calculus is provided using labelled transition systems and normal bisimulations. Unfortunately the proof technique used there requires a restriction of the language to only allow finite types. We revisit this calculus and offer an alternative presentation of the labelled transition system and a novel proof technique which allows us to provide a fully abstract characterisation of contextual equivalence using labelled transitions and bisimulations for higher-order pi-calculus with recursive types also.


title: A Survey of Reverse Engineering and Program Comprehension

abstract: Reverse engineering has been a standard practice in the hardware community for some time. It has only been within the last ten years that reverse engineering, or "program comprehension", has grown into the current sub-discipline of software engineering. Traditional software engineering is primarily focused on the development and design of new software. However, most programmers work on software that other people have designed and developed. Up to 50% of a software maintainers time can be spent determining the intent of source code. The growing demand to reevaluate and reimplement legacy software systems, brought on by the proliferation of clientserver and World Wide Web technologies, has underscored the need for reverse engineering tools and techniques. This paper introduces the terminology of reverse engineering and gives some of the obstacles that make reverse engineering difficult. Although reverse engineering remains heavily dependent on the human component, a number of automated tools are presented that aid the reverse engineer.


title: mod_oai: An Apache Module for Metadata Harvesting

abstract: We describe mod_oai, an Apache 2.0 module that implements the Open Archives Initiative Protocol for Metadata Harvesting (OAI-PMH). OAIPMH is the de facto standard for metadata exchange in digital libraries and allows repositories to expose their contents in a structured, application-neutral format with semantics optimized for accurate incremental harvesting. Current implementations of OAI-PMH are either separate applications that access an existing repository, or are built-in to repository software packages. mod_oai is different in that it optimizes harvesting web content by building OAI-PMH capability into the Apache server. We discuss the implications of adding harvesting capability to an Apache server and describe our initial experimental results accessing a departmental web site using both web crawling and OAIPMH harvesting techniques.


title: Improved message passing for inference in densely connected systems

abstract: An improved inference method for densely connected systems is presented. The approach is based on passing condensed messages between variables, representing macroscopic averages of microscopic messages. We extend previous work that showed promising results in cases where the solution space is contiguous to cases where fragmentation occurs. We apply the method to the signal detection problem of Code Division Multiple Access (CDMA) for demonstrating its potential. A highly efficient practical algorithm is also derived on the basis of insight gained from the analysis.


title: Consistency in Models for Distributed Learning under Communication Constraints

abstract: Motivated by sensor networks and other distributed settings, several models for distributed learning are presented. The models differ from classical works in statistical pattern recognition by allocating observations of an independent and identically distributed (i.i.d.) sampling process amongst members of a network of simple learning agents. The agents are limited in their ability to communicate to a central fusion center and thus, the amount of information available for use in classification or regression is constrained. For several basic communication models in both the binary classification and regression frameworks, we question the existence of agent decision rules and fusion rules that result in a universally consistent ensemble. The answers to this question present new issues to consider with regard to universal consistency. Insofar as these models present a useful picture of distributed scenarios, this paper addresses the issue of whether or not the guarantees provided by Stone's Theorem in centralized environments hold in distributed settings.


title: Distributed Learning in Wireless Sensor Networks

abstract: The problem of distributed or decentralized detection and estimation in applications such as wireless sensor networks has often been considered in the framework of parametric models, in which strong assumptions are made about a statistical description of nature. In certain applications, such assumptions are warranted and systems designed from these models show promise. However, in other scenarios, prior knowledge is at best vague and translating such knowledge into a statistical model is undesirable. Applications such as these pave the way for a nonparametric study of distributed detection and estimation. In this paper, we review recent work of the authors in which some elementary models for distributed learning are considered. These models are in the spirit of classical work in nonparametric statistics and are applicable to wireless sensor networks.


title: Tensor manipulation in GPL Maxima

abstract: GPL Maxima is an open-source computer algebra system based on DOE-MACSYMA. GPL Maxima included two tensor manipulation packages from DOE-MACSYMA, but these were in various states of disrepair. One of the two packages, CTENSOR, implemented component-based tensor manipulation; the other, ITENSOR, treated tensor symbols as opaque, manipulating them based on their index properties. The present paper describes the state in which these packages were found, the steps that were needed to make the packages fully functional again, and the new functionality that was implemented to make them more versatile. A third package, ATENSOR, was also implemented; fully compatible with the identically named package in the commercial version of MACSYMA, ATENSOR implements abstract tensor algebras.


title: A File System Abstraction for Sense and Respond Systems

abstract: The heterogeneity and resource constraints of sense-and-respond systems pose significant challenges to system and application development. In this paper, we present a flexible, intuitive file system abstraction for organizing and managing sense-and-respond systems based on the Plan 9 design principles. A key feature of this abstraction is the ability to support multiple views of the system via filesystem namespaces. Constructed logical views present an application-specific representation of the network, thus enabling high-level programming of the network. Concurrently, structural views of the network enable resource-efficient planning and execution of tasks. We present and motivate the design using several examples, outline research challenges and our research plan to address them, and describe the current state of implementation.


title: Statistical Modelling of Information Sharing: Community, Membership and Content

abstract: File-sharing systems, like many online and traditional information sharing communities (e.g. newsgroups, BBS, forums, interest clubs), are dynamical systems in nature. As peers get in and out of the system, the information content made available by the prevailing membership varies continually in amount as well as composition, which in turn affects all peers' join/leave decisions. As a result, the dynamics of membership and information content are strongly coupled, suggesting interesting issues about growth, sustenance and stability. In this paper, we propose to study such communities with a simple statistical model of an information sharing club. Carrying their private payloads of information goods as potential supply to the club, peers join or leave on the basis of whether the information they demand is currently available. Information goods are chunked and typed, as in a file sharing system where peers contribute different files, or a forum where messages are grouped by topics or threads. Peers' demand and supply are then characterized by statistical distributions over the type domain. This model reveals interesting critical behaviour with multiple equilibria. A sharp growth threshold is derived: the club may grow towards a sustainable equilibrium only if the value of an order parameter is above the threshold, or shrink to emptiness otherwise. The order parameter is composite and comprises the peer population size, the level of their contributed supply, the club's efficiency in information search, the spread of supply and demand over the type domain, as well as the goodness of match between them.


title: Geometric Models of Rolling-Shutter Cameras

abstract: Cameras with rolling shutters are becoming more common as low-power, low-cost CMOS sensors are being used more frequently in cameras. The rolling shutter means that not all scanlines are exposed over the same time interval. The effects of a rolling shutter are noticeable when either the camera or objects in the scene are moving and can lead to systematic biases in projection estimation. We develop a general projection equation for a rolling shutter camera and show how it is affected by different types of camera motion. In the case of fronto-parallel motion, we show how that camera can be modeled as an X-slit camera. We also develop approximate projection equations for a non-zero angular velocity about the optical axis and approximate the projection equation for a constant velocity screw motion. We demonstrate how the rolling shutter effects the projective geometry of the camera and in turn the structure-from-motion.


title: Weighted Automata in Text and Speech Processing

abstract: Finite-state automata are a very effective tool in natural language processing. However, in a variety of applications and especially in speech precessing, it is necessary to consider more general machines in which arcs are assigned weights or costs. We briefly describe some of the main theoretical and algorithmic aspects of these machines. In particular, we describe an efficient composition algorithm for weighted transducers, and give examples illustrating the value of determinization and minimization algorithms for weighted automata.


title: Obtaining Membership Functions from a Neuron Fuzzy System extended by Kohonen Network

abstract: This article presents the Neo-Fuzzy-Neuron Modified by Kohonen Network (NFN-MK), an hybrid computational model that combines fuzzy system technique and artificial neural networks. Its main task consists in the automatic generation of membership functions, in particular, triangle forms, aiming a dynamic modeling of a system. The model is tested by simulating real systems, here represented by a nonlinear mathematical function. Comparison with the results obtained by traditional neural networks, and correlated studies of neurofuzzy systems applied in system identification area, shows that the NFN-MK model has a similar performance, despite its greater simplicity.


title: Space-time databases modeling global semantic networks

abstract: This paper represents an approach to creating global knowledge systems, using new philosophy and infrastructure of global distributed semantic network (frame knowledge representation system) based on the space-time database construction. The main idea of the space-time database environment introduced in the paper is to bind a document (an information frame, a knowledge) to a special kind of entity, that we call permanent entity, -- an object without history and evolution, described by a "point" in the generalized, informational space-time (not an evolving object in the real space having history). For documents (information) it means that document content is unchangeable, and documents are absolutely persistent. This approach leads to new knowledge representation and retreival techniques. We discuss the way of applying the concept to a global distributed scientific library and scientific workspace. Some practical aspects of the work are elaborated by the open IT project at http://sourceforge.net/projects/gil/.


title: Enforcing Semantic Integrity on Untrusted Clients in Networked Virtual Environments

abstract: During the last years, large-scale simulations of realistic physical environments which support the interaction of multiple participants over the Internet have become increasingly available and economically significant, most notably in the computer gaming industry. Such systems, commonly called networked virtual environments (NVEs), are usually based on a client-server architecture where for performance reasons and bandwidth restrictions, the simulation is partially deferred to the clients. This inevitable architectural choice renders the simulation vulnerable to attacks against the semantic integrity of the simulation: malicious clients may attempt to compromise the physical and logical laws governing the simulation, or to alter the causality of events a posteriori. In this paper, we initiate the systematic study of semantic integrity in NVEs from a security point of view. We argue that naive policies to enforce semantic integrity involve intolerable network load, and are therefore not practically feasible. We present a new semantic integrity protocol based on cryptographic primitives which enables the server system to audit the local computations of the clients on demand. Our approach facilitates low network and CPU load, incurs reasonable engineering overhead, and maximally decouples the auditing process from the soft real time constraints of the simulation.


title: An Optimization Model for Outlier Detection in Categorical Data

abstract: The task of outlier detection is to find small groups of data objects that are exceptional when compared with rest large amount of data. Detection of such outliers is important for many applications such as fraud detection and customer migration. Most existing methods are designed for numeric data. They will encounter problems with real-life applications that contain categorical data. In this paper, we formally define the problem of outlier detection in categorical data as an optimization problem from a global viewpoint. Moreover, we present a local-search heuristic based algorithm for efficiently finding feasible solutions. Experimental results on real datasets and large synthetic datasets demonstrate the superiority of our model and algorithm.


title: Spines of Random Constraint Satisfaction Problems: Definition and Connection with Computational Complexity

abstract: We study the connection between the order of phase transitions in combinatorial problems and the complexity of decision algorithms for such problems. We rigorously show that, for a class of random constraint satisfaction problems, a limited connection between the two phenomena indeed exists. Specifically, we extend the definition of the spine order parameter of Bollobas et al. to random constraint satisfaction problems, rigorously showing that for such problems a discontinuity of the spine is associated with a $2^{\Omega(n)}$ resolution complexity (and thus a $2^{\Omega(n)}$ complexity of DPLL algorithms) on random instances. The two phenomena have a common underlying cause: the emergence of ``large'' (linear size) minimally unsatisfiable subformulas of a random formula at the satisfiability phase transition. We present several further results that add weight to the intuition that random constraint satisfaction problems with a sharp threshold and a continuous spine are ``qualitatively similar to random 2-SAT''. Finally, we argue that it is the spine rather than the backbone parameter whose continuity has implications for the decision complexity of combinatorial problems, and we provide experimental evidence that the two parameters can behave in a different manner.


title: Coarse and Sharp Thresholds of Boolean Constraint Satisfaction Problems

abstract: We study threshold properties of random constraint satisfaction problems under a probabilistic model due to Molloy. We give a sufficient condition for the existence of a sharp threshold that leads (for boolean constraints) to a necessary and sufficient for the existence of a sharp threshold in the case where constraint templates are applied with equal probability, solving thus an open problem of Creignou and Daude.


title: The Peculiarities of Nonstationary Formation of Inhomogeneous Structures of Charged Particles in the Electrodiffusion Processes

abstract: In this paper the distribution of charged particles is constructed under the approximation of ambipolar diffusion. The results of mathematical modelling in two-dimensional case taking into account the velocities of the system are presented.


title: Dynamic Shannon Coding

abstract: We present a new algorithm for dynamic prefix-free coding, based on Shannon coding. We give a simple analysis and prove a better upper bound on the length of the encoding produced than the corresponding bound for dynamic Huffman coding. We show how our algorithm can be modified for efficient length-restricted coding, alphabetic coding and coding with unequal letter costs.


title: Segmentation of the Homogeneity of a Signal Using a Piecewise Linear Recognition Tool

abstract: In this paper a new method of detection of homogeneous zones and singularity parts of a 1D signal is proposed. The entropy function is used to transform signal in piecewise linear one. The multiple regression permits to detect lines and project them in the Hough parameters space in order to easily recognise homogeneous zone and abrupt changes of the signal. Two application examples are analysed, the first is a classical fractal signal and the other is issued from a dynamic mechanical study.


title: Dynamic Simulation of Construction Machinery: Towards an Operator Model

abstract: In dynamic simulation of complete wheel loaders, one interesting aspect, specific for the working task, is the momentary power distribution between drive train and hydraulics, which is balanced by the operator. This paper presents the initial results to a simulation model of a human operator. Rather than letting the operator model follow a predefined path with control inputs at given points, it follows a collection of general rules that together describe the machine's working cycle in a generic way. The advantage of this is that the working task description and the operator model itself are independent of the machine's technical parameters. Complete sub-system characteristics can thus be changed without compromising the relevance and validity of the simulation. Ultimately, this can be used to assess a machine's total performance, fuel efficiency and operability already in the concept phase of the product development process.


title: General non-asymptotic and asymptotic formulas in channel resolvability and identification capacity and their application to wire-tap channel

abstract: Several non-asymptotic formulas are established in channel resolvability and identification capacity, and they are applied to wire-tap channel. By using these formulas, the $\epsilon$ capacities of the above three problems are considered in the most general setting, where no structural assumptions such as the stationary memoryless property are made on a channel. As a result, we solve an open problem proposed in Han & Verdu and Han. Moreover, we obtain lower bounds of the exponents of error probability and the wire-tapper's information in wire-tap channel.


title: Second order asymptotics in fixed-length source coding and intrinsic randomness

abstract: Second order asymptotics of fixed-length source coding and intrinsic randomness is discussed with a constant error constraint. There was a difference between optimal rates of fixed-length source coding and intrinsic randomness, which never occurred in the first order asymptotics. In addition, the relation between uniform distribution and compressed data is discussed based on this fact. These results are valid for general information sources as well as independent and identical distributions. A universal code attaining the second order optimal rate is also constructed.


title: Effects of variations of load distribution on network performance

abstract: This paper is concerned with the characterization of the relationship between topology and traffic dynamics. We use a model of network generation that allows the transition from random to scale free networks. Specifically, we consider three different topological types of network: random, scale-free with \gamma = 3, scale-free with \gamma = 2. By using a novel LRD traffic generator, we observe best performance, in terms of transmission rates and delivered packets, in the case of random networks. We show that, even if scale-free networks are characterized by shorter characteristic-path- length (the lower the exponent, the lower the path-length), they show worst performances in terms of communication. We conjecture this could be explained in terms of changes in the load distribution, defined here as the number of shortest paths going through a given vertex. In fact, that distribu- tion is characterized by (i) a decreasing mean (ii) an increas- ing standard deviation, as the networks becomes scale-free (especially scale-free networks with low exponents). The use of a degree-independent server also discriminates against a scale-free structure. As a result, since the model is un- controlled, most packets will go through the same vertices, favoring the onset of congestion.


title: Resource Bounded Unprovability of Computational Lower Bounds

abstract: This paper introduces new notions of asymptotic proofs, PT(polynomial-time)-extensions, PTM(polynomial-time Turing machine)-omega-consistency, etc. on formal theories of arithmetic including PA (Peano Arithmetic). This paper shows that P not= NP (more generally, any super-polynomial-time lower bound in PSPACE) is unprovable in a PTM-omega-consistent theory T, where T is a consistent PT-extension of PA. This result gives a unified view to the existing two major negative results on proving P not= NP, Natural Proofs and relativizable proofs, through the two manners of characterization of PTM-omega-consistency. We also show that the PTM-omega-consistency of T cannot be proven in any PTM-omega-consistent theory S, where S is a consistent PT-extension of T.


title: Monotonic and Nonmonotonic Preference Revision

abstract: We study here preference revision, considering both the monotonic case where the original preferences are preserved and the nonmonotonic case where the new preferences may override the original ones. We use a relational framework in which preferences are represented using binary relations (not necessarily finite). We identify several classes of revisions that preserve order axioms, for example the axioms of strict partial or weak orders. We consider applications of our results to preference querying in relational databases.


title: Probabilistic and Team PFIN-type Learning: General Properties

abstract: We consider the probability hierarchy for Popperian FINite learning and study the general properties of this hierarchy. We prove that the probability hierarchy is decidable, i.e. there exists an algorithm that receives p_1 and p_2 and answers whether PFIN-type learning with the probability of success p_1 is equivalent to PFIN-type learning with the probability of success p_2. To prove our result, we analyze the topological structure of the probability hierarchy. We prove that it is well-ordered in descending ordering and order-equivalent to ordinal epsilon_0. This shows that the structure of the hierarchy is very complicated. Using similar methods, we also prove that, for PFIN-type learning, team learning and probabilistic learning are of the same power.


title: On the Effect of Fading on Ad hoc Networking

abstract: Most MANET (Mobile Ad hoc NETwork) research assumes idealized propagation models. Experimental results have shown significant divergence from simulation results due to the effect of signal fading in realistic wireless communication channels. In this paper, we characterize the impact of fading on protocol performance. We first study the effect of fading on MAC performance and show that its effect can be dominating. One of our important conclusions is that eliminating RTS/CTS packets results in more effective operation under fading. We also identify an unfairness problem that arises due to backoffs in the presence of fading. Moreover, fading results in several subtle interactions between the MAC and routing layers. We identify several of these problems and make observations about effective approaches for addressing them. For example, the criteria for determining the best path should not only consider the link status but also the link order. In addition, because routing protocols rely on MAC level transmission failure (when the retry limit is exceeded), route failure errors are often generated unnecessarily. Finally, because MAC level broadcasts are unreliable, they are especially vulnerable to fading. We analyze these effects and outline preliminary solutions to them.


title: Multiple Description Quantization via Gram-Schmidt Orthogonalization

abstract: The multiple description (MD) problem has received considerable attention as a model of information transmission over unreliable channels. A general framework for designing efficient multiple description quantization schemes is proposed in this paper. We provide a systematic treatment of the El Gamal-Cover (EGC) achievable MD rate-distortion region, and show that any point in the EGC region can be achieved via a successive quantization scheme along with quantization splitting. For the quadratic Gaussian case, the proposed scheme has an intrinsic connection with the Gram-Schmidt orthogonalization, which implies that the whole Gaussian MD rate-distortion region is achievable with a sequential dithered lattice-based quantization scheme as the dimension of the (optimal) lattice quantizers becomes large. Moreover, this scheme is shown to be universal for all i.i.d. smooth sources with performance no worse than that for an i.i.d. Gaussian source with the same variance and asymptotically optimal at high resolution. A class of low-complexity MD scalar quantizers in the proposed general framework also is constructed and is illustrated geometrically; the performance is analyzed in the high resolution regime, which exhibits a noticeable improvement over the existing MD scalar quantization schemes.


title: Statistical analysis of quality measures for mobile ad hoc networks

abstract: How can the quality of a mobile ad hoc network (MANET) be quantified? This work aims at an answer based on the lower network layers, i.e. on connectivity between the wireless nodes, using statistical methods. A number of different quality measures are introduced and classified according to their scaling behaviour. They are analysed in a statistical model of a 1-dimensional MANET system (corresponding e.g. to cars on a road). Neglecting boundary effects, the model turns out to be exactly solvable, so that explicit analytical results for the quality levels can be obtained both at fixed system size and in the limit of large systems. In particular, this improves estimates known in the literature for the probability of connectedness of 1-dimensional MANETs.


title: Fast Codes for Large Alphabets

abstract: We address the problem of constructing a fast lossless code in the case when the source alphabet is large. The main idea of the new scheme may be described as follows. We group letters with small probabilities in subsets (acting as super letters) and use time consuming coding for these subsets only, whereas letters in the subsets have the same code length and therefore can be coded fast. The described scheme can be applied to sources with known and unknown statistics.


title: Using Information Theory Approach to Randomness Testing

abstract: We address the problem of detecting deviations of binary sequence from randomness,which is very important for random number (RNG) and pseudorandom number generators (PRNG). Namely, we consider a null hypothesis $H_0$ that a given bit sequence is generated by Bernoulli source with equal probabilities of 0 and 1 and the alternative hypothesis $H_1$ that the sequence is generated by a stationary and ergodic source which differs from the source under $H_0$. We show that data compression methods can be used as a basis for such testing and describe two new tests for randomness, which are based on ideas of universal coding. Known statistical tests and suggested ones are applied for testing PRNGs. Those experiments show that the power of the new tests is greater than of many known algorithms.


title: The Bandwidth Exchange Architecture

abstract: New applications for the Internet such as video on demand, grid computing etc. depend on the availability of high bandwidth connections with acceptable Quality of Service (QoS). There appears to be, therefore, a requirement for a market where bandwidth-related transactions can take place. For this market to be effective, it must be efficient for both the provider (seller) and the user (buyer) of the bandwidth. This implies that: (a) the buyer must have a wide choice of providers that operate in a competitive environment, (b) the seller must be assured that a QoS transaction will be paid by the customer, and (c) the QoS transaction establishment must have low overheads so that it may be used by individual customers without a significant burden to the provider. In order to satisfy these requirements, we propose a framework that allows customers to purchase bandwidth using an open market where providers advertise links and capacities and customers bid for these services. The model is close to that of a commodities market that offers both advance bookings (futures) and a spot market. We explore the mechanisms that can support such a model.


title: Super Object Oriented Programming

abstract: This submission has been withdrawn at the request of the author.


title: Towards a Group Theoretic Quantum Encryption Scheme Based on Generalized Hidden Subgroup Problem

abstract: This paper introduces a completely new approach to encryption based on group theoretic quantum framework. Quantum cryptography has essentially focused only on key distribution and proceeded with classical encryption algorithm with the generated key. Here, we present a first step towards a quantum encryption scheme based on the solution for the hidden subgroup problem. The shared secret key K from QKD evolves as a generator for a subgroup H of a group G, in combination of the plain text data modeled as group elements. The key K helps in regeneration of the plain data on the receiver's side based on subgroup reconstruction. This paper models all quantum computations using group representations. A non-constructive proof is attempted towards the security of the encryption scheme. We also address the issues involved in a such a venture into the realms of Quantum data encryption.


title: Reversible Fault-Tolerant Logic

abstract: It is now widely accepted that the CMOS technology implementing irreversible logic will hit a scaling limit beyond 2016, and that the increased power dissipation is a major limiting factor. Reversible computing can potentially require arbitrarily small amounts of energy. Recently several nano-scale devices which have the potential to scale, and which naturally perform reversible logic, have emerged. This paper addresses several fundamental issues that need to be addressed before any nano-scale reversible computing systems can be realized, including reliability and performance trade-offs and architecture optimization. Many nano-scale devices will be limited to only near neighbor interactions, requiring careful optimization of circuits. We provide efficient fault-tolerant (FT) circuits when restricted to both 2D and 1D. Finally, we compute bounds on the entropy (and hence, heat) generated by our FT circuits and provide quantitative estimates on how large can we make our circuits before we lose any advantage over irreversible computing.