ALBERT

Description: Dynamically typed languages are becoming increasingly popular for different software development scenarios such as Web engineering, rapid prototyping or the construction of applications that require runtime adaptiveness. In contrast, statically typed languages have undeniable advantages such as early type error detection and more opportunities for compiler optimizations. Since both approaches offer different benefits, hybrid statically and dynamically typed programming languages have emerged, and some statically typed languages have also incorporated dynamic typing capabilities. In this paper, we present the minimal core of StaDyn , a hybrid typing language that performs static type inference of both statically and dynamically typed references. The type information gathered by the compiler is used to generate efficient .NET code, obtaining a significant runtime performance improvement compared with C# 4.0 and Visual Basic 10.

Description: Readahead is an important technique to deal with the huge gap between disk drives and applications. It has become a standard in modern operating systems and advanced storage systems. However, it is difficult to develop the common kernel readahead and to achieve full testing coverage of all cases. In this paper, we formulate the kernel read handling, caching and readahead behavior as an absorbing Markov decision process, and present performance evaluations to compare or verify various readaheads. We also introduce algorithms to find optimal prefetching policies for specific read pattern and present the convergence analysis. By exploiting sample-path-based methods, it becomes much easier to evaluate and optimize prefetching policies, which can provide valuable informations to help the design and improvement of practical readaheads. For illustration and verification, we present two examples and some experiments on the readaheads in Linux kernel. The results show that the model-based evaluations agree with the practice and the improved prefetching policy significantly outperforms the original one in Linux kernel for the specified workloads.

Description: Crowds must be simulated believable in terms of their appearance and behavior to improve a virtual environment's realism. Due to the complex nature of human behavior, realistic behavior of agents in crowd simulations is still a challenging problem. In this paper, we propose a novel behavioral model which builds analytical maps to control agents’ behavior adaptively with agent–crowd interaction formulations. We introduce information theoretical concepts to construct analytical maps automatically. Our model can be integrated into crowd simulators and enhance their behavioral complexity. We made comparative analyses of the presented behavior model with measured crowd data and two agent-based crowd simulators.

Description: Inspired by the swarm behaviours of social insects, research into the self-assembly of swarm robots has become an attractive issue in the robotic community. Unfortunately, there are very few platforms for self-assembly and locomotion in the field of swarm robotics. The Sambot is a novel self-assembling modular robot that shares characteristics with swarm robots and self-reconfigurable robots. Each Sambot can move autonomously and connect with the other. This paper discusses the concept of combining self-assembly and locomotion for swarm robots. Distributed control algorithms for self-assembly and locomotion are proposed. Using five physical Sambots, experiments were carried out on autonomous docking, self-assembly and locomotion. Our control algorithm for self-assembly can also be used to realize the autonomous construction and self-repair of robotic structures consisting of a large number of Sambots.

Description: Scanning of ports on a computer occurs frequently on the Internet. An attacker performs port scans of Internet protocol addresses to find vulnerable hosts to compromise. However, it is also useful for system administrators and other network defenders to detect port scans as possible preliminaries to more serious attacks. It is a very difficult task to recognize instances of malicious port scanning. In general, a port scan may be an instance of a scan by attackers or an instance of a scan by network defenders. In this survey, we present research and development trends in this area. Our presentation includes a discussion of common port scan attacks. We provide a comparison of port scan methods based on type, mode of detection, mechanism used for detection and other characteristics. This survey also reports on the available data sets and evaluation criteria for port scan detection approaches.

Description: Proxy blind signature is an important cryptographic primitive and plays an essential role in construction of the electronic cash (e-cash). Recently, Tan (2001, An offline electronic cash scheme based on proxy blind signature. Comput. J. , 54, 505–512) proposed a new proxy blind signature scheme and applied it to electronic cash. The scheme was claimed as being provably secure under the Discrete Log assumption, DBDH assumption and Chosen–Target CDH assumption in the random oracle model. In this paper, we show that Tan's proxy blind signature scheme is insecure by demonstrating several attacks in which a malicious original signer can forge both valid proxy signature keys of arbitrary proxy signers and a proxy blind signature on an arbitrary message with respect to any proxy signer directly. We also discuss some weaknesses in the e-cash scheme proposed by Tan.

Description: In recent times, there has been increasing interest in storing data securely in the cloud environment. To provide owners of data stored in the cloud with flexible control over access to their data by other users, we propose a role-based encryption (RBE) scheme for secure cloud storage. Our scheme allows the owner of data to store it in an encrypted form in the cloud and to grant access to that data for users with specific roles. The scheme specifies a set of roles to which the users are assigned, with each role having a set of permissions. The data owner can encrypt the data and store it in the cloud in such a way that only users with specific roles can decrypt the data. Anyone else, including the cloud providers themselves, will not be able to decrypt the data. We describe such an RBE scheme using a broadcast encryption algorithm. The paper describes the security analysis of the proposed scheme and gives proofs showing that the proposed scheme is secure against attacks. We also analyse the efficiency and performance of our scheme and show that it has superior characteristics compared with other previously published schemes.

Description: Although the objective of secure communication can be achieved by using cryptographic tools, the undeniability that results from cryptographic properties may create a potential threat to the sender of the message. Unfortunately, most existing deniable protocols only provide 1-out-of-2 deniability. When both parties (the sender and the receiver) are allowed to deny generating the message, a dispute might occur between these two parties. The 1-out-of-2 deniable protocol can result in an unfair resolution of the dispute. Therefore, we propose a new model of deniability, called 1-out-of- deniability, that can provide full deniability. The 1-out-of- deniability protocol allows the originator of the message to deny that he or she generated the message, since there are an infinite number of possible message generators; at the same time, all transmitted messages can be protected and authenticated between the sender and the intended receiver. Our design can be implemented by using any public-key cryptography technique. We also analyze the correctness of the proposed protocols based on logical rules, and two practical examples are given to illustrate our design.

Description: Each year, large amounts of money and labor are spent on patching the vulnerabilities in operating systems and various popular software to prevent exploitation by worms. Modeling the propagation process can help us to devise effective strategies against those worms’ spreading. This paper presents a microcosmic analysis of worm propagation procedures. Our proposed model is different from traditional methods and examines deep inside the propagation procedure among nodes in the network by concentrating on the propagation probability and time delay described by a complex matrix. Moreover, since the analysis gives a microcosmic insight into a worm's propagation, the proposed model can avoid errors that are usually concealed in the traditional macroscopic analytical models. The objectives of this paper are to address three practical aspects of preventing worm propagation: (i) where do we patch? (ii) how many nodes do we need to patch? (iii) when do we patch? We implement a series of experiments to evaluate the effects of each major component in our microcosmic model. Based on the results drawn from the experiments, for high-risk vulnerabilities, it is critical that networks reduce the number of vulnerable nodes to below 80%. We believe our microcosmic model can benefit the security industry by allowing them to save significant money in the deployment of their security patching schemes.

Description: Although analyzing complex systems could be a complicated process, current approaches to quantify system security or vulnerability usually consider the whole system as a single component. In this paper, we propose a new compositional method to evaluate the vulnerability measure of complex systems. By the word composition we mean that the vulnerability measure of a complex system can be computed using pre-calculated vulnerability measures of its components. We define compatible systems to demonstrate which components could combine. Moreover, choice, sequential, parallel and synchronized parallel composition methods are defined and the measurement of the vulnerability in each case is presented. Our method uses a state machine to model the system. The model considers unauthorized states and attacker capabilities. Furthermore, both the probability of attack and delay time to reach the target state are used to quantify vulnerability. The proposed approach would be useful to analyze complex systems which may have complicated models. This approach reduces the state space and complexity of computation. On the other hand, if a component is replaced by another one, the vulnerability measures of other components do not change. Thus, these quantities are reused in new computation. Therefore, the calculation of the vulnerability measure for a new system is simplified.

Description: The construction of gene regulatory networks from expression data is one of the most important issues in systems biology research. However, building such networks is a tedious task, especially when both the number of genes and the complexity of gene regulation increase. In this work, we adopt the S-system model to represent the gene network and establish a methodology to infer the model. Our work mainly includes an adaptive genetic algorithm-particle swarm optimization hybrid method to infer appropriate network parameters, and a gene clustering method to decompose a large network into several smaller networks for dimension reduction. To validate the proposed methods, different series of experiments have been conducted and the results show that the proposed methods can be used to infer S-system models of gene networks efficiently and successfully.

Description: We present a content-based image retrieval system for plant image retrieval, intended especially for the house plant identification problem. A plant image consists of a collection of overlapping leaves and possibly flowers, which makes the problem challenging. We studied the suitability of various well-known color, shape and texture features for this problem, as well as introducing some new texture matching techniques and shape features. Feature extraction is applied after segmenting the plant region from the background using the max-flow min-cut technique. Results on a database of 380 plant images belonging to 78 different types of plants show promise of the proposed new techniques and the overall system: in 55% of the queries, the correct plant image is retrieved among the top-15 results. Furthermore, the accuracy goes up to 73% when a 132-image subset of well-segmented plant images are considered.

Description: We investigate the assignment of assets to tasks where each asset can potentially execute any of the tasks, but assets execute tasks with a probabilistic outcome of success. There is a cost associated with each possible assignment of an asset to a task, and if a task is not executed there is also a cost associated with the non-execution of the task. As we proposed in [Gelenbe, E., Timotheou, S., and Nicholson, D. (2010). Fast distributed near optimum assignment of assets to tasks. Comput. J., doi:10.1093/comjnl/bxq010], we formulate the allocation of assets to tasks in order to minimize the overall expected cost, as a nonlinear combinatorial optimization problem. We propose the use of network flow algorithms which are based on solving a sequence of minimum cost flow problems on appropriately constructed networks with estimated arc costs. We introduce three different schemes for the estimation of the arc costs and we investigate their performance compared with a random neural network algorithm and a greedy algorithm. We also develop an approach for obtaining tight lower bounds to the optimal solution based on a piecewise linear approximation of the considered problem.

Description: Building trust is a major concern in Peer-to-Peer networks as several kinds of applications rely on the presence of trusted services. Traditional techniques do not scale, produce very high overheads or rely on unrealistic assumptions. In this paper, we propose a new membership algorithm (Community Of Reputable PeerS, CORPS) for Distributed Hash Tables which builds a community of reputable nodes and thus enables the implementation of pseudo-trusted services. CORPS uses a reputation-based approach to decide whether a node can be a member of the group or not. We demonstrate the benefits of this approach and evaluate how much it improves the reliability of a trusted routing service.

Description: Many data sets exhibit skewed class distributions in which most cases are allocated to a class and far fewer cases to a smaller one. A classifier induced from an imbalanced data set has usually a low error rate for the majority class and an unacceptable error rate for the minority class. This paper provides a review on various methodologies that have tried to handle this problem. Afterwards, it presents an experimental study of these methodologies with a proposed cascade generalization ensemble that is applied in reweighted data and it concludes that such a framework can be a more effective solution to the problem. Our method improves the identification of a difficult small class, while keeping the classification ability of the other class in an acceptable level.

Description: Ants are generally believed to follow an intensive work routine. Numerous tales and fables refer to ants as conscientious workers. Nevertheless, biologists have discovered that ants also rest for extended periods of time. This does not only hold for individual ants. Interestingly, ant colonies exhibit synchronized activity phases that result from self-organization. In this work, self-synchronization in ant colonies is taken as the inspiring source for a new mechanism of self-synchronized duty-cycling in mobile sensor networks. Hereby, we assume that sensor nodes are equipped with energy harvesting capabilities such as, for example, solar cells. We show that the proposed self-synchronization mechanism can be made adaptive depending on variable energy resources. The main objective of this paper is to study and explore the swarm intelligence foundations of self-synchronized duty-cycling. With this purpose in mind, physical constraints such as packet collisions and packet loss are generally not considered.

Description: Vector field tomography is a field that has received considerable attention in recent decades. It deals with the problem of the determination of a vector field from non-invasive integral data. These data are modelled by the vectorial Radon transform. Previous attempts at solving this reconstruction problem showed that tomographic data alone are insufficient for determining a 2D band-limited vector field completely and uniquely. This paper describes a method that allows one to recover both components of a 2D vector field based only on integral data, by solving a system of linear equations. We carry out the analysis in the digital domain and we take advantage of the redundancy in the projection data, since these may be viewed as weighted sums of the local vector field's Cartesian components. The potential of the introduced method is demonstrated by presenting examples of vector field reconstruction.

Description: Historically, at the beginning of natural language processing, applications with industrial objectives were preferred, e.g. for a fully automated translation. Soon, during the 1960s, there were attempts to separate applications from basic theoretical research. Since this theoretical research encounters difficulties regarding its status as a separate discipline, and considering the constraints necessary to clarify the concept of ‘good application’, impossible to satisfy simultaneously (a real problem to solve, in response to a social demand, and a viable solution in terms of reliability, robustness, speed and cost), two main streams have emerged. The first one, as a computer technique, is intended to build applications based on a strict logic, using natural language to facilitate interaction with the computer, but not directly related to the human way of using language (this approach is designated as natural language processing ). Such pragmatic research accepts certain kinds of errors, but must lead to concrete results in limited time. The goal is to provide effective systems for real applications, able to respond effectively to requests addressed to them in fairly large areas; these systems are directly related to social and industrial productivity, which is the essential criterion of evaluation. Some technological developments, such as microcomputers, have made available to people specific applications of natural language processing and have enabled the emergence of small specialized firms. This produced, in the second half of the 1980s, the emergence of a ‘language industry’ and of the field of ‘linguistic engineering’. On the other hand, during the late 1960s, the gap between the social demand, the resources invested and the poor performance obtained led to the emergence of theoretical studies intended to formalize languages (as opposed to the more empirical machine translation). This leads to ‘pilot systems’, aimed at demonstrating the feasibility of complex theoretical approaches, but unable to operate outside a set of rather limited examples. The limits may be at different levels: more or less limited vocabulary or accepted sentences, knowledge about the field more or less complete, more or less developed reasoning and so on. These limits have a significant impact on communication itself. For natural language processing systems to be effective, they must make appropriate inferences from what is said and, conversely their behavior should allow the inferences that the users usually do when using their language. Thus, this position paper stresses that understanding the surface meaning of a natural language is not sufficient but that the goals, intentions and strategies of the participants in a dialogue must be understood.

Description: The main ‘philosophical’ outcome of this article is to demonstrate that the structural description of residuated lattices requires the use of the co-residuated setting. A construction, called skew symmetrization, which generalizes the well-known representation of an ordered Abelian group obtained from the positive (or negative) cone of the algebra is introduced here. Its definition requires leaving the accustomed residuated setting and entering the co-residuated setting. It is shown that every uninorm on [0, 1] with an involution defined by the residual complement with respect to the unit and having the unit as the fixed point of the involution can be described as the skew symmetrization of its underlying t-norm or underlying t-conorm.

Description: This article deals with some probabilistic model theory for intuitionistic predicate logic. We introduce the notions of intuitionistic probability, probabilistic structure for intuitionistic predicate logic and model of an intuitionistic probability. We prove a Gaifman-style completeness theorem: any intuitionistic probability has a weak probabilistic model.

Description: We introduce a new approach to conditional probability over many-valued events, which is based on bets. Then we show that this approach fits with Kroupa's approach, and we give two characterizations of coherence for books on conditional many-valued events, the first one based on states, and the second one based on logical coherence of a suitable theory on many-valued logic.

Description: We solve the minimization problem for finitely axiomatizable theories in Gödel infinite-valued propositional logic. That is, we obtain an algorithm that when input a formula α( X 1 ,..., X n ) outputs a formula β( X 1 ,..., X m ) such that (i) the theories singly axiomatized by {α} and {β} have isomorphic algebraic semantics, and (ii) if β'( X 1 ,..., X m ' ) is any formula satisfying (i), then m '≥ m .

Description: Ubiquitous smart environments equipped with low-cost and easily-deployable wireless sensor networks (WSNs) and ever-increasing widespread Mobile Ad hoc NETworks (MANETs) are opening brand new opportunities in environmental monitoring. This paper proposes an original solution for WSN/MANET integration based on the primary design guideline of opportunistically exploiting MANET overlays impromptu formed over the WSN to improve and boost the data collection task of a typical WSN. On the one hand, we adopt a cross-layer approach that exploits MANET connections to differentiate and fasten the delivery of sensed urgent data by pushing them over low-latency MANET paths. On the other hand, we take advantage of local cross-layer visibility of the WSN data collection procedures and protocols to carefully control and limit WSN–MANET coordination overhead. We claim that our proposed solution can obtain significant quality of service improvements via differentiation, by granting faster delivery times to urgent data with a very limited cost in most common execution scenarios.

Description: The Capsule Reviews are intended to provide a short succinct review of each paper in the issue in order to bring it to a wider readership. The Capsule Reviews were compiled by Fairouz Kamareddine. Professor Kamareddine is an Associate Editor of The Computer Journal and is based in the Department of Mathematical and Computer Sciences at Heriot-Watt University, Edinburgh, UK.

Description: Cache sharing has been a popular technique used to facilitate data access in mobile network environments. The key to this technique is to allow an efficient sharing of cache contents between neighboring nodes without introducing excessive amount of communication overhead. In this paper, we propose a cache-sharing protocol, called ‘Pull with Piggybacked Push (PPP)’, which exploits data request broadcasts by performing data pull and index push operations together. Taking advantage of both push- and pull-based approaches, PPP gains benefits from both ends: performance and communication overhead. PPP is unique in that it yields good performance over diverse operating environments, while accomplishing it with lower communication overhead than the previous methods. In addition, it adapts well to different data access patterns. As a result, better scalability is achieved by the proposed protocol.

Description: With recent advances in technologies such as radio-frequency identification and new standards such as the electronic product code, large-scale traceability is emerging as a key differentiator in a wide range of enterprise applications (e.g. counterfeit prevention, product recalls and pilferage reduction). Such traceability applications often need to access data collected by individual enterprises in a distributed environment. Traditional centralized approaches (e.g. data warehousing) are not feasible for these applications due to their unique characteristics such as large volume of data and sovereignty of the participants. In this paper, we describe an approach that enables applications to share traceability data across independent enterprises in a pure peer-to-peer (P2P) fashion. Data are stored in local repositories of participants and indexed in the network based on structured P2P overlays. In particular, we present a generic approach for efficiently indexing and locating individual objects in large, distributed traceable networks, most notably, in the emerging environment of the internet of things. The results from extensive experiments show that our approach scales well in both data volume and network size. A real-world returnable assets management system is also developed using the proposed techniques to demonstrate its feasibility.

Description: Detecting motion-based video change, such as different types of motion video or applications using different change detection algorithms in a Web system, is difficult. This paper designs and implements architecture for a real-time or near real-time on-demand motion video change detection system using the Sensor Observation Service (SOS) and the Web Processing Service (WPS) in the Sensor Web environment. Real-time or near real-time includes sensors that obtain motion video data, SOS provides motion video data to WPS and WPS processes this data. Three solution methods are introduced: the GetObservation operation of SOS by transaction, dynamical interaction between SOS and WPS, and WPS real-time or near real-time processing. On-demand means that a developer can choose different motion video change detection algorithms under different applications or different conditions. For this purpose, a flexible, standards-based and service-oriented WPS architecture is designed, which consists of three layers: the WPS interface layer, the field interface layer and the implementation layer. To test the proposed approach, a video change detection case of monitoring a road situation is shown, which was a demonstration for Open Geospatial Consortium Web Service phase 7. The results demonstrate that the proposed approach is feasible.

Description: Most traditional recommender systems lack accuracy in the case where data used in the recommendation process is sparse. This study addresses the sparsity problem and aims to get rid of it by means of a content-boosted collaborative filtering approach applied to a web-based movie recommendation system. The main motivation is to investigate whether further success can be obtained by combining ‘local and global user similarity’ and ‘effective missing data prediction’ approaches, which were previously introduced and proved to be successful separately. The present work improves these approaches by taking the content information of the movies into account during the item similarity calculations. The comparison of the proposed approach with the original methods was carried out using mean absolute error, and more accurate predictions were achieved.

Description: Lax modalities occur in intuitionistic logics concerned with hardware verification, the computational lambda calculus and access control in secure systems. They also encapsulate the logic of Lawvere–Tierney–Grothendieck topologies on topoi. This article provides a complete semantics for quantified lax logic by combining the Beth–Kripke–Joyal cover semantics for first-order intuitionistic logic with the classical relational semantics for a ‘diamond’ modality. The main technique used is the lifting of a multiplicative closure operator (nucleus) from a Heyting algebra to its MacNeille completion, and the representation of an arbitrary locale as the lattice of ‘propositions’ of a suitable cover system. In addition, the theory is worked out for certain constructive versions of the classical logics K and S4. An alternative completeness proof is given for (non-modal) first-order intuitionistic logic itself with respect to the cover semantics, using a simple and explicit Henkin-style construction of a characteristic model whose points are principal theories rather than prime-saturated ones. The article provides further evidence that there is more to intuitionistic modal logic than the generalization of properties of boxes and diamonds from Boolean modal logic.

Description: In Baaz and Iemhoff (2006, Annals of Pure and Applied Logic, 142, 269–295), an alternative skolemization method called eskolemization was introduced that is sound and complete for existence logic with respect to existential quantifiers. Existence logic is a conservative extension of intuitionistic logic by an existence predicate. Therefore, eskolemization provides a skolemization method for intuitionistic logic as well. All proofs in Baaz and Iemhoff (2006, Annals of Pure and Applied Logic, 142, 269–295) were semantical. In this article, a proof-theoretic proof of the completeness of eskolemization with respect to existential quantifiers is presented.

Description: The intuitionistic sequent calculus (at most one formula on the right-hand side of sequents) comes with a natural dual system: the dual-intuitionistic sequent calculus (at most one formula on the left-hand side). We explain how the duality between these two systems exactly corresponds to the intensively studied duality between call-by-value systems and call-by-name systems for classical logic. Relying on the uniqueness of the computational behaviour underlying these four logics (intuitionistic, dual-intuitionistic, call-by-value classical and call-by-name classical), we define a generic syntax of nets which can be used for any of these logics.

Description: The study of propositional realizability logic was initiated in the 50th of the last century. Unfortunately, no description of the class of realizable propositional formulas is found up to now. Nevertheless, some attempts of such a description were made. In 1974, the author proved that every known realizable propositional formula has the property that every one of its closed arithmetical instances is deducible in the system obtained by adding Extended Church's Thesis and Markov Principle as axiom schemes to Intuitionistic Arithmetic. Visser calls this system Markov's Arithmetic. In 1990, another attempt of describing the class of realizable propositional formulas was made by Varpakhovskii who proposed a calculus in an extended propositional language and proved that all known realizable propositional formulas are deducible in this calculus. In this article we prove that every propositional formula deducible in Varpakhovskii's calculus has the property that each of its closed arithmetical instances is deducible in Markov's Arithmetic.

Description: Is it possible to give a coordinate-free formulation of the Second Incompleteness Theorem? We pursue one possible approach to this question. We show that (i) cutfree consistency for finitely axiomatized theories can be uniquely characterized modulo EA -provable equivalence and (ii) consistency for finitely axiomatized sequential theories can be uniquely characterized modulo EA -provable equivalence. The case of infinitely axiomatized RE theories is more delicate. We carefully discuss this in the article.

Description: In this article, we study the canonical model for the closed fragment of GLP and establish its precise relationship with a universal model constructed by Ignatiev. In particular, we effectively characterize the canonical model in terms of a coordinate system based on sequences of ordinals up to 0 .We then define a simple topological model of this logic by defining a natural polytopology on the ordinal 0 itself.

Description: We give a sound and complete labelled natural deduction system for a bundled branching temporal logic, namely the until-free version of BCTL *. The logic BCTL * is obtained by referring to a more general semantics than that of CTL *, where we only require that the set of paths in a model is closed under taking suffixes (i.e. is suffix-closed) and is closed under putting together a finite prefix of one path with the suffix of any other path beginning at the same state where the prefix ends (i.e. is fusion-closed). In other words, this logic does not enjoy the so-called limit-closure property of the standard CTL * validity semantics. We give both a classical and an intuitionistic version of our labelled natural deduction system for the until-free version of BCTL *, and carry out a proof-theoretical analysis of the intuitionistic system: we prove that derivations reduce to a normal form, which allows us to give a purely syntactical proof of consistency (for both the intuitionistic and classical versions) of the deduction system.

Description: The existence of states and probabilities on effect algebras as logical structures when events may be non-compatible, unsharp, fuzzy or imprecise is still an open question. Only a few families of effect algebras possessing states are known. We are going to show some families of effect algebras, the existence of a pseudocomplementation on which implies the existence of states. Namely, those are Archimedean atomic lattice effect algebras, which are sharply dominating or s-compactly generated or extendable to complete lattice effect algebras.

Description: One approach to moderating the expected behaviour of agents in open societies is the use of explicit languages for defining norms, conditional commitments and/or social expectations, together with infrastructure supporting conformance checking. This article presents a logical account of the fulfilment and violation of social expectations modelled as conditional rules over a hybrid linear propositional temporal logic. Our semantics captures the intuition that the fulfilment or violation of an expectation must be determined without recourse to information from later states.We define a means of updating expectations from one state to the next based on formula progression, and show how conformance checking was implemented by combining the MCFULLmodel checking algorithm of Franceschet and de Rijke and the semantics for LTL over truncated paths proposed by Eisner et al. We present algorithms for both traditional offline model checking, where the complete model is available at once, and online model checking, where states are added to the model sequentially at runtime.

Description: Among the class of finite integral commutative residuated chains (ICRCs), we identify those algebras which can be obtained as a nuclear retraction of a conuclear contraction of a totally ordered Abelian -group. We call the ICRCs satisfying this condition regular. Then we discuss the structure of finite regular ICRCs. Finally, we prove that the class of regular members generate a strictly smaller variety than the variety generated by ICRCs.

Description: We provide a constructive, direct and simple proof of the completeness of the cut-free part of the hypersequential calculus HG for Gödel logic (thereby proving both completeness of the calculus for its standard semantics, and the admissibility of the cut rule in the full calculus). We then extend the results and proofs to derivations from assumptions, showing that such derivations can be confined to those in which cuts are made only on formulas which occur in the assumptions. The article is self-contained, and no previous knowledge concerning HG (or even Gödel logic) is needed for understanding it.

Description: A particular notion of an interpretation of a theory over a fuzzy predicate logic in another such theory is discussed. For interpretability with the domain defined by a provably crisp formula, which is of course a syntactical notion, a semantic characterization is established. In the last section, we discuss the question of whether the extension of a decidable theory by a single new axiom is decidable and present an erratum to the paper (Hájek, 2007, Fundamenta informaticae , 81 , 155–163).

Description: This article deals with many-valued modal logics, based only on the necessity operator, over a residuated lattice. We focus on three basic classes, according to the accessibility relation, of Kripke frames: the full class of frames evaluated in the residuated lattice (and so defining the minimum modal logic), the ones evaluated in the idempotent elements and the ones only evaluated in 0 and 1. We show how to expand an axiomatization, with canonical truth-constants in the language, of a finite residuated lattice into one of the modal logic, for each one of the three basic classes of Kripke frames. We also provide axiomatizations for the case of a finite MV chain but this time without canonical truth-constants in the language.

Description: The article deals with Codd's relational model of data and its fuzzy logic extensions. Our main purpose is to examine, from the point of view of fuzzy logic in the narrow sense, some of the extensions proposed in the literature and the relationships between them. We argue that fuzzy logic in the narrow sense is important for the fuzzy logic extensions because it provides conceptual and methodological foundations, clarity and simplicity. We present several comparative observations as well as new technical results.

Description: This article shows how derivations in the deep inference system SKS for classical propositional logic can be translated into proof nets. Since an SKS derivation contains more information about a proof than the corresponding proof net, we observe a loss of information which can be understood as ‘eliminating bureaucracy’. Technically, this is achieved by cut reduction on proof nets. As an intermediate step between the two extremes, SKS derivations and proof nets, we will see proof graphs representing derivations in ‘Formalism A’.

Description: The superintuitionistic predicate logics (without or with equality) of all predicate Kripke frames with nested domains over a fixed poset W (a set of possible worlds) are embeddable in the logic (without equality) of all Kripke frames with constant domains over W . Therefore, Takano's result [13] on finite axiomatizability of the logic of Kripke frames with constant domains over the set of real numbers implies the recursive axiomatizability of the corresponding logics with nested domains. Other consequences are mentioned as well.

Description: How do animals use their habitat? Where do they go and what do they do? These basic questions are key not only to understanding a species’ ecology and evolution, but also for addressing many of the environmental challenges we currently face, including problems posed by invasive species, the spread of zoonotic diseases and declines in wildlife populations due to anthropogenic climate and land-use changes. Monitoring the movements and activities of wild animals can be difficult, especially when the species in question are small, cryptic or move over large areas. In this paper, we describe an Automated Radio-Telemetry System (ARTS) that we designed and built on Barro Colorado Island (BCI), Panama to overcome these challenges. We describe the hardware and software we used to implement the ARTS, and discuss the scientific successes we have had using the system, as well as the logistical challenges we faced in maintaining the system in real-world, rainforest conditions. The ARTS uses automated radio-telemetry receivers mounted on 40-m towers topped with arrays of directional antennas to track the activity and location of radio-collared study animals, 24 h a day, 7 days a week. These receiving units are connected by a wireless network to a server housed in the laboratory on BCI, making these data available in real time to researchers via a web-accessible database. As long as study animals are within the range of the towers, the ARTS system collects data more frequently than typical animal-borne global positioning system collars (~12 locations/h) with lower accuracy (approximately 50 m) but at much reduced cost per tag (~10X less expensive). The geographic range of ARTS, like all VHF telemetry, is affected by the size of the radio-tag as well as its position in the forest (e.g. tags in the canopy transmit farther than those on the forest floor). We present a model of signal propagation based on landscape conditions, which quantifies these effects and identifies sources of interference, including weather events and human activity. ARTS has been used to track 374 individual animals from 38 species, including 17 mammal species, 12 birds, 7 reptiles or amphibians, as well as two species of plant seeds. These data elucidate the spatio-temporal dynamics of animal activity and movement at the site and have produced numerous peer-reviewed publications, student theses, magazine articles, educational programs and film documentaries. These data are also relevant to long-term population monitoring and conservation plans. Both the successes and the failures of the ARTS system are applicable to broader sensor network applications and are valuable for advancing sensor network research.

Description: Energy efficiency is a key characteristic of modern wireless sensors. Assuming that the transceiver is the most power-consuming component of a typical sensor node, then a large advantage can be achieved at the data link layer where the medium access control (MAC) protocol controls the usage of the radio unit. Many MAC protocols have been developed for traditional wireless networks. Given that the sensor network is different from the traditional wireless network in many places, researchers are looking for a MAC protocol that is specifically designed and adapted to the sensor network. Moreover, most of the contributions in the wireless sensor network have assumed static nodes. However, some applications in the area of medical care and disaster response make use of the mobile sensor network. Thus, the present paper studies and simulates the sensor MAC (S-MAC), timeout MAC and mobility-aware S-MAC (MS-MAC) protocols in terms of their energy efficiency in different mobility situations. Furthermore, an enhancement of the MS-MAC protocol, named as enhanced MS-MAC, is introduced and simulated. The results show that this enhancement can significantly improve the energy efficiency when there is a reasonable packet delivery rate.

Description: According to Lee in 1996, computer scientists ‘are reaching the stage of development where each new generation of participants is unaware both of their overall technological ancestry and the history of the development of their speciality, and have no past to build upon’ [Lee, J.A.N. (1996) "Those who forget the lessons of history are doomed to repeat it" or, why I study the history of computing. IEEE Ann. Hist. Comput. 18, 54–62]. A technically and historically accurate account, as attempted here, can help us, computer scientists, grasp some of the fundamental ideas underlying our discipline. This paper describes some early contributions of Dijkstra by elaborating on his involvement in putting forward and implementing the recursive procedure as an ALGOL60 language construct. Particular attention is paid to Dijkstra's generalizing style of solving problems.

Description: This paper explores efficient ways to use flash memory to store online analytical processing (OLAP) data. The particular type of queries considered are range queries using the aggregate functions SUM, COUNT and AVG. The asymmetric cost of reads and writes for flash memory gives higher importance to how updates are handled in a flash memory environment. A popular data structure used for answering OLAP range-sum queries is the prefix sum cube. It allows the range-sum query to be answered in constant time. However, updating the prefix sum cube is very expensive. To overcome this, the -tree was proposed by Chun et al . (Dynamic update cube for range-sum queries. Proc. Int. Conf. Very Large Data Bases, San Francisco, CA, USA, 2001, pp. 521–530. Morgan Kaufmann Publisher). The -tree stores all updates to the prefix sum cube in a separate r-tree. This approach worked well for the hard disk where in-place updates are relatively cheap. However, for flash memory where in-place updates are very expensive, the -tree performs very poorly. We take a four-pronged approach to overcome the problem of expensive in-place updates. The first is efficient caching of updates in RAM. The second is writing out whole trees from RAM to flash memory instead of incrementally updating a disk resident tree. The third is we allow users to trade bounded amounts of accuracy for less updates via lossy compression. Finally, we use a quadtree index structure instead of the R-tree. We prove that the quadtree compression problem is NP-complete. A greedy heuristic is proposed to find near optimal solutions in polynomial time. Various experiments were conducted to compare the proposed algorithms against the existing -tree. The results show that our algorithms consistently outperformed -tree by factors of between 10 and 100. This demonstrates the importance of designing flash memory customized algorithms for OLAP range queries. In addition, among our algorithms, the error bound solutions with a small error bound setting significantly outperform the accurate solution in terms of performance for a variety of parameter settings. This indicates that the error bound algorithms offer users an effective trade-off between execution time and accuracy.

Description: This paper focuses on the performance evaluation of Compiler for Portable Checkpointing (CPPC), a tool for the checkpointing of parallel message-passing applications. Its performance and the factors that impact it are transparently and rigorously identified and assessed. The tests were performed on a public supercomputing infrastructure, using a large number of very different applications and showing excellent results in terms of performance and effort required for integration into user codes. Statistical analysis techniques have been used to better approximate the performance of the tool. Quantitative and qualitative comparisons with other rollback-recovery approaches to fault tolerance are also included. All these data and comparisons are then discussed in an effort to extract meaningful conclusions about the state-of-the-art and future research trends in the rollback-recovery field.

Description: There are various ways to measure the shape difference between two n -node rooted binary trees (binary trees for short). A rotation on a binary tree is a local restructuring that changes the tree into another one preserving the in-order sequence. The rotation distance between two binary trees is the minimum number of rotations needed to transform one into another. Till now, no polynomial–time algorithm exists for computing the rotation distance between any two binary trees. Recently, Lucas ( Comput. J. , 47, 259–269, 2004) presented an O ( n 2 )–time algorithm for finding the rotation distance between two binary trees, where the source tree is a degenerate tree and the destination tree is an angle tree. This paper improves the time-complexity to O ( n ) under this constraint.

Description: We discuss algorithm recognition (AR) and present a method for recognizing algorithms automatically from Java source code. The method consists of two phases. In the first phase, the recognizable algorithms are converted into the vectors of characteristics, which are computed based on static analysis of program code, including various statistics of language constructs and analysis of Roles of Variables in the target program. In the second phase, the algorithms are classified based on these vectors using the C4.5 decision tree classifier. We demonstrate the performance of the method by applying it to sorting algorithms. Using leave-one-out cross-validation technique, we have conducted an experimental evaluation of the classification performance showing that the average classification accuracy is 98.1% (the data set consisted of five different types of sorting algorithms). The results show the applicability and usefulness of roles of variables in AR, and illustrate that the C4.5 algorithm is a suitable decision tree classifier for our purpose. The limitations of the method are also discussed.

Description: Electron tomography (ET) is an important technique in biosciences that is providing new insights into the cellular ultrastructure. Iterative reconstruction methods have been shown to be robust against the noise and limited-tilt range conditions present in ET. Nevertheless, these methods are not extensively used due to their computational demands. Instead, the simpler method weighted backprojection (WBP) remains prevalent. Recently, we have demonstrated that a matrix approach to WBP allows a significant reduction in processing time both on central processing units and on graphics processing units (GPUs). In this work, we extend that matrix approach to one of the most common iterative methods in ET, simultaneous iterative reconstruction technique (SIRT). We show that it is possible to implement this method targeted at GPU directly, using sparse algebra. We also analyse this approach on different GPU platforms and confirm that these implementations exhibit high performance. This may thus help to the widespread use of SIRT.

Description: The source-location privacy problem in Wireless Sensor Networks has been traditionally tackled by the creation of random routes for every packet transmitted from the source nodes to the base station. These schemes provide a considerable protection level at a high cost in terms of message delivery time and energy consumption. This overhead is due to the fact that the data routing process is done in a blind way, without knowledge about the location of the attacker. In this work, we propose the Context-Aware Location Privacy (CALP) approach, which takes advantage of the ability of sensor nodes to perceive the presence of a mobile adversary in their vicinity in order to transmit data packets in a more energy-efficient and privacy-preserving manner. In particular, we apply the concepts of CALP to the development of a shortest-path CALP routing algorithm. A permissive and a strict version of the protocol are studied for different adversarial models and the proposed schemes are evaluated through simulation experiments in terms of privacy protection and energy consumption. Finally, we present the conclusions of the paper as well as possible extensions of this work.

Description: The sum of k mins protocol was proposed by Hopper and Blum as a protocol for secure human identification. The goal of the protocol is to let an unaided human securely authenticate to a remote server. The main ingredient of the protocol is the sum of k mins problem. The difficulty of solving this problem determines the security of the protocol. In this paper, we show that the sum of k mins problem is NP-Complete and W[1]-Hard. This latter notion relates to fixed parameter intractability. We also discuss the use of the sum of k mins protocol in resource-constrained devices.

Description: As an interesting application on cloud computing, content-based image retrieval (CBIR) has attracted a lot of attention, but the focus of previous research work was mainly on improving the retrieval performance rather than addressing security issues such as copyrights and user privacy. With an increase of security attacks in the computer networks, these security issues become critical for CBIR systems. In this paper, we propose a novel two-party watermarking protocol that can resolve the issues regarding user rights and privacy. Unlike the previously published protocols, our protocol does not require the existence of a trusted party. It exhibits three useful features: security against partial watermark removal, security in watermark verification and non-repudiation. In addition, we report an empirical research of CBIR with the security mechanism. The experimental results show that the proposed protocol is practicable and the retrieval performance will not be affected by watermarking query images.

Description: A non-autonomous cross-coupled chaotic circuit is presented with its derivation mechanism. To guarantee robust chaotic behavior of the circuit against parameter variations, an ideal set of parameters is determined by constructing bifurcation diagrams. A truly random number generator (TRNG), which relies on generating non-invertible binary sequences according to regional distributions of underlying chaotic signal, is also introduced. Simulation and experimental results verifying the feasibility of the circuit are given. The proposed TRNG offers much higher and constant throughput rates, allows for offset compensation and fulfills the NIST-800-22 statistical test suite without further post-processing.

Description: In 1986, Victor Miller described an algorithm for computing the Weil pairing in his unpublished manuscript. This algorithm has then become the core of all pairing-based cryptosystems. Many improvements of the algorithm have been presented. Most of them involve a choice of elliptic curves of a special form to exploit a possible twist during Tate pairing computation. Other improvements involve a reduction of the number of iterations in the Miller's algorithm. For the generic case, Blake, Murty and Xu proposed three refinements to Miller's algorithm over Weierstrass curves. Though their refinements, which only reduce the total number of vertical lines in Miller's algorithm, did not give an efficient computation as other optimizations, they can be applied for computing both Weil and Tate pairings on all pairing-friendly elliptic curves. In this paper, we extend the Blake–Murty–Xu's method and show how to perform an elimination of all vertical lines in Miller's algorithm during computation of Weil/Tate pairings, on general elliptic curves. Experimental results show that our algorithm is faster by ~25% in comparison with the original Miller's algorithm.

Description: Hardware implementation of decimal floating-point arithmetic is a topic of great interest among the researchers in computer arithmetic and also the digital processor industry. Software packages for decimal arithmetic are actually being challenged by decimal hardware units. This spreading trend seems to include hardware implementation of elementary functions. The (Coordinate Rotation Digital Computer) CORDIC algorithm, due to its simplicity, is one of the most efficient methods for computing elementary functions. In this work, we develop a decimal CORDIC scheme with almost half number of equally long cycles with respect to the best previous design. This is achieved via retiming of the conventional CORDIC architecture and selection of the microrotation factors by rounding. However, the proposed design does not lead to a predetermined constant scaling factor. The solution that we use is to iteratively compute the logarithm of the scaling factor followed by a decimal exponentiation. The same CORDIC hardware is reused for performing the latter. The proposed CORDIC method requires 2 n + 3 cycles for n-digit decimal operands vs. 4n cycles of the previous methods. Evaluations with 16-digit operands based on logical effort analysis conclude that the proposed architecture shows 82% speed advantage, at the cost of 60% more area and 2.5 KB more ROM.

Description: This interdisciplinary study covers bionics, optimization and vehicle engineering. Semi-track air-cushion vehicle (STACV) provides a solution to transportation on soft terrain, whereas it also brings a new problem of excessive fuel consumption. By mimicking the foraging behaviour of honeybees, the bioinspired adaptive bees algorithm (ABA) is proposed to calculate its running parameters for fuel economy optimization. Inherited from the basic algorithm prototype, it involves parallel-operated global search and local search, which undertake exploration and exploitation, respectively. The innovation of this improved algorithm lies in the adaptive adjustment mechanism of the range of local search (called ‘patch size’) according to the source and the rate of change of the current optimum. Three gradually in-depth experiments are implemented for 143 kinds of soils. First, the two optimal STACV running parameters present the same increasing or decreasing trend with soil parameters. This result is consistent with the terramechanics-based theoretical analysis. Second, the comparisons with four alternative algorithms exhibit the ABA's effectiveness and efficiency, and accordingly highlight the advantage of the novel adaptive patch size adjustment mechanism. Third, the impacts of two selected optimizer parameters to optimization accuracy and efficiency are investigated and their recommended values are thus proposed.

Description: In this article, an image feature extraction method based on two-dimensional (2D) Mellin cepstrum is introduced. The concept of one-dimensional (1D) mel-cepstrum that is widely used in speech recognition is extended to two-dimensions using both the ordinary 2D Fourier transform and the Mellin transform. The resultant feature matrices are applied to two different classifiers such as common matrix approach and support vector machine to test the performance of the mel-cepstrum- and Mellin-cepstrum-based features. The AR face image database, ORL database, Yale database and FRGC database are used in experimental studies, which indicate that recognition rates obtained by the 2D mel-cepstrum-based method are superior to that obtained using 2D principal component analysis, 2D Fourier-Mellin transform and ordinary image matrix-based face recognition in both classifiers. Experimental results indicate that 2D cepstral analysis can also be used in other image feature extraction problems.

Description: Cloud security is a major concern that may delay its widespread adoption. User access control (UAC) is the core component of security in cloud computing environment, aiming to ensure that stored data are allowed to be accessed only by authenticated/authorized users. As a typical behavioural biometrics, keystroke dynamics provides a promising UAC solution. The most challenging issue that hinders the wide deployment of keystroke is the high verification error rate. Gunetti et al. proposed a classical n -graph-based keystroke verification method (GP method), which can achieve a low False Acceptance Rate (FAR). However, the GP method suffers from a high False Rejection Rate (FRR) and a severe scalability issue. Thus, GP is not a feasible solution for computing cloud application where scalability is a big issue. In this paper, two keystroke verification approaches ( n Gdv-V and n Gdv-C) are proposed to overcome GP's shortcomings. To reduce high FRR, we designed a new correlation measure using n -graph equivalent feature ( n Gdv) that enables more accurate recognition for genuine users. Moreover, correlation-based hierarchical clustering is proposed to address the scalability issue. The experimental results show that the n Gdv-C can produce much lower FRR while achieving almost the same level of FAR as that of the GP method. Furthermore, 1250 times (when using n Gdv-V) and three times (when using n Gdv-C(17,4)) authentication speed gains have been achieved.

Description: In this paper, a new compression scheme is presented, inspired by the synchronized extension systems, a mechanism somehow conceptually similar to dictionary compression. As in the case of traditional dictionary compression methods, the input sequence is parsed into blocks and the repeating blocks are identified. The main difference is that overlapping blocks are allowed. A modified Lampel-Ziv-Welch (LZW) parsing scheme is also presented.

Description: The increasing popularity of flash memory means more database systems will run on flash memory in the future. One of the most important database operations is the external sort. Hence, this paper is focused on studying the problem of efficient external sorting on flash memory. In contrast to most previous work, we target the situation where previously sorted data have become progressively unsorted due to data updates. Accordingly, we call this ‘partially’ sorted data. We focus on re-sorting partially sorted data by taking advantage of the partial sorted nature of the data to speed up the run generation phase of the traditional external merge sort. We do this by finding ‘naturally occurring’ page runs in the partially sorted data. Our algorithm can perform up to a factor of 1024 less write IO compared with a traditional external merge sort during the run generation phase. We map the problem of finding naturally occurring runs into the shortest distance problem in a directed acyclic graph (DAG). Accordingly, we propose an optimal solution to the problem using the well-known DAG-Shortest-Paths algorithm. However, we found that the optimal solution was too slow for even moderate-sized data sets and accordingly propose a fast heuristic solution that—we experimentally show—finds a high percentage of page runs using a minimum of computational overhead. Experiments using both real and synthetic data sets show that our heuristic algorithm can halve the external sorting time when compared with three likely competing external sorting algorithms.

Description: The L (2, 1)-labeling of a digraph G is a function f from the node set of G to the set of all non-negative integers such that | f ( x )– f ( y )| ≥ 2 if x and y are at distance 1, and f ( x ) != f ( y ) if x and y are at distance 2, where the distance from node x to node y is the length of a shortest dipath from x to y . The minimum over all L (2, 1)-labeling of G of the largest used label is called . In this paper, we study the L (2, 1)-labelings problem on squared, triangular and hexagonal grids and for them we compute the exact values of .

Description: At present server farms play an important role in the provision of services in IT industry. The energy consumption of server farms significantly contributes to the operational cost. Complementary management actions exploit the capability of the hardware infrastructure and the stochastic nature of computing demands to reduce energy consumption related to the operation of server farms. In this paper, a simple energy-aware policy incorporating allocation schemes of virtual servers is proposed to achieve the aim of green computing. The policy automatically governs physical hosts to a low-energy consuming state when no virtual servers are allocated in a specific physical host and automatically manages a physical host into the operating state of full functionality when virtual servers are assigned. We present an analytical performance model to compare three allocation schemes of dynamic requests for virtual servers in a server farm.

Description: This article formalizes and compares two different styles of reasoning with inductively defined predicates, each style being encapsulated by a corresponding sequent calculus proof system.The first system, LKID, supports traditional proof by induction, with induction rules formulated as rules for introducing inductively defined predicates on the left of sequents.We show LKID to be cut-free complete with respect to a natural class of Henkin models; the eliminability of cut follows as a corollary. The second system, LKID , uses infinite (non-well-founded) proofs to represent arguments by infinite descent. In this system, the left-introduction rules for inductively defined predicates are simple case-split rules, and an infinitary, global condition on proof trees is required in order to ensure soundness.We show LKID to be cut-free complete with respect to standard models, and again infer the eliminability of cut. The infinitary system LKID is unsuitable for formal reasoning. However, it has a natural restriction to proofs given by regular trees, i.e. to those proofs representable by finite graphs, which is so suited. We demonstrate that this restricted ‘cyclic’ proof system, CLKID , subsumes LKID, and conjecture that CLKID and LKID are in fact equivalent, i.e. that proof by induction is equivalent to regular proof by infinite descent.

Description: Measuring inconsistency in knowledge bases has been recognized as an important problem in several research areas. Many methods have been proposed to solve this problem and a main class of them is based on some kind of paraconsistent semantics. However, existing methods suffer from two limitations: (i) they are mostly restricted to propositional knowledge bases; (ii) very few of them discuss computational aspects of computing inconsistency measures. In this article, we try to solve these two limitations by exploring algorithms for computing an inconsistency measure of first-order knowledge bases. After introducing a four-valued semantics for first-order logic, we define an inconsistency measure of a first-order knowledge base, which is a sequence of inconsistency degrees. We then propose a precise algorithm to compute our inconsistency measure. We show that this algorithm reduces the computation of the inconsistency measure to classical satisfiability checking. This is done by introducing a new semantics, named S [ n ] -4 semantics, which can be calculated by invoking a classical SAT solver. Moreover, we show that this auxiliary semantics also gives a direct way to compute upper and lower bounds of inconsistency degrees. That is, it can be easily revised to compute approximating inconsistency measures. The approximating inconsistency measures converge to the precise values if enough resources are available. Finally, by some nice properties of the S [ n ] -4 semantics, we show that some upper and lower bounds can be computed in P-time, which says that the problem of computing these approximating inconsistency measures is tractable.

Description: The abstract nature of Dung’s theory of argumentation accounts for its wide-spread application as a general framework for various species of non-monotonic reasoning, and, more generally, reasoning in the presence of conflict. In this article, we formalize reasoning about argumentation within the Dung argumentation paradigm itself. A metalevel Dung argumentation framework is itself instantiated by arguments that make statements about arguments, their interactions, and their evaluation in an object-level argumentation framework.We show how Dung’s theory, and object-level extensions of Dung’s theory, such as those intended to accommodate preferences, can then be uniformly characterised by metalevel argumentation in a Dung framework. We then discuss how this provides for application of the full range of theoretical and practical developments of Dung’s theory, to extensions of Dung’s theory, and provides for integration and further augmentation of these extensions.

Description: Classical logic of proofs LP naturally extends propositional calculus to the language enriched with formulas meaning t is a proof of formula F . Intuitionistic logic of proofs iLP introduced by Artemov and Iemhoff was conjectured to be complete with respect to intuitionistic arithmetic HA. The article presents a proof of this conjecture.

Description: Using Pauly’s majority logic, a modal-like language that describes decisions of a collective of agents, this article develops an explicit relationship between logic and social choice theory, particularly judgement aggregation. Majority logic is, within certain limits, able to express properties of decision procedures that are used to reach collective judgements. Those properties are often facts about the validity of logical inference rules at the level of collective decision making. From the perspective of social choice theory, formulae of majority logic can be regarded as axioms about the possibility of correct collective inference. Exploring the link with modal logic, and using so-called simple games as the mathematical structures representing decision procedures, we argue that the axiomatizations of social choice theorists mimic definability results from the perspective of modal logicians. Sets of formulae of majority logic define classes of decision procedures in this sense. Based on simple games, we give a game-theoretic characterization of properties of decision procedures that can be expressed using majority logic. From this, we deduce the closure conditions on classes of decision procedures that are definable using majority logic. This establishes a concrete link between a language in which axioms may be formulated, and the properties of decision procedures that it is able to characterize. Closure conditions also allow us to determine limits to the expressive and axiomatic power of majority logic. Since much of social choice theory is occupied with finding decision procedures that admit valid collective inference, and this is the domain of majority logic, quite a few familiar classes of decision procedures are definable. However, we show that majority logic is too weak to express non-dictatorship—in effect a language-relative impossibility result. We relate these definability results to recent results obtained in the judgement aggregation literature, in particular to some of the impossibility results.

Description: Recent work on Alternating-Time Temporal Logic and Coalition Logic has allowed the expression of many interesting properties of coalitions and strategies. However, there is no natural way of expressing resource requirements in these logics. In this article, we present a Resource-Bounded Coalition Logic ( RBCL ) that has explicit representation of resource bounds in the language. We give a complete and sound axiomatization of RBCL , a procedure for deciding satisfiability of RBCL formulas, and a model-checking algorithm.

Description: We show that propositional linear temporal logic with knowledge modalities but without common knowledge has an undecidable satisfiability problem when interpreted in a ‘concrete’ semantics with perfect recall or with perfect recall and synchrony.We then conclude that this concrete semantics is not axiomatizable in the semantics, based on local states.

Description: Justification Logic is a framework for reasoning about evidence and justification in multi-agent systems. Most accounts of Justification Logic are essentially static, in that the (justified) beliefs of agents are immutable. In this article, we add public communication, a dynamic operation of belief change studied in the area of Dynamic Epistemic Logic , to the language of Justification Logic. Introducing notions of bisimulation for the languages of Justification Logic with and without public communication, we catalogue the expressive relationships that exist between almost all of the well-known static fragments of Justification Logic and then determine whether the addition of public communication affects the various expressive relationships existing between these fragments.

Description: The study of constraint satisfaction problems (CSPs) definable in various fragments of Datalog has recently gained considerable importance.We consider CSPs that are definable in the smallest natural recursive fragment of Datalog—monadic linear Datalog with at most one EDB (extensional database predicates) per rule, and also in the smallest nonlinear extension of this fragment. We give combinatorial and algebraic characterizations of such problems, in terms of homomorphism dualities and lattice operations, respectively.We then apply our results to study graph H -colouring problems.

Description: Many sensor network application scenarios include mobile nodes, such as a moving sink. Evaluation of such applications in a testbed is challenging as the testbed has to support mobile nodes. Here, we present Sensei-UU, a sensor network testbed that supports mobile sensor nodes. The testbed is inexpensive, relocatable and possible to reproduce by other researchers. Its primary design objectives are to support experiments with repeatable mobility and relocating the testbed deployment to different locations. Mobile sensor nodes are carried by robots that use floor markings for navigation and localization. The testbed can be used to evaluate applications in which sensor nodes move in the order of meters rather than millimeters, e.g. when a human carries a mobile phone that collects data while passing stationary sensor nodes. To investigate the repeatability of robot movements, we measure the achieved precision and the timing of the robots, and find that our robot localization is accurate to ±1 cm. Furthermore, we investigate variations in radio signal strengths between mobile and stationary nodes. We study the impact of imprecise movements, external sources of interference and environmental influences. We conclude that Sensei-UU supports experiments in which these variations are acceptably low to capture small-scale fading phenomena in IEEE 802.15.4.

Description: It is a known phenomenon that in a wireless sensor network, sensors communicating directly with a sink deplete their energy faster than the others. As a result, the so-called neighboring sensors can die, disconnecting some of the sinks from the rest of the network, even though most of the sensors are still fully functional. One possible remedy is to balance the relaying load of the sensors using mobile sinks and controlling their mobility, which has attracted the interest of researchers. In this work, we extend the relevant literature by introducing two new mathematical programming models. They intend to maximize the network lifetime through the controlled mobility of a sink with nonzero travel times with and without limiting the number of hops by which the data originating from the sensors reach the sink. Both models allow more than one tour of the sink during the network lifetime and determine the optimal sink route and sojourn times. Since the models are computationally difficult to solve, we propose efficient heuristics methods to compute near-optimal solutions. On the basis of the computational results performed on randomly generated problem instances, we can say that their performance is remarkable.

Description: The Capsule Reviews are intended to provide a short succinct review of each paper in the issue in order to bring it to a wider readership. The Capsule Reviews were compiled by Fairouz Kamareddine. Professor Kamareddine is an Associate Editor of The Computer Journal and is based in the Department of Mathematical and Computer Sciences at Heriot-Watt University, Edinburgh, UK.

Description: This paper proposes a unitable multi-core architecture, called hyperscalar , that can dynamically unite many scalar cores as a larger superscalar processor to accelerate a thread. To accomplish this, this paper proposes the virtual shared register files (VSRFs) that help the instructions of a thread in different cores can logically face a uniform set of register files. We also propose an instruction analyzer that can detect and tag the dependence information to the newly fetched instructions. With the tags, instructions in the united cores can issue requests to obtain their remote operands via the VSRF. Thus, the dependences arising among instructions in different cores can be resolved. Moreover, some extended instructions are defined for programmers to grow or shrink the number of united cores to match the available instruction level parallelism for different applications. The reconfigurable feature of hyperscalar covers a spectrum of workloads well, providing high single-thread performance when thread level parallelism (TLP) is low and high throughput when TLP is high. Simulation results show that the eight-core hyperscalar chip multiprocessor's two-, four- and eight-core-united configurations archive 93, 80 and 76% of the performance of the monolithic two-, four- and eight-issue out-of-order superscalar processors with lower area costs and better support for software diversity.

Description: Automatic video segmentation plays an important role in a wide range of computer vision and image processing applications. Recently, various methods have been proposed for this purpose. The problem is that most of these methods are far from real-time processing even for low-resolution videos due to the complex procedures. To this end, we propose a new and quite fast method for automatic video segmentation with the help of (1) efficient optimization of Markov random fields with polynomial time of the number of pixels by introducing graph cuts, (2) automatic, computationally efficient but stable derivation of segmentation priors using visual saliency and sequential update mechanism and (3) an implementation strategy in the principle of stream processing with graphics processor units. Test results indicate that our method extracts appropriate regions from videos as precisely as and much faster than previous semi-automatic methods even though no supervisions have been incorporated.

Description: Motion estimation (ME) process consumes up to 70% of the total encoding time of video transmission. Because it has a high coding efficiency and it is very scalable, the full search (FS) algorithm is considered to be the most popular ME algorithm. However, the main drawback of the FS algorithm is that it is computationally intensive. For this reason, FS is rarely used for real-time video coding. This paper proposes a simple and fast adaptive search window size (ASWS) algorithm that eliminates a significant amount of computations from the conventional FS algorithm. This is achieved by dynamically reducing the required search area for each reference block. Simulation results show that more than 94% of the candidate blocks are eliminated by our algorithm without significant loss in visual quality. This paper also presents an efficient and high-speed ME engine (MEE) architecture for the proposed ASWS algorithm. The MEE efficiently reuses the search area data to minimize the memory I/O while fully utilizing the available hardware resources. A smart processing element design along with an innovative data scheduling scheme allows the search area data to flow both horizontally and vertically, whereas the current block data remain stationary. This allows the proposed architecture a simple and highly regular dataflow through the core. Simulation results show that for a search range of [–16,+15] and a block size of 16 x 16, the proposed architecture performs the ME for 60 fps of 4CIF video at 100 MHz and easily outperforms many FS architectures.

Description: This study explores an alternative way of storing text files to answer exact match queries faster. We decompose the original file into two parts as filter and payload. The filter part contains the most informative k bits of each byte, and the remaining bits of the bytes are concatenated in the order of appearance to generate the payload. We refer to this structure as k -bit filtered format. When an input pattern is to be searched on the k -bit filtered structure, the same decomposition is performed on the pattern. The k bits from each byte of the pattern form the pattern filter bit sequence, and the rest is the payload. The pattern filter is first scanned on the filter part of the file. At each match position detected in the filter part, the pattern payload is verified against the corresponding location in the payload part of the text. Thus, instead of searching an m -byte pattern on an n -byte text, first k · m bits are scanned on k · n bits, followed by a verification of (8 – k )· m bits on the respective locations of the matching positions. Experiments conducted on natural language texts, plain ASCII DNA sequences and random byte sequences showed that the search performance with the proposed scheme is on average two times faster than the tested best exact pattern-matching algorithms. The highest gain is obtained on plain ASCII DNA sequences. We also developed an effective bitwise pattern-matching algorithm of possible independent interest within this study.

Description: The Capsule Reviews are intended to provide a short succinct review of each paper in the issue in order to bring it to a wider readership. The Capsule Reviews were compiled by Fairouz Kamareddine. Professor Kamareddine is an Associate Editor of The Computer Journal and is based in the Department of Mathematical and Computer Sciences at Heriot-Watt University, Edinburgh, UK.

Description: Coverage problems are a flourishing topic in optimization, thanks to the recent advances in the field of wireless sensor networks. The main coverage issue centres around critical conditions that require reliable monitoring and prohibit failures. This issue can be addressed by maximal-exposure paths, regarding which this article presents new results. Namely, it shows how to minimize the sensing range of a set of sensors in order to ensure the existence of a k -covered path between two points on a given region. Such a path's coverage depends on k ≥2, which is fixed. The three types of regions studied are: a planar graph, the whole plane and a polygonal region.

Description: Network coding, a well-known technique for optimizing data-flow in wired and wireless network systems, has attracted considerable attention in various fields. However, the decoding complexity in network coding becomes a major performance bottleneck in the practical network systems; thus, several researches have been conducted for improving the decoding performance in network coding. Nevertheless, previously proposed parallel network coding algorithms have shown limited scalability and performance imbalance for different-sized transfer units and multiple streams. In this paper, we propose a new parallel decoding algorithm for network coding using a graphics processing unit (GPU). This algorithm can simultaneously process multiple incoming streams and can maintain its maximum decoding performance irrespective of the size and number of transfer units. Our experimental results show that the proposed algorithm exhibits a 682.2 Mbps decoding bandwidth on a system with GeForce GTX 285 GPU and speed-ups of up to 26 as compared to the existing single stream decoding procedure with a 128 x 128 coefficient matrix and different-sized data blocks.

Description: This paper investigates the role of outliers in literature-based knowledge discovery. It shows that detecting interesting outliers which appear in the literature on a given phenomenon can help the expert to find implicit relationships among concepts of different domains. The underlying assumption is that while the majority of articles in the given scientific domain describe matters related to a common understanding of the domain, the exploration of outliers may lead to the detection of scientifically interesting bridging concepts among disjoint sets of scientific articles. The proposed approach contributes to cross-context link discovery by proving the utility of outlier detection for finding bisociative links in the process of autism literature exploration, as well as by uncovering implicit relationships in the articles from the migraine domain.

Description: Semistatic word-based byte-oriented compressors are known to be attractive alternatives to compress natural language texts. With compression ratios around 30–35%, they allow fast direct searching of compressed text. In this article, we reveal that these compressors have even more benefits. We show that most of the state-of-the-art compressors benefit from compressing not the original text, but the compressed representation obtained by a word-based byte-oriented statistical compressor. For example, p7zip with a dense-coding preprocessing achieves even better compression ratios and much faster compression than p7zip alone. We reach compression ratios below 17% in typical large English texts, which was obtained only by the slow prediction by partial matching compressors. Furthermore, searches perform much faster if the final compressor operates over word-based compressed text. We show that typical self-indexes also profit from our preprocessing step. They achieve much better space and time performance when indexing is preceded by a compression step. Apart from using the well-known Tagged Huffman code, we present a new suffix-free Dense-Code-based compressor that compresses slightly better. We also show how some self-indexes can handle non-suffix-free codes. As a result, the compressed/indexed text requires around 35% of the space of the original text and allows indexed searches for both words and phrases.

Description: Achieving accurate interpolation is an important requirement for many signal-processing applications. While nearest-neighbor and linear interpolation methods are popular due to their native GPU support, they unfortunately result in severe undesirable artifacts. Better interpolation methods are known but lack a native GPU support. Yet, a particularly attractive one is prefiltered cubic-spline interpolation. The signal it reconstructs from discrete samples has a much higher fidelity to the original data than what is achievable with nearest-neighbor and linear interpolation. At the same time, its computational load is moderate, provided a sequence of two operations is applied: first, prefilter the samples, and only then reconstruct the signal with the help of a B-spline basis. It has already been established in the literature that the reconstruction step can be implemented efficiently on a GPU. This article focuses on an efficient GPU implementation of the prefilter, on how to apply it to multidimensional samples (e.g. RGB color images), and on its performance aspects.

Description: This paper examines three ideas: First, the traditional relationship between a science, the mathematics it uses and the engineering based on it. Second, the nature of (software) computer science, which may not be a science at all, and its unusual use of mathematics. And finally, the nature of software engineering, its relationship with computer science, and its use of mathematics called ‘formal methods’. These three ideas turn on the first of them, since the scientific world view seems natural for the study of computing. The paper's thesis is that while software touches science in many ways, it does not itself have a significant scientific component. For understanding programming, for teaching it and for applying it in the world, science is the wrong model. Mathematics has found its own foundations apart from science, and computer science must do the same.

Description: Novel data-mining tasks in e-science involve mining of distributed, highly heterogeneous data and knowledge sources. However, standard data mining platforms, such as Weka and Orange, involve only their own data mining algorithms in the process of knowledge discovery from local data sources. In contrast, next generation data mining technologies should enable processing of distributed data sources, the use of data mining algorithms implemented as web services, as well as the use of formal descriptions of data sources and knowledge discovery tools in the form of ontologies, enabling automated composition of complex knowledge discovery workflows for a given data mining task. This paper proposes a novel Service-oriented Knowledge Discovery framework and its implementation in a service-oriented data mining environment Orange4WS (Orange for Web Services), based on the existing Orange data mining toolbox and its visual programming environment, which enables manual composition of data mining workflows. The new service-oriented data mining environment Orange4WS includes the following new features: simple use of web services as remote components that can be included into a data mining workflow; simple incorporation of relational data mining algorithms; a knowledge discovery ontology to describe workflow components (data, knowledge and data mining services) in an abstract and machine-interpretable way, and its use by a planner that enables automated composition of data mining workflows. These new features are showcased in three real-world scenarios.