Search

It is 12 years since I opened the discussion at the Royal Statistical Society meeting at which Rissanen and Wallace and Freeman presented companion papers on topics not far removed from those under discussion now. In the interim our understanding of the relationship between statistical inference, coding theory and algorithmic complexity has developed somewhat, but I feel there are still gaps to bridge. Rather than comment in detail on the current papers, I propose to use this opportunity to attempt a review of the whole area of stochastic complexity, or MDL, from a personal perspective. [ABSTRACT FROM PUBLISHER]

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue in order to bring the content 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. [ABSTRACT FROM AUTHOR]

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue in order to bring the content 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. [ABSTRACT FROM PUBLISHER]

The stream ciphers RCR-64 and RCR-32 designed by Sekar et al. are the most recent additions to the Py-family of stream ciphers, originally designed by Biham et al. The ciphers are among the fastest stream ciphers on software. To the best of our knowledge, the only reported attacks on the ciphers are due to Ding et al. , published in the Journal of Universal Computer Science. In this paper, we review these alleged attacks on the RCR ciphers and show that they are based on non-existent keystream biases stemming from flawed probability calculations. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This special issue contains four papers selected from the 26th UK Performance Engineering Workshop (UKPEW), which was held during 8–9 July 2010 in the Department of Computer Science at the University of Warwick. UKPEW is the leading UK forum for the presentation of work relating to all aspects of performance modelling and the analysis of computer and telecommunication systems. This year's selected papers demonstrate the variety of topics on offer at UKPEW: performance issues in cloud computing, energy-aware routing in packet networks, source location privacy and multi-hop ad hoc networks for wireless networks. [ABSTRACT FROM AUTHOR]

We would like to thank all the discussants for their contributions. Our paper attempts only a first step towards a satisfactory linkage between complexity theory and coding-based inference and these discussions will help to blaze the paths for future exploration. We also take this opportunity to remind the reader that, in our opinion, MDL and MML agree on many, many points. While we certainly disagree with Dr Rissanen and he with us on quite a few points, we certainly acknowledge that these disagreements would understandably appear both infrequent and minor from the perspective of someone who knew relatively little about MDL and MML. [ABSTRACT FROM PUBLISHER]

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue in order to bring 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. [ABSTRACT FROM AUTHOR]

Signposts make complex documents more flexible and easier to read; signposts exist in many forms, but are familiar as cross references and as hypertext links. Signposting systems need to be carefully designed, so that they are reliable, easy to use for readers yet convenient for authors to embed in their writing. There are fundamental problems in achieving good signposting, which this paper explores through cross-referencing in the popular medium of LaTeX, which is often the typesetting system of choice for heavily cross-referenced documents. This paper provides an implementation of cross references for LaTeX users. Problems with LaTeX and TeX arise, and are explored and mostly solved: some problems are due to the designs of these systems, but, crucially, some problems are unavoidable, an inevitable part of signposting in principle, whatever systems are used, even including the web. [ABSTRACT FROM AUTHOR]

Artificial intelligence is one of the most trending topics in the field of Computer Science which aims to make machines and computers 'smart'. There are multiple diverse technical and specialized research associated with it. Due to the accelerating rate of technological changes, artificial intelligence has taken over a lot of human jobs and is giving excellent results that are more efficient and effective, than humans. However, a lot of time there has been a concern about the following: will artificial intelligence surpass human intelligence in the near future? Are computers' ever accelerating abilities to outpace human jobs and skills a matter of concern? The different views and myths on the subject have made it even a more than just a topic of discussion.   In this research paper, we will study the existing facts and literature to understand the true definitions of artificial intelligence (AI) and human intelligence (HI) by classifying each of its types separately and analyzing the extent of their full capabilities. Later, we will discuss the possibilities if AI eventually can replace human jobs in the market. Finally, we will synthesize and summarize results and findings of why artificial intelligence cannot surpass human intelligence completely in the future. [ABSTRACT FROM AUTHOR]

This special issue includes research papers related to a workshop held at the Royal Society on 21st of September 2010, honouring Erol Gelenbe on his 65th birthday. The workshop brought together some 40 participants including some of Erol's former and current PhD students, colleagues and friends with whom he has interacted over the years, both in Europe and the USA. The papers focus on probability models in computer science, at the core of the field of computer performance engineering, which Erol pioneered. [ABSTRACT FROM AUTHOR]

Affine equivalence of Boolean functions has various applications in computer science and modern cryptography, such as circuit design and S-boxes. Existing methods for detecting affine equivalence of Boolean functions work in some cases but not when the truth table of a Boolean function is sparse. To improve previous methods and overcome this limitation, we propose a method by transforming the Boolean function to a function with the property that its function values at the orthonormal basis are all equal to 1 or 0, which narrows down the search space of affine transformations. Our first algorithm has the advantage of getting a smaller search space than previous methods and is especially useful for sparse functions. Specifically, when the Boolean functions are sparse, the search space can be reduced exponentially in average and experiments show the efficiency of our first algorithm. We then present another algorithm to transform one circuit into its equivalent affine circuit by synthesizing a reversible circuit and inserting it in front of the original circuit. To our knowledge, this is the first work to automatically synthesize an affine equivalent circuit for any given circuit and the first to do this by combining reversible circuit and non-reversible circuit. [ABSTRACT FROM AUTHOR]

The article presents abstracts on computer software topics which include the development of computer science, the applications of finite automata computer regular languages, and perfect algorithm for data mining.

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue in order to bring 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. [ABSTRACT FROM AUTHOR]

The mixing time of random walks on a graph has found broad applications across both theoretical and practical aspects of computer science, with the application effects depending on the behavior of mixing time. It is extensively believed that real-world networks, especially social networks, are fast mixing with their mixing time at most |$O(\log N)$| where |$N$| is the number of vertices. However, the behavior of mixing time in the real-life networks has not been examined carefully, and exactly analytical research for mixing time in models mimicking real networks is still lacking. In this paper, we first experimentally evaluate the mixing time of various real-world networks with scale-free small-world properties and show that their mixing time is much higher than anticipated. To better understand the behavior of the mixing time for real-world networks, we then analytically study the mixing time of the Apollonian network, which is simultaneously scale-free and small-world. To this end, we derive the recursive relations for all eigenvalues, especially the second largest eigenvalue modulus of the transition matrix, based on which we deduce a lower bound for the mixing time of the Apollonian network, which approximately scales sublinearly with |$N$|⁠. Our results indicate that real-world networks are not always fast mixing, which has potential implications in the design of algorithms related to mixing time. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue in order to bring the content 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 Science at Heriot-Watt University, Edinburgh, UK. [ABSTRACT FROM AUTHOR]

Synchronizations frequently occur in the modeling and design of distributed and concurrent systems. Designing a correct system from subsystems by considering the synchronizations of events is a difficult and complex task because it often destroys some desirable properties of subsystems and induces the whole system deadlocks. This paper formulates a property-preserving transition-reduction transformation to handle the synchronization problem in Petri net-based system design. It starts by designing correct subsystems without taking transition-reduction consideration. Synchronizations are then introduced by merging transitions of subsystems. Depending on the structure of transitions, two classes of transition-reductions are investigated. For each class, this paper shows that many structural and behavior properties can be preserved. [ABSTRACT FROM AUTHOR]

Caches hide the growing latency of accesses to the main memory from the processor by storing the most recently used data on-chip. To limit the search time through the caches, they are organized in a direct mapped or set-associative way. Such an organization introduces many conflict misses that hamper performance. This paper studies randomizing set index functions, a technique to place the data in the cache in such a way that conflict misses are avoided. The performance of such a randomized cache strongly depends on the randomization function. This paper discusses a methodology to generate randomization functions that perform well over a broad range of benchmarks. The methodology uses profiling information to predict the conflict miss rate of randomization functions. Then, using this information, a search algorithm finds the best randomization function. Due to implementation issues, it is preferable to use a randomization function that is extremely simple and can be evaluated in little time. For these reasons, we use randomization functions where each randomized address bit is computed as the XOR of a subset of the original address bits. These functions are chosen such that they operate on as few address bits as possible and have few inputs to each XOR. This paper shows that to index a 2m-set cache, it suffices to randomize in + 2 or m + 3 address bits and to limit the number of inputs to each XOR to 2 bits to obtain the full potential of randomization. Furthermore, it is shown that the randomization function that we generate for one set of benchmarks also works well for an entirely different set of benchmarks. Using the described methodology, it is possible to reduce the implementation cost of randomization functions with only an insignificant loss in conflict reduction. [ABSTRACT FROM AUTHOR]

This paper considers the problem of testing a deterministic system against a non-deterministic finite-state machine. An adaptive test process, with two phases, is proposed. The paper focuses on the first stage which involves testing to generate a candidate deterministic finite-state machine. This candidate has the property that, under the test hypotheses used, the implementation is correct if and only if it is equivalent to the candidate. A test may then be derived from the candidate. [ABSTRACT FROM AUTHOR]

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue, in order to bring the content to a wider readership. This issue's Capsule Reviews were compiled by Fairouz Kamareddine. Professor Kamareddine is an Associate Editor of The Computer Journal and is based in the School of Mathematical and Computer Sciences at Heriot-Watt University, Edinburgh, UK. [ABSTRACT FROM PUBLISHER]

Due to the increasing scale and complexity of software products, software maintenance especially on bug resolution has become a challenging task. Generally in large-scale software programs, developers depend on software artifacts (e.g., bug report, source code and change history) in bug repositories to complete the bug resolution task. However, a mountain of submitted bug reports every day increase the developers' workload. Therefore, 'How to effectively resolve software defects by utilizing software artifacts?' becomes a research hotspot in software maintenance. Considerable studies have been done on bug resolution by using multi-techniques, which cover data mining, machine learning and natural language processing. In this paper, we present a literature survey on tasks, challenges and future directions of bug resolution in software maintenance process. Our investigation concerns the most important phases in bug resolution, including bug understanding, bug triage and bug fixing. Moreover, we present the advantages and disadvantages of each study. Finally, based on the investigation and comparison results, we propose the future research directions of bug resolution. [ABSTRACT FROM AUTHOR]

The prevalence of heterogeneous manycore processors has been shown as a promising alternative to web-based data parallel MapReduce applications. The differences of manycore from multicore raise new challenges to designing and implementing efficient and scalable MapReduce applications, such as memory access congestion. This paper argues that it is more efficient using multiple small groups of cores than using a single group with all cores to address these challenges. We propose a group-based MapReduce implementation, called Grouped-MapReduce (GMR). It uses grouping to align tasks so that the tasks in each group are congestion-free. Further, it uses multiplexing to control the implementation of groups so that multiple groups can efficiently share the limited memory bandwidth without causing serious memory access congestion. We have implemented a prototype of GMR based on Phoenix++, an already highly optimized MapReduce runtime. Experiments on six benchmarks show that GMR implements and scales well on manycore systems and obtains an impressive improvement over Phoenix++ from 1.04x to 1.77x without artificially tuning the existing application code. [ABSTRACT FROM AUTHOR]

To solve the problem of group task allocation with time constraints in open and dynamic network environments, this paper proposes a decentralized combinatorial auction-based approach for group task allocation. In the proposed approach, both resource providers and consumers are modeled as intelligent agents. The proposed approach is decentralized, so all the agents are limited to communicating with their neighboring agents. The proposed approach also allows agents to enter and leave the network environments freely, and is robust for the dynamism and openness of the network environments. Tasks in the proposed approach have deadlines, and may need the collaboration of a group of self-interested providers. The experimental results demonstrate that the proposed approach outperforms two well-known task allocation approaches in terms of success rate of task allocation, the individual utility of the agents, the speed of task allocation and scalability. [ABSTRACT FROM AUTHOR]

This special issue focuses on Discovery Science (DS), which is a scientific discipline on any discovery process that is mainly approached by computer science. DS first started as a national project in Japan involving more than 100 researchers in 1998 and the project gave birth to a series of international conferences on DS, which have been held successfully every year since 1998. The objective of this special issue is to provide a leading forum for timely, in-depth presentation of recent advances in algorithms, theories and applications in the field of DS. Seven papers, ranging in a spectrum from basic theoretical research to solid application research, are included in this special issue. [ABSTRACT FROM PUBLISHER]

The Capsule Reviews are intended to provide a short succinct review of each paper in the issue in order to bring 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. [ABSTRACT FROM AUTHOR]

Confidentiality, integrity and availability, while being key requirements for ensuring security, have had limitations in providing an integral security model that incorporates the benefits of all predominant designs. Heeding to the call that security models cater to unique operational characteristics of individual firms, this paper presents a deep structure framework of information systems (ISs) security. The framework incorporates three models—representational model, which identifies subsystems within an organization; state-tracking model, which ensures that different states trace IS security in the real world;nd the decomposition model, which defines specific external events that are a stimuli to changes in internal events. In a final synthesis, the paper presents a deep structure-based conceptual clarity that manifests the meaning of dynamic, custom-fit and flexible IS security solutions. [ABSTRACT FROM AUTHOR]

This paper studies semantic efficiency measures for ambient intelligence. We follow an agent-based approach and investigate how large quantities of information can be efficiently handled. We will show how to dynamically set up a communication network between agents, which aims to minimize the communication load. The approach is based on a formal ontological notion of informativeness, on quantitative measures such as information gain and on the proper use of interaction mechanisms such as Publish/Subscribe. We also present experimental results that were obtained using our prototyping tool called Ubismart. [ABSTRACT FROM PUBLISHER]

A policy for a minimal reactive agent is a set of condition-action rules used to determine its response to perceived environmental stimuli. When the policy pre-disposes the agent to achieving a stipulated goal we call it a teleo-reactive policy. This paper presents a framework for constructing and evaluating teleo-reactive policies for one or more minimal agents, based upon discounted-reward evaluation of policy-restricted subgraphs of complete situation graphs. The main feature of the method is that it exploits explicit associations of the agent's perceptions with states. The framework allows to construct and evaluate policies for a number of cooperating agents by focusing upon the behaviour of a single representative of them. This abstraction ameliorates the potential combinatorial burden. Within the framework varied behaviours can be modelled, including communication between agents. Simulation results presented here indicate that the method affords a good degree of predictive power. The paper presents two different branch and bound algorithms used to optimize policy evaluation. [ABSTRACT FROM PUBLISHER]

Energy efficiency is increasingly important for future information and communication technologies (ICT), because the increased usage of ICT, together with increasing energy costs and the need to reduce green house gas emissions call for energy-efficient technologies that decrease the overall energy consumption of computation, storage and communications. Cloud computing has recently received considerable attention, as a promising approach for delivering ICT services by improving the utilization of data centre resources. In principle, cloud computing can be an inherently energy-efficient technology for ICT provided that its potential for significant energy savings that have so far focused on hardware aspects, can be fully explored with respect to system operation and networking aspects. Thus this paper, in the context of cloud computing, reviews the usage of methods and technologies currently used for energy-efficient operation of computer hardware and network infrastructure. After surveying some of the current best practice and relevant literature in this area, this paper identifies some of the remaining key research challenges that arise when such energy-saving techniques are extended for use in cloud computing environments. [ABSTRACT FROM PUBLISHER]

In this paper, we introduce a new side-channel attack using block cipher cryptanalysis named a meet-in-the-middle attack. Using our new side-channel technique we show that advanced encryption standard (AES) with reduced 10 masked rounds is broken, which is faster than the exhaustive key search attack. This implies that one has to mask the entire rounds of the 12-round 192-bit key AES to prevent our attacks. Our result is the first one to analyse AES with reduced 10 masked rounds, while the previous best known side-channel attack is on AES with reduced eight masked rounds. [ABSTRACT FROM PUBLISHER]

Current computer architecture research relies heavily on architectural simulation to obtain insight into the cycle-level behavior of modern microarchitectures. Unfortunately, such architectural simulations are extremely time-consuming. Sampling is an often-used technique to reduce the total simulation time. This is achieved by selecting a limited number of samples from a complete benchmark execution. One important issue with sampling, however, is the unknown hardware state at the beginning of each sample. Several approaches have been proposed to address this problem by warming up the hardware state before each sample. This paper presents the boundary line reuse latency (BLRL) which is an accurate and efficient warmup strategy. BLRL considers reuse latencies (between memory references to the same memory location) that cross the boundary line between the pre-sample and the sample to compute the warmup that is required for each sample. This guarantees a nearly perfect warmup state at the beginning of a sample. Our experimental results obtained using detailed processor simulation of SPEC CPU2000 benchmarks show that BLRL significantly outperforms the previously proposed memory reference reuse latency (MRRL) warmup strategy. BLRL achieves a warmup that is only half the warmup for MRRL on average for the same level of accuracy. [ABSTRACT FROM PUBLISHER]

One approach to formally specifying a system is to use a form of extended finite-state machine called a stream X-machine. A stream X-machine is a type of X-machine that describes a system as a finite set of states, each with an internal store, called memory, and a number of transitions between the states. A stream X-machine may be modelled by a finite automaton (the associated finite automaton) in which the arcs are labelled by function names (the processing functions). One important problem that may appear in the specification process is to find a 'minimal' (in some sense) stream X-machine that specifies the required functionality. This paper investigates the minimality issue in the context of deterministic stream X-machines and considers two types of minimality: state-minimal stream X-machine with respect to φ and minimal cover with respect to φ where φ is the set of processing functions that the machine may use. [ABSTRACT FROM AUTHOR]

An introduction is presented in which the editor discusses on various reports within the issue on topics including the compression effectiveness of PPM mechanism, the use of codes as a function of statistical observation, and the use of co-operating pair of compressors.

Many techniques in many diverse areas in computer science, such as process modelling, process programming, decision support systems and workflow systems, use concepts for the specification of process control. These typically include concepts for the specification of sequential execution, parallelism, synchronization and moments of choice. This paper identifies some typical verification problems in process control specifications, such as reachability, termination, freedom of deadlock and livelock, and determines their computational complexity. These results then provide computational lower bounds for any technique using these concepts for process control. [ABSTRACT FROM PUBLISHER]

Digital forensics is a recently emerged research area, and it has attracted the attention of computer professionals, law enforcement experts and practitioners. It is a multidisciplinary area that includes multiple fields, i.e. law, computer science, finance, networking, data mining and criminal justice. We believe that papers enclosed in this Special Issue will enhance knowledge in digital forensics and will stimulate further research in the important areas of information and network security. [ABSTRACT FROM PUBLISHER]

The motif discovery problem (MDP) is an important biological optimization problem that has been addressed in numerous ways. However, it is important to note that when we address real complex optimization problems, we should adequately formulate them in order to provide real applicability to the developed techniques. In the particular case of MDP, as we do not know the size of the motifs and the number of repetitions that can be found in the sequences, we must not make any length or pattern-repetition assumptions. In addition, if we consider that it is practically impossible to adequately formulate an optimization problem with a single-objective function formulation, multiobjective optimization can be a good methodology to be considered. In this paper, we propose a novel hybrid multiobjective algorithm for tackling the MDP. Our main objective is to study the results achieved by our algorithm, analysing its performance when different motif occurrence models are considered. As we will see, experimental results on different sets of real instances will point out the advantages and disadvantages of each model, also checking how a more realistic definition of the optimized problem provides better quality biological results. [ABSTRACT FROM AUTHOR]

Reversible data hiding (RDH) algorithms are concerned with the recovery of the original cover image upon the extraction of the secret data. In some RDH algorithms, embedding and extraction are performed through modifying the histogram of prediction errors that are computed using certain predictors. However, the embedding capacity and image quality in these algorithms are dependent on the characteristics of a single predictor. In this paper, we propose the idea of employing multiple predictors in order to increase the embedding capacity. The idea of multiple predictors is integrated in the modification of prediction errors algorithm without adding any overhead regarding the predictor that is used for embedding at each pixel in the image. The selection of the accurate predictor depends on the polarity of the prediction errors from all predictors. Experimental results proved the efficiency of the proposed algorithm in terms of increasing the embedding capacity and producing competitive quantitative and qualitative quality of the stego image when compared with recent algorithms. [ABSTRACT FROM AUTHOR]

Presents abstracts of articles concerning computer science, published in the May 2003 issue of the 'Journal of Computer.' 'Representation of Web data in a Web Warehouse,' by S.S. Bhowmick, S. Madria and W.K. Ng; 'A Type-Passing Approach for the Implementation of Parametric Methods in Java,' by M. Viroli.

This section presents a review of several papers on computer science. They include "Hardware-Oriented Algorithms for Rendering Order-Independent Transparency," by M. Amor, M. Bóo, E. J. Padrón, and D. Bartz, "Instruction-Level Parallelism Through Microthreading--A Scalable Approach to Chip Multiprocessors," by K. Bousias, N. Hasasneh, and C. Jesshope, and "Using Control Dependencies for Space-Aware Bytecode Verification," by C. Bernardeschi, G. Lettieri, L. Martini, and P. Masci.

IEEE 802.22 wireless regional area network (WRAN) is a cognitive radio-based network. WRANs are intended to be deployed by different service providers and designed to opportunistically utilize the unused TV bands. WRANs have to self-coexist with other overlapped WRANs in a distributed manner. Therefore, every service provider tries to acquire a band free of interference from others to satisfy a required quality of service. This self-coexistence problem is one of the major challenges in WRAN. In this paper, we propose a Markov-based distributed approach for mitigating this problem. We model the problem as an absorbing discrete-time Markov chain. In this model, if two or more overlapped WRANs select the same band, then each one should either stay or switch to another band according to a certain switching probability. This process continues until each one of the WRANs finds an interference-free band. In this case, the Markov chain reaches the absorbing state. This model is employed to find the optimal switching probability, which in turn minimizes the time required to reach the absorbing state. The switching probability is numerically found as a function of the number of overlapped WRANs and available bands. Extensive simulation has been conducted to validate our numerical results. [ABSTRACT FROM PUBLISHER]

Nowadays, networks are almost ubiquitous. In the past decade, community detection received an increasing interest as a way to uncover the structure of networks by grouping nodes into communities more densely connected internally than externally. Yet most of the effective methods available do not consider the potential levels of organization, or scales, a network may encompass and are therefore limited. In this paper, we present a method compatible with global and local criteria that enables fast multi-scale community detection on large networks. The method is derived in two algorithms, one for each type of criterion, and implemented with six known criteria. Uncovering communities at various scales is a computationally expensive task. Therefore, this work puts a strong emphasis on the reduction of computational complexity. Some heuristics are introduced for speed-up purposes. Experiments demonstrate the efficiency and accuracy of our method with respect to each algorithm and criterion by testing them against large generated multi-scale networks. This study also offers a comparison between criteria and between the global and local approaches. In particular, our results suggest that global criteria seem to be more robust to noise and thus more accurate than local criteria. [ABSTRACT FROM PUBLISHER]

While multi-label classification can be widely applied for problems where multiple classes can be assigned to an object, its effectiveness may be sacrificed due to curse of dimensionality in the feature space and sparseness of dimensionality in the label space. As a solution, this paper presents two alternative methods, namely Dependent Dual Space Reduction and Independent Dual Space Reduction, to reduce dimensions in the dual spaces, i.e. the feature and label spaces, using singular value decomposition (SVD). The first approach constructs the cross-covariance matrix to represent dependency between the features and labels, projects both of them into a single reduced space, and then performs prediction on the reduced space. On the other hand, the second approach handles the feature space and the label space separately by constructing a covariance matrix for each space to represent feature dependency and label dependency before performing SVD on dependency profile of each space to reduce dimension and for noise elimination and then predicting classes using their reduced dimensions. A number of experiments show that prediction on the reduced spaces for both dependent and independent reduction approaches can obtain better classification accuracy as well as faster computation, compared with the prediction using the original spaces. Finally, the results of our methods are also compared with the prediction using other types of dimensionality reduction, with consideration of the factors of covariance and threshold selection. [ABSTRACT FROM PUBLISHER]

Linkable ring signatures have found many attractive applications. One of the recent important extensions is a linkable threshold ring signature (LTRS) scheme. Unfortunately, the existing LTRS schemes are only secure in the random oracle model (ROM). In this paper, we make the following contributions. First, we construct the first LTRS scheme that is secure without requiring the ROM. Further, we enhance the security of a threshold ring signature (for both linkable or non-linkable) by providing a stronger definition of anonymity. This strengthened notion makes threshold ring signature schemes more suitable in real life. Finally, we provide efficient schemes that outperform the existing schemes in the literature. Our scheme is particularly suitable for electronic commerce or electronic government where anonymity and accountability are the most concerned factors. [ABSTRACT FROM PUBLISHER]

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(n2)–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. [ABSTRACT FROM AUTHOR]

Composing large enterprise applications from reusable software components has become a major software development technique. Components are considered as black boxes and are composed together by their provided and required services. In comparison to other software development approaches, this allows for rapid development, clean and explicit architectures, and easy component reuse. Currently, there are several systems that support development and composition of components: service component architecture and Fractal are two well-known ones. At first sight, both have the same goals and provide very similar means to developers. In this paper, we briefly present both systems and then we focus on an in-depth comparison and evaluation of them. [ABSTRACT FROM AUTHOR]

This paper presents new algorithms for generating all n-node t-ary trees in linked representation which take constant average time per tree. They use fewer memory references and are considerably faster than previous such algorithms. [ABSTRACT FROM AUTHOR]

Applications of modal logics are abundant in computer science, and a large number of structurally different modal logics have been successfully employed in a diverse spectrum of application contexts. Coalgebraic semantics, on the other hand, provides a uniform and encompassing view on the large variety of specific logics used in particular domains. The coalgebraic approach is generic and compositional: tools and techniques simultaneously apply to a large class of application areas and can, moreover, be combined in a modular way. In particular, this facilitates a pick-and-choose approach to domain-specific formalisms, applicable across the entire scope of application areas, leading to generic software tools that are easier to design, to implement and to maintain. This paper substantiates the authors’ firm belief that the systematic exploitation of the coalgebraic nature of modal logic will not only have impact on the field of modal logic itself but also lead to significant progress in a number of areas within computer science, such as knowledge representation and concurrency/mobility. [ABSTRACT FROM AUTHOR]

In this paper we discuss the use of the social concept ‘conviviality’ for computer science in general, and for the development of ambient technologies in particular. First, we give a survey of the use of the concept ‘conviviality’ in the social sciences. Conviviality is usually considered a positive concept related to sociability. However, further analysis reveals a negative side related to lack of diversity, privacy and ethical issues. Second, we argue that conviviality requirements for ambient intelligence are challenging, because ambient technologies give rise to a new virtual and social reality, and conviviality issues play a central role in applications that are concerned with the interaction of material, virtual and social realities. Conviviality highlights an important challenge that we illustrate with examples that emphasize ethical issues, such as privacy threats, surveillance of users and identity theft. Intelligent interfaces, for example, allow instant interactions and thereby create strong needs for coordination and regulation mechanisms that have to be addressed to ensure the safeguard of individuals against abuses, such as privacy intrusions and identity manipulations. Third, we propose a conviviality ontology by operationalizing the fuzzy concept of ‘conviviality,’ such that it can be used in computer science in the same way as other social concepts such as ‘service,’ ‘contract’ or ‘trust’ are used in this area. Conviviality is defined using dependence networks, and tools for conviviality are based on, what we call, conviviality masks. Fourth, we illustrate how convivial ambient intelligence applications can be designed using our operationalized concept of conviviality. We illustrate our arguments and contributions with a running example on the use of ambient technologies in digital cities, as a prototypical example where material reality such as ambient technologies interacts with virtual and social realities. [ABSTRACT FROM PUBLISHER]