title: The Random Buffer Tree : A Randomized Technique for I/O-efficient Algorithms

abstract: In this paper, we present a probabilistic self-balancing dictionary data structure for massive data sets, and prove expected amortized I/O-optimal bounds on the dictionary operations. We show how to use the structure as an I/O-optimal priority queue. The data structure, which we call as the random buffer tree, abstracts the properties of the random treap and the buffer tree and has the same expected I/O-bounds as the buffer tree.


title: The Effect of Faults on Network Expansion

abstract: In this paper we study the problem of how resilient networks are to node faults. Specifically, we investigate the question of how many faults a network can sustain so that it still contains a large (i.e. linear-sized) connected component that still has approximately the same expansion as the original fault-free network. For this we apply a pruning technique which culls away parts of the faulty network which have poor expansion. This technique can be applied to both adversarial faults and to random faults. For adversarial faults we prove that for every network with expansion alpha, a large connected component with basically the same expansion as the original network exists for up to a constant times alpha n faults. This result is tight in the sense that every graph G of size n and uniform expansion alpha(.), i.e. G has an expansion of alpha(n) and every subgraph G' of size m of G has an expansion of O(alpha(m)), can be broken into sublinear components with omega(alpha(n) n) faults. For random faults we observe that the situation is significantly different, because in this case the expansion of a graph only gives a very weak bound on its resilience to random faults. More specifically, there are networks of uniform expansion O(sqrt{n}) that are resilient against a constant fault probability but there are also networks of uniform expansion Omega(1/log n) that are not resilient against a O(1/log n) fault probability. Thus, a different parameter is needed. For this we introduce the span of a graph which allows us to determine the maximum fault probability in a much better way than the expansion can. We use the span to show the first known results for the effect of random faults on the expansion of d-dimensional meshes.


title: XML framework for concept description and knowledge representation

abstract: An XML framework for concept description is given, based upon the fact that the tree structure of XML implies the logical structure of concepts as defined by attributional calculus. Especially, the attribute-value representation is implementable in the XML framework. Since the attribute-value representation is an important way to represent knowledge in AI, the framework offers a further and simpler way than the powerful RDF technology.


title: Characterisations of Intersection Graphs by Vertex Orderings

abstract: Characterisations of interval graphs, comparability graphs, co-comparability graphs, permutation graphs, and split graphs in terms of linear orderings of the vertex set are presented. As an application, it is proved that interval graphs, co-comparability graphs, AT-free graphs, and split graphs have bandwidth bounded by their maximum degree.


title: When Do Differences Matter? On-Line Feature Extraction Through Cognitive Economy

abstract: For an intelligent agent to be truly autonomous, it must be able to adapt its representation to the requirements of its task as it interacts with the world. Most current approaches to on-line feature extraction are ad hoc; in contrast, this paper presents an algorithm that bases judgments of state compatibility and state-space abstraction on principled criteria derived from the psychological principle of cognitive economy. The algorithm incorporates an active form of Q-learning, and partitions continuous state-spaces by merging and splitting Voronoi regions. The experiments illustrate a new methodology for testing and comparing representations by means of learning curves. Results from the puck-on-a-hill task demonstrate the algorithm's ability to learn effective representations, superior to those produced by some other, well-known, methods.


title: The Persistent Buffer Tree : An I/O-efficient Index for Temporal Data

abstract: In a variety of applications, we need to keep track of the development of a data set over time. For maintaining and querying this multi version data I/O-efficiently, external memory data structures are required. In this paper, we present a probabilistic self-balancing persistent data structure in external memory called the persistent buffer tree, which supports insertions, updates and deletions of data items at the present version and range queries for any version, past or present. The persistent buffer tree is I/O-optimal in the sense that the expected amortized I/O performance bounds are asymptotically the same as the deterministic amortized bounds of the (single version) buffer tree in the worst case.


title: Propagation by Selective Initialization and Its Application to Numerical Constraint Satisfaction Problems

abstract: Numerical analysis has no satisfactory method for the more realistic optimization models. However, with constraint programming one can compute a cover for the solution set to arbitrarily close approximation. Because the use of constraint propagation for composite arithmetic expressions is computationally expensive, consistency is computed with interval arithmetic. In this paper we present theorems that support, selective initialization, a simple modification of constraint propagation that allows composite arithmetic expressions to be handled efficiently.


title: Elements for Response Time Statistics in ERP Transaction Systems

abstract: We present some measurements and ideas for response time statistics in ERP systems. It is shown that the response time distribution of a given transaction in a given system is generically a log-normal distribution or, in some situations, a sum of two or more log-normal distributions. We present some arguments for this form of the distribution based on heuristic rules for response times, and we show data from performance measurements in actual systems to support the log-normal form. Deviations of the log-normal form can often be traced back to performance problems in the system. Consequences for the interpretation of response time data and for service level agreements are discussed.


title: Online Searching with an Autonomous Robot

abstract: We discuss online strategies for visibility-based searching for an object hidden behind a corner, using Kurt3D, a real autonomous mobile robot. This task is closely related to a number of well-studied problems. Our robot uses a three-dimensional laser scanner in a stop, scan, plan, go fashion for building a virtual three-dimensional environment. Besides planning trajectories and avoiding obstacles, Kurt3D is capable of identifying objects like a chair. We derive a practically useful and asymptotically optimal strategy that guarantees a competitive ratio of 2, which differs remarkably from the well-studied scenario without the need of stopping for surveying the environment. Our strategy is used by Kurt3D, documented in a separate video.


title: Model-checking Driven Black-box Testing Algorithms for Systems with Unspecified Components

abstract: Component-based software development has posed a serious challenge to system verification since externally-obtained components could be a new source of system failures. This issue can not be completely solved by either model-checking or traditional software testing techniques alone due to several reasons: 1) externally obtained components are usually unspecified/partially specified; 2)it is generally difficult to establish an adequacy criteria for testing a component; 3)components may be used to dynamically upgrade a system. This paper introduces a new approach (called {\em model-checking driven black-box testing}) that combines model-checking with traditional black-box software testing to tackle the problem in a complete, sound, and automatic way. The idea is to, with respect to some requirement (expressed in CTL or LTL) about the system, use model-checking techniques to derive a condition (expressed in communication graphs) for an unspecified component such that the system satisfies the requirement iff the condition is satisfied by the component, and which can be established by testing the component with test cases generated from the condition on-the-fly. In this paper, we present model-checking driven black-box testing algorithms to handle both CTL and LTL requirements. We also illustrate the idea through some examples.


title: 2-Sat Sub-Clauses and the Hypernodal Structure of the 3-Sat Problem

abstract: Like simpler graphs, nested (hypernodal) graphs consist of two components: a set of nodes and a set of edges, where each edge connects a pair of nodes. In the hypernodal graph model, however, a node may contain other graphs, so that a node may be contained in a graph that it contains. The inherently recursive structure of the hypernodal graph model aptly characterizes both the structure and dynamic of the 3-sat problem, a broadly applicable, though intractable, computer science problem. In this paper I first discuss the structure of the 3-sat problem, analyzing the relation of 3-sat to 2-sat, a related, though tractable problem. I then discuss sub-clauses and sub-clause thresholds and the transformation of sub-clauses into implication graphs, demonstrating how combinations of implication graphs are equivalent to hypernodal graphs. I conclude with a brief discussion of the use of hypernodal graphs to model the 3-sat problem, illustrating how hypernodal graphs model both the conditions for satisfiability and the process by which particular 3-sat assignments either succeed or fail.


title: Algorithms for Estimating Information Distance with Application to Bioinformatics and Linguistics

abstract: After reviewing unnormalized and normalized information distances based on incomputable notions of Kolmogorov complexity, we discuss how Kolmogorov complexity can be approximated by data compression algorithms. We argue that optimal algorithms for data compression with side information can be successfully used to approximate the normalized distance. Next, we discuss an alternative information distance, which is based on relative entropy rate (also known as Kullback-Leibler divergence), and compression-based algorithms for its estimation. Based on available biological and linguistic data, we arrive to unexpected conclusion that in Bioinformatics and Computational Linguistics this alternative distance is more relevant and important than the ones based on Kolmogorov complexity.


title: Near Rationality and Competitive Equilibria in Networked Systems

abstract: A growing body of literature in networked systems research relies on game theory and mechanism design to model and address the potential lack of cooperation between self-interested users. Most game-theoretic models applied to system research only describe competitive equilibria in terms of pure Nash equilibria, that is, a situation where the strategy of each user is deterministic, and is her best response to the strategies of all the other users. However, the assumptions necessary for a pure Nash equilibrium to hold may be too stringent for practical systems. Using three case studies on computer security, TCP congestion control, and network formation, we outline the limits of game-theoretic models relying on Nash equilibria, and we argue that considering competitive equilibria of a more general form may help reconcile predictions from game-theoretic models with empirically observed behavior.


title: NLOMJ--Natural Language Object Model in Java

abstract: In this paper we present NLOMJ--a natural language object model in Java with English as the experiment language. This modal describes the grammar elements of any permissible expression in a natural language and their complicated relations with each other with the concept "Object" in OOP(Object Oriented Programming). Directly mapped to the syntax and semantics of the natural language, it can be used in information retrieval as a linguistic method. Around the UML diagram of the NLOMJ the important classes(Sentence, Clause and Phrase) and their sub classes are introduced and their syntactic and semantic meanings are explained.


title: Extraction of topological features from communication network topological patterns using self-organizing feature maps

abstract: Different classes of communication network topologies and their representation in the form of adjacency matrix and its eigenvalues are presented. A self-organizing feature map neural network is used to map different classes of communication network topological patterns. The neural network simulation results are reported.


title: Benchmarking Blunders and Things That Go Bump in the Night

abstract: Benchmarking; by which I mean any computer system that is driven by a controlled workload, is the ultimate in performance testing and simulation. Aside from being a form of institutionalized cheating, it also offer countless opportunities for systematic mistakes in the way the workloads are applied and the resulting measurements interpreted. Right test, wrong conclusion is a ubiquitous mistake that happens because test engineers tend to treat data as divine. Such reverence is not only misplaced, it's also a sure ticket to production hell when the application finally goes live. I demonstrate how such mistakes can be avoided by means of two war stories that are real WOPRs. (a) How to resolve benchmark flaws over the psychic hotline and (b) How benchmarks can go flat with too much Java juice. In each case I present simple performance models and show how they can be applied to correctly assess benchmark data.


title: A note on dimensions of polynomial size circuits

abstract: In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every $i\geq 0$, $\Ppoly$ has $i$th order scaled $\pthree$-strong dimension 0. We also show that $\Ppoly^\io$ has $\pthree$-dimension 1/2, $\pthree$-strong dimension 1. Our results improve previous measure results of Lutz (1992) and dimension results of Hitchcock and Vinodchandran (2004).


title: Speculation on graph computation architectures and computing via synchronization

abstract: A speculative overview of a future topic of research. The paper is a collection of ideas concerning two related areas: 1) Graph computation machines ("computing with graphs"). This is the class of models of computation in which the state of the computation is represented as a graph or network. 2) Arc-based neural networks, which store information not as activation in the nodes, but rather by adding and deleting arcs. Sometimes the arcs may be interpreted as synchronization. Warnings to readers: this is not the sort of thing that one might submit to a journal or conference. No proofs are presented. The presentation is informal, and written at an introductory level. You'll probably want to wait for a more concise presentation.


title: Visualising the structure of architectural open spaces based on shape analysis

abstract: This paper proposes the application of some well known two-dimensional geometrical shape descriptors for the visualisation of the structure of architectural open spaces. The paper demonstrates the use of visibility measures such as distance to obstacles and amount of visible space to calculate shape descriptors such as convexity and skeleton of the open space. The aim of the paper is to indicate a simple, objective and quantifiable approach to understand the structure of open spaces otherwise impossible due to the complex construction of built structures.


title: Using matrices in post-processing phase of CFD simulations

abstract: In this work I present a technique of construction and fast evaluation of a family of cubic polynomials for analytic smoothing and graphical rendering of particles trajectories for flows in a generic geometry. The principal result of the work was implementation and test of a method for interpolating 3D points by regular parametric curves and their fast and efficient evaluation for a good resolution of rendering. For the purpose I have used a parallel environment using a multiprocessor cluster architecture. The efficiency of the used method is good, mainly reducing the number of floating-points computations by caching the numerical values of some line-parameter's powers, and reducing the necessity of communication among processes. This work has been developed for the Research and Development Department of my company for planning advanced customized models of industrial burners.


title: Incompleteness of States w.r.t. Traces in Model Checking

abstract: Cousot and Cousot introduced and studied a general past/future-time specification language, called mu*-calculus, featuring a natural time-symmetric trace-based semantics. The standard state-based semantics of the mu*-calculus is an abstract interpretation of its trace-based semantics, which turns out to be incomplete (i.e., trace-incomplete), even for finite systems. As a consequence, standard state-based model checking of the mu*-calculus is incomplete w.r.t. trace-based model checking. This paper shows that any refinement or abstraction of the domain of sets of states induces a corresponding semantics which is still trace-incomplete for any propositional fragment of the mu*-calculus. This derives from a number of results, one for each incomplete logical/temporal connective of the mu*-calculus, that characterize the structure of models, i.e. transition systems, whose corresponding state-based semantics of the mu*-calculus is trace-complete.


title: Exploiting Cross-Document Relations for Multi-document Evolving Summarization

abstract: This paper presents a methodology for summarization from multiple documents which are about a specific topic. It is based on the specification and identification of the cross-document relations that occur among textual elements within those documents. Our methodology involves the specification of the topic-specific entities, the messages conveyed for the specific entities by certain textual elements and the specification of the relations that can hold among these messages. The above resources are necessary for setting up a specific topic for our query-based summarization approach which uses these resources to identify the query-specific messages within the documents and the query-specific relations that connect these messages across documents.


title: A General Framework For Lazy Functional Logic Programming With Algebraic Polymorphic Types

abstract: We propose a general framework for first-order functional logic programming, supporting lazy functions, non-determinism and polymorphic datatypes whose data constructors obey a set C of equational axioms. On top of a given C, we specify a program as a set R of C-based conditional rewriting rules for defined functions. We argue that equational logic does not supply the proper semantics for such programs. Therefore, we present an alternative logic which includes C-based rewriting calculi and a notion of model. We get soundness and completeness for C-based rewriting w.r.t. models, existence of free models for all programs, and type preservation results. As operational semantics, we develop a sound and complete procedure for goal solving, which is based on the combination of lazy narrowing with unification modulo C. Our framework is quite expressive for many purposes, such as solving action and change problems, or realizing the GAMMA computation model.


title: Knowledge And The Action Description Language A

abstract: We introduce Ak, an extension of the action description language A (Gelfond and Lifschitz, 1993) to handle actions which affect knowledge. We use sensing actions to increase an agent's knowledge of the world and non-deterministic actions to remove knowledge. We include complex plans involving conditionals and loops in our query language for hypothetical reasoning. We also present a translation of Ak domain descriptions into epistemic logic programs.


title: Multi-Threading And Message Communication In Qu-Prolog

abstract: This paper presents the multi-threading and internet message communication capabilities of Qu-Prolog. Message addresses are symbolic and the communications package provides high-level support that completely hides details of IP addresses and port numbers as well as the underlying TCP/IP transport layer. The combination of the multi-threads and the high level inter-thread message communications provide simple, powerful support for implementing internet distributed intelligent applications.


title: Constraint Logic Programming with Hereditary Harrop Formula

abstract: Constraint Logic Programming (CLP) and Hereditary Harrop formulas (HH) are two well known ways to enhance the expressivity of Horn clauses. In this paper, we present a novel combination of these two approaches. We show how to enrich the syntax and proof theory of HH with the help of a given constraint system, in such a way that the key property of HH as a logic programming language (namely, the existence of uniform proofs) is preserved. We also present a procedure for goal solving, showing its soundness and completeness for computing answer constraints. As a consequence of this result, we obtain a new strong completeness theorem for CLP that avoids the need to build disjunctions of computed answers, as well as a more abstract formulation of a known completeness theorem for HH.


title: New Covert Channels in HTTP

abstract: This paper presents new methods enabling anonymous communication on the Internet. We describe a new protocol that allows us to create an anonymous overlay network by exploiting the web browsing activities of regular users. We show that the overlay network provides an anonymity set greater than the set of senders and receivers in a realistic threat model. In particular, the protocol provides unobservability in our threat model.


title: Finite-Tree Analysis for Constraint Logic-Based Languages: The Complete Unabridged Version

abstract: Logic languages based on the theory of rational, possibly infinite, trees have much appeal in that rational trees allow for faster unification (due to the safe omission of the occurs-check) and increased expressivity (cyclic terms can provide very efficient representations of grammars and other useful objects). Unfortunately, the use of infinite rational trees has problems. For instance, many of the built-in and library predicates are ill-defined for such trees and need to be supplemented by run-time checks whose cost may be significant. Moreover, some widely-used program analysis and manipulation techniques are correct only for those parts of programs working over finite trees. It is thus important to obtain, automatically, a knowledge of the program variables (the finite variables) that, at the program points of interest, will always be bound to finite terms. For these reasons, we propose here a new data-flow analysis, based on abstract interpretation, that captures such information.


title: A lambda calculus for quantum computation with classical control

abstract: The objective of this paper is to develop a functional programming language for quantum computers. We develop a lambda calculus for the classical control model, following the first author's work on quantum flow-charts. We define a call-by-value operational semantics, and we give a type system using affine intuitionistic linear logic. The main results of this paper are the safety properties of the language and the development of a type inference algorithm.


title: Convergence of Discrete MDL for Sequential Prediction

abstract: We study the properties of the Minimum Description Length principle for sequence prediction, considering a two-part MDL estimator which is chosen from a countable class of models. This applies in particular to the important case of universal sequence prediction, where the model class corresponds to all algorithms for some fixed universal Turing machine (this correspondence is by enumerable semimeasures, hence the resulting models are stochastic). We prove convergence theorems similar to Solomonoff's theorem of universal induction, which also holds for general Bayes mixtures. The bound characterizing the convergence speed for MDL predictions is exponentially larger as compared to Bayes mixtures. We observe that there are at least three different ways of using MDL for prediction. One of these has worse prediction properties, for which predictions only converge if the MDL estimator stabilizes. We establish sufficient conditions for this to occur. Finally, some immediate consequences for complexity relations and randomness criteria are proven.


title: Efficient coroutine generation of constrained Gray sequences

abstract: We study an interesting family of cooperating coroutines, which is able to generate all patterns of bits that satisfy certain fairly general ordering constraints, changing only one bit at a time. (More precisely, the directed graph of constraints is required to be cycle-free when it is regarded as an undirected graph.) If the coroutines are implemented carefully, they yield an algorithm that needs only a bounded amount of computation per bit change, thereby solving an open problem in the field of combinatorial pattern generation.


title: Toward a New Policy for Scientific and Technical Communication: the Case of Kyrgyz Republic

abstract: The objective of this policy paper is to formulate a new policy in the field of scientific and technical information (STI) in Kyrgyz Republic in the light of emergence and rapid development of electronic scientific communication. The major problem with communication in science in the Republic is lack of adequate access to information by scientists. An equally serious problem is poor visibility of research conducted in Kyrgyzstan and, as consequence, negligible research impact on academic society globally. The paper proposes an integrated approach to formulation of a new STI policy based on a number of policy components: telecommunication networks, computerization, STI systems, legislation & standards, and education & trainings. Two alternatives were considered: electronic vs. paper-based scientific communication and development of the national STI system vs. cross-national virtual collaboration. The study results in suggesting a number of policy recommendations for identified stakeholders.


title: Splitting an operator: Algebraic modularity results for logics with fixpoint semantics

abstract: It is well known that, under certain conditions, it is possible to split logic programs under stable model semantics, i.e. to divide such a program into a number of different "levels", such that the models of the entire program can be constructed by incrementally constructing models for each level. Similar results exist for other non-monotonic formalisms, such as auto-epistemic logic and default logic. In this work, we present a general, algebraicsplitting theory for logics with a fixpoint semantics. Together with the framework of approximation theory, a general fixpoint theory for arbitrary operators, this gives us a uniform and powerful way of deriving splitting results for each logic with a fixpoint semantics. We demonstrate the usefulness of these results, by generalizing existing results for logic programming, auto-epistemic logic and default logic.


title: Model checking for Process Rewrite Systems and a class of action--based regular properties

abstract: We consider the model checking problem for Process Rewrite Systems (PRSs), an infinite-state formalism (non Turing-powerful) which subsumes many common models such as Pushdown Processes and Petri Nets. PRSs can be adopted as formal models for programs with dynamic creation and synchronization of concurrent processes, and with recursive procedures. The model-checking problem for PRSs and action-based linear temporal logic (ALTL) is undecidable. However, decidability for some interesting fragment of ALTL remains an open question. In this paper we state decidability results concerning generalized acceptance properties about infinite derivations (infinite term rewriting) in PRSs. As a consequence, we obtain decidability of the model-checking (restricted to infinite runs) for PRSs and a meaningful fragment of ALTL.


title: Quantum Computers

abstract: This research paper gives an overview of quantum computers - description of their operation, differences between quantum and silicon computers, major construction problems of a quantum computer and many other basic aspects. No special scientific knowledge is necessary for the reader.


title: Maximum-likelihood decoding of Reed-Solomon Codes is NP-hard

abstract: Maximum-likelihood decoding is one of the central algorithmic problems in coding theory. It has been known for over 25 years that maximum-likelihood decoding of general linear codes is NP-hard. Nevertheless, it was so far unknown whether maximum- likelihood decoding remains hard for any specific family of codes with nontrivial algebraic structure. In this paper, we prove that maximum-likelihood decoding is NP-hard for the family of Reed-Solomon codes. We moreover show that maximum-likelihood decoding of Reed-Solomon codes remains hard even with unlimited preprocessing, thereby strengthening a result of Bruck and Naor.


title: Bi-criteria Algorithm for Scheduling Jobs on Cluster Platforms

abstract: We describe in this paper a new method for building an efficient algorithm for scheduling jobs in a cluster. Jobs are considered as parallel tasks (PT) which can be scheduled on any number of processors. The main feature is to consider two criteria that are optimized together. These criteria are the makespan and the weighted minimal average completion time (minsum). They are chosen for their complementarity, to be able to represent both user-oriented objectives and system administrator objectives. We propose an algorithm based on a batch policy with increasing batch sizes, with a smart selection of jobs in each batch. This algorithm is assessed by intensive simulation results, compared to a new lower bound (obtained by a relaxation of ILP) of the optimal schedules for both criteria separately. It is currently implemented in an actual real-size cluster platform.


title: "In vivo" spam filtering: A challenge problem for data mining

abstract: Spam, also known as Unsolicited Commercial Email (UCE), is the bane of email communication. Many data mining researchers have addressed the problem of detecting spam, generally by treating it as a static text classification problem. True in vivo spam filtering has characteristics that make it a rich and challenging domain for data mining. Indeed, real-world datasets with these characteristics are typically difficult to acquire and to share. This paper demonstrates some of these characteristics and argues that researchers should pursue in vivo spam filtering as an accessible domain for investigating them.


title: A Comparative Study of Fuzzy Classification Methods on Breast Cancer Data

abstract: In this paper, we examine the performance of four fuzzy rule generation methods on Wisconsin breast cancer data. The first method generates fuzzy if then rules using the mean and the standard deviation of attribute values. The second approach generates fuzzy if then rules using the histogram of attributes values. The third procedure generates fuzzy if then rules with certainty of each attribute into homogeneous fuzzy sets. In the fourth approach, only overlapping areas are partitioned. The first two approaches generate a single fuzzy if then rule for each class by specifying the membership function of each antecedent fuzzy set using the information about attribute values of training patterns. The other two approaches are based on fuzzy grids with homogeneous fuzzy partitions of each attribute. The performance of each approach is evaluated on breast cancer data sets. Simulation results show that the Modified grid approach has a high classification rate of 99.73 %.


title: Intelligent Systems: Architectures and Perspectives

abstract: The integration of different learning and adaptation techniques to overcome individual limitations and to achieve synergetic effects through the hybridization or fusion of these techniques has, in recent years, contributed to a large number of new intelligent system designs. Computational intelligence is an innovative framework for constructing intelligent hybrid architectures involving Neural Networks (NN), Fuzzy Inference Systems (FIS), Probabilistic Reasoning (PR) and derivative free optimization techniques such as Evolutionary Computation (EC). Most of these hybridization approaches, however, follow an ad hoc design methodology, justified by success in certain application domains. Due to the lack of a common framework it often remains difficult to compare the various hybrid systems conceptually and to evaluate their performance comparatively. This chapter introduces the different generic architectures for integrating intelligent systems. The designing aspects and perspectives of different hybrid archirectures like NN-FIS, EC-FIS, EC-NN, FIS-PR and NN-FIS-EC systems are presented. Some conclusions are also provided towards the end.


title: A Neuro-Fuzzy Approach for Modelling Electricity Demand in Victoria

abstract: Neuro-fuzzy systems have attracted growing interest of researchers in various scientific and engineering areas due to the increasing need of intelligent systems. This paper evaluates the use of two popular soft computing techniques and conventional statistical approach based on Box--Jenkins autoregressive integrated moving average (ARIMA) model to predict electricity demand in the State of Victoria, Australia. The soft computing methods considered are an evolving fuzzy neural network (EFuNN) and an artificial neural network (ANN) trained using scaled conjugate gradient algorithm (CGA) and backpropagation (BP) algorithm. The forecast accuracy is compared with the forecasts used by Victorian Power Exchange (VPX) and the actual energy demand. To evaluate, we considered load demand patterns for 10 consecutive months taken every 30 min for training the different prediction models. Test results show that the neuro-fuzzy system performed better than neural networks, ARIMA model and the VPX forecasts.


title: Neuro Fuzzy Systems: Sate-of-the-Art Modeling Techniques

abstract: Fusion of Artificial Neural Networks (ANN) and Fuzzy Inference Systems (FIS) have attracted the growing interest of researchers in various scientific and engineering areas due to the growing need of adaptive intelligent systems to solve the real world problems. ANN learns from scratch by adjusting the interconnections between layers. FIS is a popular computing framework based on the concept of fuzzy set theory, fuzzy if-then rules, and fuzzy reasoning. The advantages of a combination of ANN and FIS are obvious. There are several approaches to integrate ANN and FIS and very often it depends on the application. We broadly classify the integration of ANN and FIS into three categories namely concurrent model, cooperative model and fully fused model. This paper starts with a discussion of the features of each model and generalize the advantages and deficiencies of each model. We further focus the review on the different types of fused neuro-fuzzy systems and citing the advantages and disadvantages of each model.


title: Is Neural Network a Reliable Forecaster on Earth? A MARS Query!

abstract: Long-term rainfall prediction is a challenging task especially in the modern world where we are facing the major environmental problem of global warming. In general, climate and rainfall are highly non-linear phenomena in nature exhibiting what is known as the butterfly effect. While some regions of the world are noticing a systematic decrease in annual rainfall, others notice increases in flooding and severe storms. The global nature of this phenomenon is very complicated and requires sophisticated computer modeling and simulation to predict accurately. In this paper, we report a performance analysis for Multivariate Adaptive Regression Splines (MARS)and artificial neural networks for one month ahead prediction of rainfall. To evaluate the prediction efficiency, we made use of 87 years of rainfall data in Kerala state, the southern part of the Indian peninsula situated at latitude -longitude pairs (8o29'N - 76o57' E). We used an artificial neural network trained using the scaled conjugate gradient algorithm. The neural network and MARS were trained with 40 years of rainfall data. For performance evaluation, network predicted outputs were compared with the actual rainfall data. Simulation results reveal that MARS is a good forecasting tool and performed better than the considered neural network.


title: DCT Based Texture Classification Using Soft Computing Approach

abstract: Classification of texture pattern is one of the most important problems in pattern recognition. In this paper, we present a classification method based on the Discrete Cosine Transform (DCT) coefficients of texture image. As DCT works on gray level image, the color scheme of each image is transformed into gray levels. For classifying the images using DCT we used two popular soft computing techniques namely neurocomputing and neuro-fuzzy computing. We used a feedforward neural network trained using the backpropagation learning and an evolving fuzzy neural network to classify the textures. The soft computing models were trained using 80% of the texture data and remaining was used for testing and validation purposes. A performance comparison was made among the soft computing models for the texture classification problem. We also analyzed the effects of prolonged training of neural networks. It is observed that the proposed neuro-fuzzy model performed better than neural network.


title: Estimating Genome Reversal Distance by Genetic Algorithm

abstract: Sorting by reversals is an important problem in inferring the evolutionary relationship between two genomes. The problem of sorting unsigned permutation has been proven to be NP-hard. The best guaranteed error bounded is the 3/2- approximation algorithm. However, the problem of sorting signed permutation can be solved easily. Fast algorithms have been developed both for finding the sorting sequence and finding the reversal distance of signed permutation. In this paper, we present a way to view the problem of sorting unsigned permutation as signed permutation. And the problem can then be seen as searching an optimal signed permutation in all n2 corresponding signed permutations. We use genetic algorithm to conduct the search. Our experimental result shows that the proposed method outperform the 3/2-approximation algorithm.


title: A High-Level Reconfigurable Computing Platform Software Frameworks

abstract: Reconfigurable computing refers to the use of processors, such as Field Programmable Gate Arrays (FPGAs), that can be modified at the hardware level to take on different processing tasks. A reconfigurable computing platform describes the hardware and software base on top of which modular extensions can be created, depending on the desired application. Such reconfigurable computing platforms can take on varied designs and implementations, according to the constraints imposed and features desired by the scope of applications. This paper introduces a PC-based reconfigurable computing platform software frameworks that is flexible and extensible enough to abstract the different hardware types and functionality that different PCs may have. The requirements of the software platform, architectural issues addressed, rationale behind the decisions made, and frameworks design implemented are discussed.


title: Intrusion Detection Systems Using Adaptive Regression Splines

abstract: Past few years have witnessed a growing recognition of intelligent techniques for the construction of efficient and reliable intrusion detection systems. Due to increasing incidents of cyber attacks, building effective intrusion detection systems (IDS) are essential for protecting information systems security, and yet it remains an elusive goal and a great challenge. In this paper, we report a performance analysis between Multivariate Adaptive Regression Splines (MARS), neural networks and support vector machines. The MARS procedure builds flexible regression models by fitting separate splines to distinct intervals of the predictor variables. A brief comparison of different neural network learning algorithms is also given.


title: Data Mining Approach for Analyzing Call Center Performance

abstract: The aim of our research was to apply well-known data mining techniques (such as linear neural networks, multi-layered perceptrons, probabilistic neural networks, classification and regression trees, support vector machines and finally a hybrid decision tree neural network approach) to the problem of predicting the quality of service in call centers; based on the performance data actually collected in a call center of a large insurance company. Our aim was two-fold. First, to compare the performance of models built using the above-mentioned techniques and, second, to analyze the characteristics of the input sensitivity in order to better understand the relationship between the perform-ance evaluation process and the actual performance and in this way help improve the performance of call centers. In this paper we summarize our findings.


title: Modeling Chaotic Behavior of Stock Indices Using Intelligent Paradigms

abstract: The use of intelligent systems for stock market predictions has been widely established. In this paper, we investigate how the seemingly chaotic behavior of stock markets could be well represented using several connectionist paradigms and soft computing techniques. To demonstrate the different techniques, we considered Nasdaq-100 index of Nasdaq Stock MarketS and the S&P CNX NIFTY stock index. We analyzed 7 year's Nasdaq 100 main index values and 4 year's NIFTY index values. This paper investigates the development of a reliable and efficient technique to model the seemingly chaotic behavior of stock markets. We considered an artificial neural network trained using Levenberg-Marquardt algorithm, Support Vector Machine (SVM), Takagi-Sugeno neuro-fuzzy model and a Difference Boosting Neural Network (DBNN). This paper briefly explains how the different connectionist paradigms could be formulated using different learning methods and then investigates whether they can provide the required level of performance, which are sufficiently good and robust so as to provide a reliable forecast model for stock market indices. Experiment results reveal that all the connectionist paradigms considered could represent the stock indices behavior very accurately.


title: Hybrid Fuzzy-Linear Programming Approach for Multi Criteria Decision Making Problems

abstract: The purpose of this paper is to point to the usefulness of applying a linear mathematical formulation of fuzzy multiple criteria objective decision methods in organising business activities. In this respect fuzzy parameters of linear programming are modelled by preference-based membership functions. This paper begins with an introduction and some related research followed by some fundamentals of fuzzy set theory and technical concepts of fuzzy multiple objective decision models. Further a real case study of a manufacturing plant and the implementation of the proposed technique is presented. Empirical results clearly show the superiority of the fuzzy technique in optimising individual objective functions when compared to non-fuzzy approach. Furthermore, for the problem considered, the optimal solution helps to infer that by incorporating fuzziness in a linear programming model either in constraints, or both in objective functions and constraints, provides a similar (or even better) level of satisfaction for obtained results compared to non-fuzzy linear programming.


title: A proof of Alon's second eigenvalue conjecture and related problems

abstract: In this paper we show the following conjecture of Noga Alon. Fix a positive integer d>2 and real epsilon > 0; consider the probability that a random d-regular graph on n vertices has the second eigenvalue of its adjacency matrix greater than 2 sqrt(d-1) + epsilon; then this probability goes to zero as n tends to infinity. We prove the conjecture for a number of notions of random d-regular graph, including models for d odd. We also estimate the aforementioned probability more precisely, showing in many cases and models (but not all) that it decays like a polynomial in 1/n.


title: Computing Multi-Homogeneous Bezout Numbers is Hard

abstract: The multi-homogeneous Bezout number is a bound for the number of solutions of a system of multi-homogeneous polynomial equations, in a suitable product of projective spaces. Given an arbitrary, not necessarily multi-homogeneous system, one can ask for the optimal multi-homogenization that would minimize the Bezout number. In this paper, it is proved that the problem of computing, or even estimating the optimal multi-homogeneous Bezout number is actually NP-hard. In terms of approximation theory for combinatorial optimization, the problem of computing the best multi-homogeneous structure does not belong to APX, unless P = NP. Moreover, polynomial time algorithms for estimating the minimal multi-homogeneous Bezout number up to a fixed factor cannot exist even in a randomized setting, unless BPP contains NP.


title: Encryption Schemes using Finite Frames and Hadamard Arrays

abstract: We propose a cipher similar to the One Time Pad and McEliece cipher based on a subband coding scheme. The encoding process is an approximation to the One Time Pad encryption scheme. We present results of numerical experiments which suggest that a brute force attack to the proposed scheme does not result in all possible plaintexts, as the One Time Pad does, but still the brute force attack does not compromise the system. However, we demonstrate that the cipher is vulnerable to a chosen-plaintext attack.


title: A Grid Service Broker for Scheduling Distributed Data-Oriented Applications on Global Grids

abstract: The next generation of scientific experiments and studies, popularly called as e-Science, is carried out by large collaborations of researchers distributed around the world engaged in analysis of huge collections of data generated by scientific instruments. Grid computing has emerged as an enabler for e-Science as it permits the creation of virtual organizations that bring together communities with common objectives. Within a community, data collections are stored or replicated on distributed resources to enhance storage capability or efficiency of access. In such an environment, scientists need to have the ability to carry out their studies by transparently accessing distributed data and computational resources. In this paper, we propose and develop a Grid broker that mediates access to distributed resources by (a) discovering suitable data sources for a given analysis scenario, (b) suitable computational resources, (c) optimally mapping analysis jobs to resources, (d) deploying and monitoring job execution on selected resources, (e) accessing data from local or remote data source during job execution and (f) collating and presenting results. The broker supports a declarative and dynamic parametric programming model for creating grid applications. We have used this model in grid-enabling a high energy physics analysis application (Belle Analysis Software Framework). The broker has been used in deploying Belle experiment data analysis jobs on a grid testbed, called Belle Analysis Data Grid, having resources distributed across Australia interconnected through GrangeNet.


title: Meta-Learning Evolutionary Artificial Neural Networks

abstract: In this paper, we present MLEANN (Meta-Learning Evolutionary Artificial Neural Network), an automatic computational framework for the adaptive optimization of artificial neural networks wherein the neural network architecture, activation function, connection weights; learning algorithm and its parameters are adapted according to the problem. We explored the performance of MLEANN and conventionally designed artificial neural networks for function approximation problems. To evaluate the comparative performance, we used three different well-known chaotic time series. We also present the state of the art popular neural network learning algorithms and some experimentation results related to convergence speed and generalization performance. We explored the performance of backpropagation algorithm; conjugate gradient algorithm, quasi-Newton algorithm and Levenberg-Marquardt algorithm for the three chaotic time series. Performances of the different learning algorithms were evaluated when the activation functions and architecture were changed. We further present the theoretical background, algorithm, design strategy and further demonstrate how effective and inevitable is the proposed MLEANN framework to design a neural network, which is smaller, faster and with a better generalization performance.


title: The Largest Compatible Subset Problem for Phylogenetic Data

abstract: The phylogenetic tree construction is to infer the evolutionary relationship between species from the experimental data. However, the experimental data are often imperfect and conflicting each others. Therefore, it is important to extract the motif from the imperfect data. The largest compatible subset problem is that, given a set of experimental data, we want to discard the minimum such that the remaining is compatible. The largest compatible subset problem can be viewed as the vertex cover problem in the graph theory that has been proven to be NP-hard. In this paper, we propose a hybrid Evolutionary Computing (EC) method for this problem. The proposed method combines the EC approach and the algorithmic approach for special structured graphs. As a result, the complexity of the problem is dramatically reduced. Experiments were performed on randomly generated graphs with different edge densities. The vertex covers produced by the proposed method were then compared to the vertex covers produced by a 2-approximation algorithm. The experimental results showed that the proposed method consistently outperformed a classical 2- approximation algorithm. Furthermore, a significant improvement was found when the graph density was small.


title: A Concurrent Fuzzy-Neural Network Approach for Decision Support Systems

abstract: Decision-making is a process of choosing among alternative courses of action for solving complicated problems where multi-criteria objectives are involved. The past few years have witnessed a growing recognition of Soft Computing technologies that underlie the conception, design and utilization of intelligent systems. Several works have been done where engineers and scientists have applied intelligent techniques and heuristics to obtain optimal decisions from imprecise information. In this paper, we present a concurrent fuzzy-neural network approach combining unsupervised and supervised learning techniques to develop the Tactical Air Combat Decision Support System (TACDSS). Experiment results clearly demonstrate the efficiency of the proposed technique.


title: Evolution of a Subsumption Architecture Neurocontroller

abstract: An approach to robotics called layered evolution and merging features from the subsumption architecture into evolutionary robotics is presented, and its advantages are discussed. This approach is used to construct a layered controller for a simulated robot that learns which light source to approach in an environment with obstacles. The evolvability and performance of layered evolution on this task is compared to (standard) monolithic evolution, incremental and modularised evolution. To corroborate the hypothesis that a layered controller performs at least as well as an integrated one, the evolved layers are merged back into a single network. On the grounds of the test results, it is argued that layered evolution provides a superior approach for many tasks, and it is suggested that this approach may be the key to scaling up evolutionary robotics.


title: Analysis of Hybrid Soft and Hard Computing Techniques for Forex Monitoring Systems

abstract: In a universe with a single currency, there would be no foreign exchange market, no foreign exchange rates, and no foreign exchange. Over the past twenty-five years, the way the market has performed those tasks has changed enormously. The need for intelligent monitoring systems has become a necessity to keep track of the complex forex market. The vast currency market is a foreign concept to the average individual. However, once it is broken down into simple terms, the average individual can begin to understand the foreign exchange market and use it as a financial instrument for future investing. In this paper, we attempt to compare the performance of hybrid soft computing and hard computing techniques to predict the average monthly forex rates one month ahead. The soft computing models considered are a neural network trained by the scaled conjugate gradient algorithm and a neuro-fuzzy model implementing a Takagi-Sugeno fuzzy inference system. We also considered Multivariate Adaptive Regression Splines (MARS), Classification and Regression Trees (CART) and a hybrid CART-MARS technique. We considered the exchange rates of Australian dollar with respect to US dollar, Singapore dollar, New Zealand dollar, Japanese yen and United Kingdom pounds. The models were trained using 70% of the data and remaining was used for testing and validation purposes. It is observed that the proposed hybrid models could predict the forex rates more accurately than all the techniques when applied individually. Empirical results also reveal that the hybrid hard computing approach also improved some of our previous work using a neuro-fuzzy approach.


title: A New Computational Framework For 2D Shape-Enclosing Contours

abstract: In this paper, a new framework for one-dimensional contour extraction from discrete two-dimensional data sets is presented. Contour extraction is important in many scientific fields such as digital image processing, computer vision, pattern recognition, etc. This novel framework includes (but is not limited to) algorithms for dilated contour extraction, contour displacement, shape skeleton extraction, contour continuation, shape feature based contour refinement and contour simplification. Many of the new techniques depend strongly on the application of a Delaunay tessellation. In order to demonstrate the versatility of this novel toolbox approach, the contour extraction techniques presented here are applied to scientific problems in material science, biology and heavy ion physics.


title: Business Intelligence from Web Usage Mining

abstract: The rapid e-commerce growth has made both business community and customers face a new situation. Due to intense competition on one hand and the customer's option to choose from several alternatives business community has realized the necessity of intelligent marketing strategies and relationship management. Web usage mining attempts to discover useful knowledge from the secondary data obtained from the interactions of the users with the Web. Web usage mining has become very critical for effective Web site management, creating adaptive Web sites, business and support services, personalization, network traffic flow analysis and so on. In this paper, we present the important concepts of Web usage mining and its various practical applications. We further present a novel approach 'intelligent-miner' (i-Miner) to optimize the concurrent architecture of a fuzzy clustering algorithm (to discover web data clusters) and a fuzzy inference system to analyze the Web site visitor trends. A hybrid evolutionary fuzzy clustering algorithm is proposed in this paper to optimally segregate similar user interests. The clustered data is then used to analyze the trends using a Takagi-Sugeno fuzzy inference system learned using a combination of evolutionary algorithm and neural network learning. Proposed approach is compared with self-organizing maps (to discover patterns) and several function approximation techniques like neural networks, linear genetic programming and Takagi-Sugeno fuzzy inference system (to analyze the clusters). The results are graphically illustrated and the practical significance is discussed in detail. Empirical results clearly show that the proposed Web usage-mining framework is efficient.


title: Adaptation of Mamdani Fuzzy Inference System Using Neuro - Genetic Approach for Tactical Air Combat Decision Support System

abstract: Normally a decision support system is build to solve problem where multi-criteria decisions are involved. The knowledge base is the vital part of the decision support containing the information or data that is used in decision-making process. This is the field where engineers and scientists have applied several intelligent techniques and heuristics to obtain optimal decisions from imprecise information. In this paper, we present a hybrid neuro-genetic learning approach for the adaptation a Mamdani fuzzy inference system for the Tactical Air Combat Decision Support System (TACDSS). Some simulation results demonstrating the difference of the learning techniques and are also provided.


title: EvoNF: A Framework for Optimization of Fuzzy Inference Systems Using Neural Network Learning and Evolutionary Computation

abstract: Several adaptation techniques have been investigated to optimize fuzzy inference systems. Neural network learning algorithms have been used to determine the parameters of fuzzy inference system. Such models are often called as integrated neuro-fuzzy models. In an integrated neuro-fuzzy model there is no guarantee that the neural network learning algorithm converges and the tuning of fuzzy inference system will be successful. Success of evolutionary search procedures for optimization of fuzzy inference system is well proven and established in many application areas. In this paper, we will explore how the optimization of fuzzy inference systems could be further improved using a meta-heuristic approach combining neural network learning and evolutionary computation. The proposed technique could be considered as a methodology to integrate neural networks, fuzzy inference systems and evolutionary search procedures. We present the theoretical frameworks and some experimental results to demonstrate the efficiency of the proposed technique.


title: Optimization of Evolutionary Neural Networks Using Hybrid Learning Algorithms

abstract: Evolutionary artificial neural networks (EANNs) refer to a special class of artificial neural networks (ANNs) in which evolution is another fundamental form of adaptation in addition to learning. Evolutionary algorithms are used to adapt the connection weights, network architecture and learning algorithms according to the problem environment. Even though evolutionary algorithms are well known as efficient global search algorithms, very often they miss the best local solutions in the complex solution space. In this paper, we propose a hybrid meta-heuristic learning approach combining evolutionary learning and local search methods (using 1st and 2nd order error information) to improve the learning and faster convergence obtained using a direct evolutionary approach. The proposed technique is tested on three different chaotic time series and the test results are compared with some popular neuro-fuzzy systems and a recently developed cutting angle method of global optimization. Empirical results reveal that the proposed technique is efficient in spite of the computational complexity.


title: Computational Geometry Column 45

abstract: The algorithm of Edelsbrunner for surface reconstruction by ``wrapping'' a set of points in R^3 is described.


title: Security-Performance Tradeoffs of Inheritance based Key Predistribution for Wireless Sensor Networks

abstract: Key predistribution is a well-known technique for ensuring secure communication via encryption among sensors deployed in an ad-hoc manner to form a sensor network. In this paper, we propose a novel 2-Phase technique for key predistribution based on a combination of inherited and random key assignments from the given key pool to individual sensor nodes. We also develop an analytical framework for measuring security-performance tradeoffs of different key distribution schemes by providing metrics for measuring sensornet connectivity and resiliency to enemy attacks. In particular, we show analytically that the 2-Phase scheme provides better average connectivity and superior $q$-composite connectivity than the random scheme. We then prove that the invulnerability of a communication link under arbitrary number of node captures by an adversary is higher under the 2-Phase scheme. The probability of a communicating node pair having an exclusive key also scales better with network size under the 2-Phase scheme. We also show analytically that the vulnerability of an arbitrary communication link in the sensornet to single node capture is lower under 2-Phase assuming both network-wide as well as localized capture. Simulation results also show that the number of exclusive keys shared between any two nodes is higher while the number of $q$-composite links compromised when a given number of nodes are captured by the enemy is smaller under the 2-Phase scheme as compared to the random one.


title: Single-Strip Triangulation of Manifolds with Arbitrary Topology

abstract: Triangle strips have been widely used for efficient rendering. It is NP-complete to test whether a given triangulated model can be represented as a single triangle strip, so many heuristics have been proposed to partition models into few long strips. In this paper, we present a new algorithm for creating a single triangle loop or strip from a triangulated model. Our method applies a dual graph matching algorithm to partition the mesh into cycles, and then merges pairs of cycles by splitting adjacent triangles when necessary. New vertices are introduced at midpoints of edges and the new triangles thus formed are coplanar with their parent triangles, hence the visual fidelity of the geometry is not changed. We prove that the increase in the number of triangles due to this splitting is 50% in the worst case, however for all models we tested the increase was less than 2%. We also prove tight bounds on the number of triangles needed for a single-strip representation of a model with holes on its boundary. Our strips can be used not only for efficient rendering, but also for other applications including the generation of space filling curves on a manifold of any arbitrary topology.


title: A Probabilistic Model of Machine Translation

abstract: A probabilistic model for computer-based generation of a machine translation system on the basis of English-Russian parallel text corpora is suggested. The model is trained using parallel text corpora with pre-aligned source and target sentences. The training of the model results in a bilingual dictionary of words and "word blocks" with relevant translation probability.


title: Deductive Algorithmic Knowledge

abstract: The framework of algorithmic knowledge assumes that agents use algorithms to compute the facts they explicitly know. In many cases of interest, a deductive system, rather than a particular algorithm, captures the formal reasoning used by the agents to compute what they explicitly know. We introduce a logic for reasoning about both implicit and explicit knowledge with the latter defined with respect to a deductive system formalizing a logical theory for agents. The highly structured nature of deductive systems leads to very natural axiomatizations of the resulting logic when interpreted over any fixed deductive system. The decision problem for the logic, in the presence of a single agent, is NP-complete in general, no harder than propositional logic. It remains NP-complete when we fix a deductive system that is decidable in nondeterministic polynomial time. These results extend in a straightforward way to multiple agents.


title: Catching the Drift: Probabilistic Content Models, with Applications to Generation and Summarization

abstract: We consider the problem of modeling the content structure of texts within a specific domain, in terms of the topics the texts address and the order in which these topics appear. We first present an effective knowledge-lean method for learning content models from un-annotated documents, utilizing a novel adaptation of algorithms for Hidden Markov Models. We then apply our method to two complementary tasks: information ordering and extractive summarization. Our experiments show that incorporating content models in these applications yields substantial improvement over previously-proposed methods.


title: Supervisory Control of Fuzzy Discrete Event Systems

abstract: In order to cope with situations in which a plant's dynamics are not precisely known, we consider the problem of supervisory control for a class of discrete event systems modelled by fuzzy automata. The behavior of such discrete event systems is described by fuzzy languages; the supervisors are event feedback and can disable only controllable events with any degree. The concept of discrete event system controllability is thus extended by incorporating fuzziness. In this new sense, we present a necessary and sufficient condition for a fuzzy language to be controllable. We also study the supremal controllable fuzzy sublanguage and the infimal controllable fuzzy superlanguage when a given pre-specified desired fuzzy language is uncontrollable. Our framework generalizes that of Ramadge-Wonham and reduces to Ramadge-Wonham framework when membership grades in all fuzzy languages must be either 0 or 1. The theoretical development is accompanied by illustrative numerical examples.


title: The modulus in the CAD system drawings as a base of developing of the problem-oriented extensions

abstract: The concept of the "modulus" in the CAD system drawings is characterized, being a base of developing of the problem-oriented extensions. The modulus consists of visible geometric elements of the drawing and invisible parametric representation of the modelling object. The technological advantages of moduluss in a complex CAD system developing are described.


title: A Distributed TDMA Slot Assignment Algorithm for Wireless Sensor Networks

abstract: Wireless sensor networks benefit from communication protocols that reduce power requirements by avoiding frame collision. Time Division Media Access methods schedule transmission in slots to avoid collision, however these methods often lack scalability when implemented in \emph{ad hoc} networks subject to node failures and dynamic topology. This paper reports a distributed algorithm for TDMA slot assignment that is self-stabilizing to transient faults and dynamic topology change. The expected local convergence time is O(1) for any size network satisfying a constant bound on the size of a node neighborhood.


title: Prediction with Expert Advice by Following the Perturbed Leader for General Weights

abstract: When applying aggregating strategies to Prediction with Expert Advice, the learning rate must be adaptively tuned. The natural choice of sqrt(complexity/current loss) renders the analysis of Weighted Majority derivatives quite complicated. In particular, for arbitrary weights there have been no results proven so far. The analysis of the alternative "Follow the Perturbed Leader" (FPL) algorithm from Kalai (2003} (based on Hannan's algorithm) is easier. We derive loss bounds for adaptive learning rate and both finite expert classes with uniform weights and countable expert classes with arbitrary weights. For the former setup, our loss bounds match the best known results so far, while for the latter our results are (to our knowledge) new.


title: Corpus structure, language models, and ad hoc information retrieval

abstract: Most previous work on the recently developed language-modeling approach to information retrieval focuses on document-specific characteristics, and therefore does not take into account the structure of the surrounding corpus. We propose a novel algorithmic framework in which information provided by document-based language models is enhanced by the incorporation of information drawn from clusters of similar documents. Using this framework, we develop a suite of new algorithms. Even the simplest typically outperforms the standard language-modeling approach in precision and recall, and our new interpolation algorithm posts statistically significant improvements for both metrics over all three corpora tested.


title: Culture and International Usability Testing: The Effects of Culture in Structured Interviews

abstract: The global audience for software products includes members of different countries, religions, and cultures: people who speak different languages, have different life styles, and have different perceptions and expectations of any given product. A major impediment in interface development is that there is inadequate empirical evidence for the effects of culture in the usability engineering methods used for developing user interfaces. This paper presents a controlled study investigating the effects of culture on the effectiveness of structured interviews in usability testing. The experiment consisted of usability testing of a website with two independent groups of Indian participants by two interviewers; one belonging to the Indian culture and the other to the Anglo-American culture. Participants found more usability problems and made more suggestions to an interviewer who was a member of the same (Indian) culture than to the foreign (Anglo-American) interviewer. The results of the study empirically establish that culture significantly affects the efficacy of structured interviews during international user testing. The implications of this work for usability engineering are discussed.


title: Soft Computing Models for Network Intrusion Detection Systems

abstract: Security of computers and the networks that connect them is increasingly becoming of great significance. Computer security is defined as the protection of computing systems against threats to confidentiality, integrity, and availability. There are two types of intruders: external intruders, who are unauthorized users of the machines they attack, and internal intruders, who have permission to access the system with some restrictions. This chapter presents a soft computing approach to detect intrusions in a network. Among the several soft computing paradigms, we investigated fuzzy rule-based classifiers, decision trees, support vector machines, linear genetic programming and an ensemble method to model fast and efficient intrusion detection systems. Empirical results clearly show that soft computing approach could play a major role for intrusion detection.


title: Modular technology of developing of the problem-oriented extensions of a CAD system of reconstruction of the plant

abstract: The modular technology of creation of the problem-oriented extensions of a CAD system is described, which was realised in a system TechnoCAD GlassX for designing of reconstruction of the plants. The modularity of the technology is expressed in storage of all parameters of the design in one element of the drawing - modulus, with automatic generation of a geometrical part of the modulus from these parameters. The common principles of the system organization of extensions developing are described: separation of the part of the design to automize in this extension, architecture of parameters in the form of the lists of objects with their properties and links to another objects, separation of common and special operations, stages of the developing, boundaries of applicability of technology.


title: Interactive visualization of higher dimensional data in a multiview environment

abstract: We develop multiple view visualization of higher dimensional data. Our work was chiefly motivated by the need to extract insight from four dimensional Quantum Chromodynamic (QCD) data. We develop visualization where multiple views, generally views of 3D projections or slices of a higher dimensional data, are tightly coupled not only by their specific order but also by a view synchronizing interaction style, and an internally defined interaction language. The tight coupling of the different views allows a fast and well-coordinated exploration of the data. In particular, the visualization allowed us to easily make consistency checks of the 4D QCD data and to infer the correctness of particle properties calculations. The software developed was also successfully applied in material studies, in particular studies of meteorite properties. Our implementation uses the VTK API. To handle a large number of views (slices/projections) and to still maintain good resolution, we use IBM T221 display (3840 X 2400 pixels).


title: Export Behaviour Modeling Using EvoNF Approach

abstract: The academic literature suggests that the extent of exporting by multinational corporation subsidiaries (MCS) depends on their product manufactured, resources, tax protection, customers and markets, involvement strategy, financial independence and suppliers' relationship with a multinational corporation (MNC). The aim of this paper is to model the complex export pattern behaviour using a Takagi-Sugeno fuzzy inference system in order to determine the actual volume of MCS export output (sales exported). The proposed fuzzy inference system is optimised by using neural network learning and evolutionary computation. Empirical results clearly show that the proposed approach could model the export behaviour reasonable well compared to a direct neural network approach.


title: Traffic Accident Analysis Using Decision Trees and Neural Networks

abstract: The costs of fatalities and injuries due to traffic accident have a great impact on society. This paper presents our research to model the severity of injury resulting from traffic accidents using artificial neural networks and decision trees. We have applied them to an actual data set obtained from the National Automotive Sampling System (NASS) General Estimates System (GES). Experiment results reveal that in all the cases the decision tree outperforms the neural network. Our research analysis also shows that the three most important factors in fatal injury are: driver's seat belt usage, light condition of the roadway, and driver's alcohol usage.


title: Short Term Load Forecasting Models in Czech Republic Using Soft Computing Paradigms

abstract: This paper presents a comparative study of six soft computing models namely multilayer perceptron networks, Elman recurrent neural network, radial basis function network, Hopfield model, fuzzy inference system and hybrid fuzzy neural network for the hourly electricity demand forecast of Czech Republic. The soft computing models were trained and tested using the actual hourly load data for seven years. A comparison of the proposed techniques is presented for predicting 2 day ahead demands for electricity. Simulation results indicate that hybrid fuzzy neural network and radial basis function networks are the best candidates for the analysis and forecasting of electricity demand.


title: Decision Support Systems Using Intelligent Paradigms

abstract: Decision-making is a process of choosing among alternative courses of action for solving complicated problems where multi-criteria objectives are involved. The past few years have witnessed a growing recognition of Soft Computing (SC) technologies that underlie the conception, design and utilization of intelligent systems. In this paper, we present different SC paradigms involving an artificial neural network trained using the scaled conjugate gradient algorithm, two different fuzzy inference methods optimised using neural network learning/evolutionary algorithms and regression trees for developing intelligent decision support systems. We demonstrate the efficiency of the different algorithms by developing a decision support system for a Tactical Air Combat Environment (TACE). Some empirical comparisons between the different algorithms are also provided.


title: Synchronous Relaxation for Parallel Ising Spin Simulations

abstract: A new parallel algorithm for simulating Ising spin systems is presented. The sequential prototype is the n-fold way algorithm cite{BKL75}, which is efficient but is hard to parallelize using conservative methods. Our parallel algorithm is optimistic. Unlike other optimistic algorithms, e.g., Time Warp, our algorithm is synchronous. It also belongs to the class of simulations known as ``relaxation'' cite{CS8 hence it is named ``synchronous relaxation.'' We derive performance guarantees for this algorithm. If N is the number of PEs, then under weak assumptions we show that the number of correct events processed per unit of time is, on average, at least of order N/log(N). All communication delays, processing time, and busy waits are taken into account.

categories: cs.DC cond-mat.mtrl-sci cs.DS physics.comp-ph


title: The model of the tables in design documentation for operating with the electronic catalogs and for specifications making in a CAD system

abstract: The hierarchic block model of the tables in design documentation as a part of a CAD system is described, intended for automatic specifications making of elements of the drawings, with usage of the electronic catalogs. The model is created for needs of a CAD system of reconstruction of the industrial plants, where the result of designing are the drawings, which include the specifications of different types. The adequate simulation of the specification tables is ensured with technology of storing in the drawing of the visible geometric elements and invisible parametric representation, sufficient for generation of this elements.


title: Modular technology of developing of the extensions of a CAD system. Axonometric piping diagrams. Parametric representation

abstract: Applying the modular technology of developing of the problem-oriented extensions of a CAD system to a problem of automation of creating of the axonometric piping diagrams on an example of the program system TechnoCAD GlassX is described. The proximity of composition of the schemas is detected for special technological pipe lines, systems of a water line and water drain, heating, heat supply, ventilating, air conditioning. The structured parametric representation of the schemas, including properties of objects, their link, common settings, settings by default and the special links of compatibility is reviewed.


title: Modular technology of developing of the extensions of a CAD system. The axonometric piping diagrams. Common and special operations

abstract: Applying the modular technology of developing of the problem-oriented extensions of a CAD system to a problem of automation of creating of the axonometric piping diagrams on an example of the program system TechnoCAD GlassX is described. The features of realization of common operations, composition and realization of special operations of a designing of the schemas of the special technological pipe lines, systems of a water line and water drain, heating, heat supply, ventilating, air conditioning are reviewed.


title: Mathematical and programming toolkit of the computer aided design of the axonometric piping diagrams

abstract: The problem of the automation of the designing of the axonometric piping diagrams include, as the minimum, manipulations with the flat schemas of three-dimensional wireframe objects (with dimension of 2,5). The specialized model, methodical and mathematical approaches are required because of large bulk of calculuss. Coordinate systems, data types, common principles of realization of operation with data and composition of the basic operations are described which are realised in the complex CAD system of the reconstruction of the plants TechnoCAD GlassX.


title: Neighborhood-Based Topology Recognition in Sensor Networks

abstract: We consider a crucial aspect of self-organization of a sensor network consisting of a large set of simple sensor nodes with no location hardware and only very limited communication range. After having been distributed randomly in a given two-dimensional region, the nodes are required to develop a sense for the environment, based on a limited amount of local communication. We describe algorithmic approaches for determining the structure of boundary nodes of the region, and the topology of the region. We also develop methods for determining the outside boundary, the distance to the closest boundary for each point, the Voronoi diagram of the different boundaries, and the geometric thickness of the network. Our methods rely on a number of natural assumptions that are present in densely distributed sets of nodes, and make use of a combination of stochastics, topology, and geometry. Evaluation requires only a limited number of simple local computations.


title: Erratum : MCColor is not optimal on Meyniel graphs

abstract: A Meyniel graph is a graph in which every odd cycle of length at least five has two chords. In the manuscript "Coloring Meyniel graphs in linear time" we claimed that our algorithm MCColor produces an optimal coloring for every Meyniel graph. But later we found a mistake in the proof and a couterexample to the optimality, which we present here. MCColor can still be used to find a stable set that intersects all maximal cliques of a Meyniel graph in linear time. Consequently it can be used to find an optimal coloring in time O(nm), and the same holds for Algorithm MCS+Color. This is explained in the manuscript "A linear algorithm to find a strong stable set in a Meyniel graph" but this is equivalent to Hertz's algorithm. The current best algorithm for coloring Meyniel graphs is the O(n^2) algorithm LexColor due to Roussel and Rusu. The question of finding a linear-time algorithm to color Meyniel graphs is still open.


title: An unexpected application of minimization theory to module decompositions

abstract: The aim of this work is to show how we can decompose a module (if decomposable) into an indecomposable module with the help of the minimization process.


title: Jigsaw-based Security in Data Transfer in Computer Networks

abstract: In this paper, we present a novel encryption-less algorithm to enhance security in transmission of data in networks. The algorithm uses an intuitively simple idea of a 'jigsaw puzzle' to break the transformed data into multiple parts where these parts form the pieces of the puzzle. Then these parts are packaged into packets and sent to the receiver. A secure and efficient mechanism is provided to convey the information that is necessary for obtaining the original data at the receiver-end from its parts in the packets, that is, for solving the 'jigsaw puzzle'. The algorithm is designed to provide information-theoretic (that is, unconditional) security by the use of a one-time pad like scheme so that no intermediate or unintended node can obtain the entire data. An authentication code is also used to ensure authenticity of every packet.


title: Efficiency Enhancement of Probabilistic Model Building Genetic Algorithms

abstract: This paper presents two different efficiency-enhancement techniques for probabilistic model building genetic algorithms. The first technique proposes the use of a mutation operator which performs local search in the sub-solution neighborhood identified through the probabilistic model. The second technique proposes building and using an internal probabilistic model of the fitness along with the probabilistic model of variable interactions. The fitness values of some offspring are estimated using the probabilistic model, thereby avoiding computationally expensive function evaluations. The scalability of the aforementioned techniques are analyzed using facetwise models for convergence time and population sizing. The speed-up obtained by each of the methods is predicted and verified with empirical results. The results show that for additively separable problems the competent mutation operator requires O(k 0.5 logm)--where k is the building-block size, and m is the number of building blocks--less function evaluations than its selectorecombinative counterpart. The results also show that the use of an internal probabilistic fitness model reduces the required number of function evaluations to as low as 1-10% and yields a speed-up of 2--50.


title: Let's Get Ready to Rumble: Crossover Versus Mutation Head to Head

abstract: This paper analyzes the relative advantages between crossover and mutation on a class of deterministic and stochastic additively separable problems. This study assumes that the recombination and mutation operators have the knowledge of the building blocks (BBs) and effectively exchange or search among competing BBs. Facetwise models of convergence time and population sizing have been used to determine the scalability of each algorithm. The analysis shows that for additively separable deterministic problems, the BB-wise mutation is more efficient than crossover, while the crossover outperforms the mutation on additively separable problems perturbed with additive Gaussian noise. The results show that the speed-up of using BB-wise mutation on deterministic problems is O(k^{0.5}logm), where k is the BB size, and m is the number of BBs. Likewise, the speed-up of using crossover on stochastic problems with fixed noise variance is O(mk^{0.5}log m).


title: Designing Competent Mutation Operators via Probabilistic Model Building of Neighborhoods

abstract: This paper presents a competent selectomutative genetic algorithm (GA), that adapts linkage and solves hard problems quickly, reliably, and accurately. A probabilistic model building process is used to automatically identify key building blocks (BBs) of the search problem. The mutation operator uses the probabilistic model of linkage groups to find the best among competing building blocks. The competent selectomutative GA successfully solves additively separable problems of bounded difficulty, requiring only subquadratic number of function evaluations. The results show that for additively separable problems the probabilistic model building BB-wise mutation scales as O(2^km^{1.5}), and requires O(k^{0.5}logm) less function evaluations than its selectorecombinative counterpart, confirming theoretical results reported elsewhere (Sastry & Goldberg, 2004).


title: Efficiency Enhancement of Genetic Algorithms via Building-Block-Wise Fitness Estimation

abstract: This paper studies fitness inheritance as an efficiency enhancement technique for a class of competent genetic algorithms called estimation distribution algorithms. Probabilistic models of important sub-solutions are developed to estimate the fitness of a proportion of individuals in the population, thereby avoiding computationally expensive function evaluations. The effect of fitness inheritance on the convergence time and population sizing are modeled and the speed-up obtained through inheritance is predicted. The results show that a fitness-inheritance mechanism which utilizes information on building-block fitnesses provides significant efficiency enhancement. For additively separable problems, fitness inheritance reduces the number of function evaluations to about half and yields a speed-up of about 1.75--2.25.


title: A Logic for Reasoning about Digital Rights

abstract: We present a logic for reasoning about licenses, which are ``terms of use'' for digital resources. The logic provides a language for writing both properties of licenses and specifications that govern a client's actions. We discuss the complexity of checking properties and specifications written in our logic and propose a technique for verification. A key feature of our approach is that it is essentially parameterized by the language in which the licenses are written, provided that this language can be given a trace-based semantics. We consider two license languages to illustrate this flexibility.


title: Note on Counting Eulerian Circuits

abstract: We show that the problem of counting the number of Eulerian circuits in an undirected graph is complete for the class #P.


title: Observability and Decentralized Control of Fuzzy Discrete Event Systems

abstract: Fuzzy discrete event systems as a generalization of (crisp) discrete event systems have been introduced in order that it is possible to effectively represent uncertainty, imprecision, and vagueness arising from the dynamic of systems. A fuzzy discrete event system has been modelled by a fuzzy automaton; its behavior is described in terms of the fuzzy language generated by the automaton. In this paper, we are concerned with the supervisory control problem for fuzzy discrete event systems with partial observation. Observability, normality, and co-observability of crisp languages are extended to fuzzy languages. It is shown that the observability, together with controllability, of the desired fuzzy language is a necessary and sufficient condition for the existence of a partially observable fuzzy supervisor. When a decentralized solution is desired, it is proved that there exist local fuzzy supervisors if and only if the fuzzy language to be synthesized is controllable and co-observable. Moreover, the infimal controllable and observable fuzzy superlanguage, and the supremal controllable and normal fuzzy sublanguage are also discussed. Simple examples are provided to illustrate the theoretical development.


title: Mining Frequent Itemsets from Secondary Memory

abstract: Mining frequent itemsets is at the core of mining association rules, and is by now quite well understood algorithmically. However, most algorithms for mining frequent itemsets assume that the main memory is large enough for the data structures used in the mining, and very few efficient algorithms deal with the case when the database is very large or the minimum support is very low. Mining frequent itemsets from a very large database poses new challenges, as astronomical amounts of raw data is ubiquitously being recorded in commerce, science and government. In this paper, we discuss approaches to mining frequent itemsets when data structures are too large to fit in main memory. Several divide-and-conquer algorithms are given for mining from disks. Many novel techniques are introduced. Experimental results show that the techniques reduce the required disk accesses by orders of magnitude, and enable truly scalable data mining.


title: Traffic-driven model of the World Wide Web graph

abstract: We propose a model for the World Wide Web graph that couples the topological growth with the traffic's dynamical evolution. The model is based on a simple traffic-driven dynamics and generates weighted directed graphs exhibiting the statistical properties observed in the Web. In particular, the model yields a non-trivial time evolution of vertices and heavy-tail distributions for the topological and traffic properties. The generated graphs exhibit a complex architecture with a hierarchy of cohesiveness levels similar to those observed in the analysis of real data.


title: Regression with respect to sensing actions and partial states

abstract: In this paper, we present a state-based regression function for planning domains where an agent does not have complete information and may have sensing actions. We consider binary domains and employ the 0-approximation [Son & Baral 2001] to define the regression function. In binary domains, the use of 0-approximation means using 3-valued states. Although planning using this approach is incomplete with respect to the full semantics, we adopt it to have a lower complexity. We prove the soundness and completeness of our regression formulation with respect to the definition of progression. More specifically, we show that (i) a plan obtained through regression for a planning problem is indeed a progression solution of that planning problem, and that (ii) for each plan found through progression, using regression one obtains that plan or an equivalent one. We then develop a conditional planner that utilizes our regression function. We prove the soundness and completeness of our planning algorithm and present experimental results with respect to several well known planning problems in the literature.


title: Grid Databases for Shared Image Analysis in the MammoGrid Project

abstract: The MammoGrid project aims to prove that Grid infrastructures can be used for collaborative clinical analysis of database-resident but geographically distributed medical images. This requires: a) the provision of a clinician-facing front-end workstation and b) the ability to service real-world clinician queries across a distributed and federated database. The MammoGrid project will prove the viability of the Grid by harnessing its power to enable radiologists from geographically dispersed hospitals to share standardized mammograms, to compare diagnoses (with and without computer aided detection of tumours) and to perform sophisticated epidemiological studies across national boundaries. This paper outlines the approach taken in MammoGrid to seamlessly connect radiologist workstations across a Grid using an "information infrastructure" and a DICOM-compliant object model residing in multiple distributed data stores in Italy and the UK


title: Advanced exploitation of buffer overflow

abstract: This article describes in depth several ways of exploiting buffer overflows in the UNIX operating systems.


title: MammoGrid: A Service Oriented Architecture based Medical Grid Application

abstract: The MammoGrid project has recently delivered its first proof-of-concept prototype using a Service-Oriented Architecture (SOA)-based Grid application to enable distributed computing spanning national borders. The underlying AliEn Grid infrastructure has been selected because of its practicality and because of its emergence as a potential open source standards-based solution for managing and coordinating distributed resources. The resultant prototype is expected to harness the use of huge amounts of medical image data to perform epidemiological studies, advanced image processing, radiographic education and ultimately, tele-diagnosis over communities of medical virtual organisations. The MammoGrid prototype comprises a high-quality clinician visualization workstation used for data acquisition and inspection, a DICOM-compliant interface to a set of medical services (annotation, security, image analysis, data storage and querying services) residing on a so-called Grid-box and secure access to a network of other Grid-boxes connected through Grid middleware. This paper outlines the MammoGrid approach in managing a federation of Grid-connected mammography databases in the context of the recently delivered prototype and will also describe the next phase of prototyping.


title: Reduction Strategies in Lambda Term Normalization and their Effects on Heap Usage

abstract: Higher-order representations of objects such as programs, proofs, formulas and types have become important to many symbolic computation tasks. Systems that support such representations usually depend on the implementation of an intensional view of the terms of some variant of the typed lambda-calculus. Various notations have been proposed for lambda-terms to explicitly treat substitutions as basis for realizing such implementations. There are, however, several choices in the actual reduction strategies. The most common strategy utilizes such notations only implicitly via an incremental use of environments. This approach does not allow the smaller substitution steps to be intermingled with other operations of interest on lambda-terms. However, a naive strategy explicitly using such notations can also be costly: each use of the substitution propagation rules causes the creation of a new structure on the heap that is often discarded in the immediately following step. There is thus a tradeoff between these two approaches. This thesis describes the actual realization of the two approaches, discusses their tradeoffs based on this and, finally, offers an amalgamated approach that utilizes recursion in rewrite rule application but also suspends substitution operations where necessary.


title: An Abductive Framework For Computing Knowledge Base Updates

abstract: This paper introduces an abductive framework for updating knowledge bases represented by extended disjunctive programs. We first provide a simple transformation from abductive programs to update programs which are logic programs specifying changes on abductive hypotheses. Then, extended abduction, which was introduced by the same authors as a generalization of traditional abduction, is computed by the answer sets of update programs. Next, different types of updates, view updates and theory updates are characterized by abductive programs and computed by update programs. The task of consistency restoration is also realized as special cases of these updates. Each update problem is comparatively assessed from the computational complexity viewpoint. The result of this paper provides a uniform framework for different types of knowledge base updates, and each update is computed using existing procedures of logic programming.


title: Fast Simulation of Multicomponent Dynamic Systems

abstract: A computer simulation has to be fast to be helpful, if it is employed to study the behavior of a multicomponent dynamic system. This paper discusses modeling concepts and algorithmic techniques useful for creating such fast simulations. Concrete examples of simulations that range from econometric modeling to communications to material science are used to illustrate these techniques and concepts. The algorithmic and modeling methods discussed include event-driven processing, ``anticipating'' data structures, and ``lazy'' evaluation, Poisson dispenser, parallel processing by cautious advancements and by synchronous relaxations. The paper gives examples of how these techniques and models are employed in assessing efficiency of capacity management methods in wireless and wired networks, in studies of magnetization, crystalline structure, and sediment formation in material science, in studies of competition in economics.