Search

International audience; Aged macular degeneration (AMD) leads to a progressive decline in visual acuity until reaching blindness. It is considered as an irreversible pathology where an early diagnosis remains crucial. However, the lack of ophthalmologists, the permanent increase in elderly people, and their limited mobility involves a delay in AMD diagnosis. In this paper, we propose an automated method for AMD screening. The proposed processing pipeline consists in applying the well-known Radon transform to the macula region in order to model the AMD lesions even with a moderate quality of smartphone-captured fundus images. Thereby, the relevant features are carefully selected, related to the main proprieties of drusens, and then provided to an SVM classifer. The implementation of the method into a smartphone associated to a fundus image capturing device leads to a mobile CAD system that performs higher performance AMD screening. Within this framework and to achieve a real-time implementation, an optimization approach is suggested in order to reduce the processing workload. The evaluation of our method is carried out through the three public STARE, REFUGE, and RFMiD databases. A 4-fold cross-validation approach is used to evaluate the method performance where accuracies of 100%, 95.2%, and 94.3% are respectively obtained with STARE, REFUGE, and RFMiD databases. Comparisons with the state-of-the-art methods in the literature are done. Thereafter, the robustness of the proposed method was evaluated and proved. We note that 100% accuracy was preserved despite the use of degraded quality fundus images as noisy and blurred. Moreover, the propounded method was implemented in S7-Edge and S9 Smartphone devices, where the execution times of 19 and 15 milliseconds were respectively achieved, which proves the AMD real-time detection. Taking advantage of its mobility, cost-efective, detection performance, andreduced execution time, our proposed method seems a good solution for real-time AMD screening on mobile devices.

12th International Symposium on Parameterized and Exact Computation (IPEC 2017); International audience; Given a graph G, we define bcg(G) as the minimum k for which G can be contracted to the uniformly triangulated grid Γk. A graph class G has the SQGC property if every graph G ∈ G has treewidth O(bcg(G)c) for some 1 ≤ c < 2. The SQGC property is important for algo- rithm design as it defines the applicability horizon of a series of meta-algorithmic results, in the framework of bidimensionality theory, related to fast parameterized algorithms, kernelization, and approximation schemes. These results apply to a wide family of problems, namely problems that are contraction-bidimensional. Our main combinatorial result reveals a general family of graph classes that satisfy the SQGC property and includes bounded-degree string graphs. This considerably extends the applicability of bidimensionality theory for several intersection graph classes of 2-dimensional geometrical objects.

International audience; In the localization game, introduced by Seager in 2013, an invisible and immobile target is hidden at some vertex of a graph $G$. At every step, one vertex $v$ of $G$ can be probed which results in the knowledge of the distance between $v$ and the secret location of the target. The objective of the game is to minimize the number of steps needed to locate the target whatever be its location.We address the generalization of this game where $k\geq 1$ vertices can be probed at every step. Our game also generalizes the notion of the {\it metric dimension} of a graph.Precisely, given a graph $G$ and two integers $k,\ell \geq 1$, the {\sc Localization} problem asks whether there exists a strategy to locate a target hidden in $G$ in at most $\ell$ steps and probing at most $k$ vertices per step. We first show that, in general, this problem is \textsf{NP}-complete for every fixed $k \geq 1$ (resp., $\ell \geq 1$).We then focus on the class of trees.On the negative side,we prove that the \Localization problem is \textsf{NP}-complete in trees when $k$ and $\ell$ are part of the input. On the positive side, we design a $(+1)$-approximation algorithm for the problem in $n$-node trees, {\it i.e.}, an algorithm that computes in time $O(n \log n)$ (independent of $k$) a strategy to locate the target in at most one more step than an optimal strategy. This algorithm can be used to solve the \Localization problem in trees in polynomial time if $k$ is fixed.We also consider some of these questions in the context where, upon probing the vertices,the relative distances to the target are retrieved.This variant of the problem generalizes the notion of the {\it centroidal dimension} of a graph.

International audience; This paper presents a new consensus algorithm, Proof of Usage (PoU), for the blockchain technology. This consensus is introduced for permis-sioned (or private) blockchains and is designed for a user-centric personal data market. This market is subject to specific regulations with which conventional blockchains fail to comply. Proof of Usage aims to promote a new paradigm dedicated to usage incentivization, valuation, and control of user data in various sectors, such as banking and insurance. Other consensuses such as Proof of Stake or historical Proof of Work do not encourage coin spending and usage (in fact, Proof of Stake promotes the opposite). However, the value of the currency mainly depends on its use. This paper first introduces a contextualization of blockchain technology and decentralized consensus models. The motivation is then discussed for a new model of personal data exchange in a decentralized but supervised environment. The PoU protocol and its process flow are defined in detail. Furthermore, the paper explores two different approaches regarding the reward mechanism and the incentive model. Finally, the paper focuses on security requirements and how PoU meets such requirements in a permissioned-based blockchain system.

The Capacitated Team Orienteering Problem (CTOP) is a variant of the well-known Team Orienteering Problem where additional capacity limitation constraints are considered for each vehicle. Solving CTOP consists of organizing a set of routes that maximize the total profit collected from the served customers while taking into consideration the capacity and travel time limitation for each vehicle. In this paper, we propose a variable space search heuristic to solve CTOP. Our algorithm alternates between two search spaces: the giant tour and routes search spaces. We develop a hybrid heuristic as a framework for our algorithm composed of a combination between Greedy Randomized Adaptive Search Procedure and Evolutionary Local Search. Several local search techniques were developed in each search space to improve the quality of the solutions and the giant tours. A dedicated optimal split procedure and a concatenation technique are performed to ensure the link between the search spaces. This approach shows its high performance on the benchmark of CTOP, and proves its competitiveness in comparison to the other heuristic methods available in the literature as it yields to strict improvements with small computational time.

Continuous-in-scale multifractal cascades has long been an attractive choice for mathematically modeling turbulent and turbulent-like geophysical fields. These fields are usually anisotropic as they are subject to both stratification and rotation, thereby questioning the isotropy assumption often made to model them. The self-affine and generalized scale invariance approaches to scaling are used here to introduce anisotropy in such models. These anisotropic simulations have (1) unresolved large-scale features and (2) statistics that deviate from the desired power-law scaling mainly in the small scales. The former issue is solved via nesting, whereas the latter is attempted to be overcome using singularity correction methods. While earlier studies have proposed isotropic correction methods, here they have been generalized to correct anisotropic simulations. These singularity corrections seem to improve the small-scale statistical properties of mildly anisotropic simulations; nesting, on the other hand, appears to enhance statistics over almost all scales even for strongly anisotropic simulations. Both the correction and nesting techniques lead to a reduction in computational time and memory usage suggesting that nested singularity-corrected cascades offer a better framework for quantitatively modeling the atmosphere, ocean, solid earth, and associated fields.

International audience; Computing discrete logarithms is generically a difficult problem. For divisor class groups of curves defined over extension fields, a variant of the Index-Calculus called Decomposition attack is used, and it can be faster than generic approaches. In this situation, collecting the relations is done by solving multiple instances of the Point m-Decomposition Problem (PDP$_m$). An instance of this problem can be modelled as a zero-dimensional polynomial system. Solving is done with Gröbner bases algorithms, where the number of solutions of the system is a good indicator for the time complexity of the solving process. For systems arising from a PDP$_m$ context, this number grows exponentially fast with the extension degree. To achieve an efficient harvesting, this number must be reduced as much as as possible. Extending the elliptic case, we introduce a notion of Summation Ideals to describe PDP m instances over higher genus curves, and compare to Nagao's general approach to PDP$_m$ solving. In even characteristic we obtain reductions of the number of solutions for both approaches, depending on the curve's equation. In the best cases, for a hyperelliptic curve of genus $g$, we can divide the number of solutions by $2^{(n−1)(g+1)}$. For instance, for a type II genus 2 curve defined over $\mathbb{F}_{2^{93}}$ whose divisor class group has cardinality a near-prime 184 bits integer, the number of solutions is reduced from 4096 to 64. This is enough to build the matrix of relations in around 7 days with 8000 cores using a dedicated implementation.

Linear rank-width is a linearized variation of rank-width, and it is deeply related to matroid path-width. In this paper, we show that the linear rank-width of every $n$-vertex distance-hereditary graph, equivalently a graph of rank-width at most $1$, can be computed in time $\mathcal{O}(n^2\cdot \log_2 n)$, and a linear layout witnessing the linear rank-width can be computed with the same time complexity. As a corollary, we show that the path-width of every $n$-element matroid of branch-width at most $2$ can be computed in time $\mathcal{O}(n^2\cdot \log_2 n)$, provided that the matroid is given by an independent set oracle. To establish this result, we present a characterization of the linear rank-width of distance-hereditary graphs in terms of their canonical split decompositions. This characterization is similar to the known characterization of the path-width of forests given by Ellis, Sudborough, and Turner [The vertex separation and search number of a graph. Inf. Comput., 113(1):50--79, 1994]. However, different from forests, it is non-trivial to relate substructures of the canonical split decomposition of a graph with some substructures of the given graph. We introduce a notion of `limbs' of canonical split decompositions, which correspond to certain vertex-minors of the original graph, for the right characterization., Comment: 28 pages, 3 figures, 2 table. A preliminary version appeared in the proceedings of WG'14

International audience; The organizations of insect societies, such as division of labor, task allocation , collective regulation, mass action responses, have been considered as main reasons for the ecological success. In this article, we propose and study a general modeling framework that includes the following three features: (a) the average internal response threshold for each task (the internal factor); (b) social network communications that could lead to task switching (the environmental factor); and (c) dynamical changes of task demands (the external factor). Since workers in many social insect species exhibit age polyethism, we also extend our model to incorporate age polyethism in which worker task preferences change with age. We apply our general modeling framework to the cases of two task groups: the inside colony task versus the outside colony task. Our analytical study of the models provides important insights and predictions on the effects of colony size, social communication, and age-related task preferences on task allocation and division of labor in the adaptive dynamical environment. Our study implies that the smaller size colony invests its resource for the colony growth and allocates more workers in the risky tasks such as foraging while the larger colony shifts more workers to perform the safer tasks inside the colony. 123 880 Y. Kang, G. Theraulaz Social interactions among different task groups play an important role in shaping task allocation depending on the relative cost and demands of the tasks.

Estimating the number of triangles in graph streams using a limited amount of memory has become a popular topic in the last decade. Different variations of the problem have been studied, depending on whether the graph edges are provided in an arbitrary order or as incidence lists. However, with a few exceptions, the algorithms have considered {\em insert-only} streams. We present a new algorithm estimating the number of triangles in {\em dynamic} graph streams where edges can be both inserted and deleted. We show that our algorithm achieves better time and space complexity than previous solutions for various graph classes, for example sparse graphs with a relatively small number of triangles. Also, for graphs with constant transitivity coefficient, a common situation in real graphs, this is the first algorithm achieving constant processing time per edge. The result is achieved by a novel approach combining sampling of vertex triples and sparsification of the input graph. In the course of the analysis of the algorithm we present a lower bound on the number of pairwise independent 2-paths in general graphs which might be of independent interest. At the end of the paper we discuss lower bounds on the space complexity of triangle counting algorithms that make no assumptions on the structure of the graph., New version of a SWAT 2014 paper with improved results

International audience; Despite the obvious influence of space on interactions, constraints imposed by the built environment are seldom considered when examining collective behaviours of animals and humans. We propose an interdisciplinary path towards uncovering the impact of architecture on collective outcomes.

Consider a system of two polynomial equations in two variables: $$\begin{aligned} F(X,Y)=G(X,Y)=0, \end{aligned}$$F(X,Y)=G(X,Y)=0,where $$F \in \mathbb {R}[X,Y]$$F?R[X,Y] has degree $$d \ge 1$$d?1 and $$G \in \mathbb {R}[X,Y]$$G?R[X,Y] has $$t$$t monomials. We show that the system has only $$O(d^3t+d^2t^3)$$O(d3t+d2t3) real solutions when it has a finite number of real solutions. This is the first polynomial bound for this problem. In particular, the bounds coming from the theory of fewnomials are exponential in $$t$$t, and count only non-degenerate solutions. More generally, we show that if the set of solutions is infinite, it still has at most $$O(d^3t+d^2t^3)$$O(d3t+d2t3) connected components. By contrast, the following question seems to be open: if $$F$$F and $$G$$G have at most $$t$$t monomials, is the number of (non-degenerate) solutions polynomial in $$t$$t? The authors' interest for these problems was sparked by connections between lower bounds in algebraic complexity theory and upper bounds on the number of real roots of "sparse like" polynomials.

International audience; Given an undirected graph G = (V,E) and two positive integers k and d, we are interested in finding a set of edges (resp. non-edges) of size at most k to delete (resp. to add) in such a way that the chromatic number (resp. stability number) in the resulting graph will decrease by at least d compared to the original graph. We investigate these two problems in various classes of graphs (split graphs, threshold graphs, (complement of) bipartite graphs) and determine their computational complexity. In some of the polynomial-time solvable cases, we also give a structural description of a solution.

The k-Coloring problem is to decide whether a graph can be colored with at most k colors such that no two adjacent vertices receive the same color. The List k-Coloring problem requires in addition that every vertex u must receive a color from some given set L(u)⊆{1,?,k}. Let P n denote the path on n vertices, and G+H and rH the disjoint union of two graphs G and H and r copies of H, respectively. For any two fixed integers k and r, we show that List k-Coloring can be solved in polynomial time for graphs with no induced rP 1+P 5, hereby extending the result of Hoang, Kaminski, Lozin, Sawada and Shu for graphs with no induced P 5. Our result is tight; we prove that for any graph H that is a supergraph of P 1+P 5 with at least 5 edges, already List 5-Coloring is NP-complete for graphs with no induced H.

We show that the separation property fails for the classes Σ n of the Rabin-Mostowski index hierarchy of alternating automata on infinite trees. This extends our previous result (obtained with Szczepan Hummel) on the failure of the separation property for the class Σ 2 (i.e., for co-Buchi sets). The non-separation result is also adapted to the analogous classes induced by weak alternating automata. To prove our main result, we first consider the Rabin-Mostowski index hierarchy of deterministic automata on infinite words, for which we give a complete answer (generalizing previous results of Selivanov): the separation property holds for ? n and fails for Σ n -classes. The construction invented for words turns out to be useful for trees via a suitable game. It remains open if the separation property holds for all classes ? n of the index hierarchy for tree automata. To give a positive answer it would be enough to show the reduction property of the dual classes--a method well-known in descriptive set theory. We show that it cannot work here, because the reduction property fails for all classes in the index hierarchy.

International audience; Building a meaningful model of biological regulatory network is usually done by specifying the components (e.g. the genes) and their interactions, by guessing the values of parameters, by comparing the predicted behaviors to the observed ones, and by modifying in a trial-error process both architecture and parameters in order to reach an optimal fitness. We propose here a different approach to construct and analyze biological models avoiding the trial-error part, where structure and dynamics are represented as formal constraints. We apply the method to Hopfield-like networks, a formalism often used in both neural and regulatory networks modeling. The aim is to characterize automatically the set of all models consistent with all the available knowledge (about structure and behavior). The available knowledge is formalized into formal constraints. The latter are compiled into Boolean formula in conjunctive normal form and then submitted to a Boolean satisfiability solver. This approach allows to formulate a wide range of queries, expressed in a high level language, and possibly integrating formalized intuitions. In order to explore its potential, we use it to find cycles for 3-nodes networks and to determine the flower morphogenesis regulatory network of Arabidopsis thaliana. Applications of this technique are numerous and concern the building of models from data as well as the design of biological networks possessing specified behaviors.

International audience; Topology identification of complex networks is an important problem. Existing research shows that the synchronization of network nodes is an obstacle in the identification of network topology. Identification of the structure of the network presents an interesting challenge during the synchronization of complex networks. We developed a new method using the sinusoidal disturbance to identify the topology when the complex network achieves synchronization. Compared with the disturbance of all the nodes, the disturbance of the key nodes alone can achieve a very good effect. Finally, numerical simulation data are provided to validate our hypothesis.

Let $$(MQP)$$ be a general mixed-integer quadratic program that consists of minimizing a quadratic function $$f(x) = x^TQx +c^Tx$$ subject to linear constraints. Our approach to solve $$(MQP)$$ is first to consider an equivalent general mixed-integer quadratic problem. This equivalent problem has additional variables $$y_{ij}$$ , additional quadratic constraints $$y_{ij}=x_ix_j$$ , a convex objective function, and a set of valid inequalities. Contrarily to the reformulation proposed in Billionnet et al. (Math Program 131(1):381---401, 2012), the equivalent problem cannot be directly solved by a standard solver. Here, we propose a new Branch and Bound process based on the relaxation of the non-convex constraints $$y_{ij}=x_ix_j$$ to solve $$(MQP)$$ . Computational experiences are carried out on pure- and mixed-integer quadratic instances. The results show that the solution time of most of the considered instances with up to 60 variables is improved by our Branch and Bound algorithm in comparison with the approach of Billionnet et al. (2012) and with the general mixed-integer nonlinear solver BARON (Sahinidis and Tawarmalani, Global optimization of mixed-integer nonlinear programs, user's manual, 2010).

Clique-width is a complexity measure of directed as well as undirected graphs. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss an extension of the notion of rank-width to edge-colored graphs. A C-colored graph is a graph where the arcs are colored with colors from the set C. There is not a natural notion of rank-width for C-colored graphs. We define two notions of rank-width for them, both based on a coding of C-colored graphs by edge-colored graphs where each edge has exactly one color from a field F and named respectively F-rank-width and F-bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for F-colored graphs and prove that F-colored graphs of bounded F-rank-width are characterised by a finite list of F-colored graphs to exclude as vertex-minors. A cubic-time algorithm to decide whether a F-colored graph has F-rank-width (resp. F-bi-rank-width) at most k, for fixed k, is also given. Graph operations to check MSOL-definable properties on F-colored graphs of bounded rank-width are presented. A specialisation of all these notions to (directed) graphs without edge colors is presented, which shows that our results generalise the ones in undirected graphs., It is an update of the last version generalising all the results to edge-colored graphs and answering some of the raised questions

International audience; Collective decision-making is a process whereby the members of a group decide on a course of action by consensus. In this paper, we propose a collective decision-making mechanism for robot swarms deployed in scenarios in which robots can choose between two actions that have the same effects but that have different execution times. The proposed mechanism allows a swarm composed of robots with no explicit knowledge about the difference in execution times between the two actions to choose the one with the shorter execution time. We use an opinion formation model that captures important elements of the scenarios in which the proposed mechanism can be used in order to predict the system's behavior. The model predicts that when the two actions have different average execution times, the swarm chooses with high probability the action with the shorter average execution time. We validate the model's predictions through a swarm robotics experiment in which robot teams Electronic supplementary material The online version of this article (306 Swarm Intell (2011) 5:305–327 must choose one of two paths of different length that connect two locations. Thanks to the proposed mechanism, a swarm made of robot teams that do not measure time or distance is able to choose the shorter path.

The theory of analog computation aims at modeling computational systems that evolve in a continuous space. Unlike the situation with the discrete setting there is no unified theory of analog computation. There are several proposed theories, some of them seem quite orthogonal. Some theories can be considered as generalizations of the Turing machine theory and classical recursion theory. Among such are recursive analysis and Moore's class of recursive real functions. Recursive analysis was introduced by Turing (Proc Lond Math Soc 2(42):230---265, 1936), Grzegorczyk (Fundam Math 42:168---202, 1955), and Lacombe (Compt Rend l'Acad Sci Paris 241:151---153, 1955). Real computation in this context is viewed as effective (in the sense of Turing machine theory) convergence of sequences of rational numbers. In 1996 Moore introduced a function algebra that captures his notion of real computation; it consists of some basic functions and their closure under composition, integration and zero-finding. Though this class is inherently unphysical, much work have been directed at stratifying, restricting, and comparing it with other theories of real computation such as recursive analysis and the GPAC. In this article we give a detailed exposition of recursive analysis and Moore's class and the relationships between them.

DOI 10.1007 /s10479-009-0624-2 http://www.springerlink.com/content/j15506t4m7377312/; International audience; A fast realization of drugs is an important part in the quality of service of a hospital. In this paper we propose a scheduling method for the preparation of chemotherapy doses in order to reduce the patient waiting time. Two approaches have been defined: an off-line approach and a real time approach. The off-line approach is using a linear programming model for minimizing the maximum tardiness of jobs in a production day. This method is re-used during the real-time resolution combined with a greedy algorithm. The solution obtained respects constraints on the production center and the hospital organization. Our model is currently used in software which helps the decision maker of the service and allows increasing the patient satisfaction and the productivity of the service.

We introduce a new class VPSPACE of families of polynomials. Roughly speaking, a family of polynomials is in VPSPACE if its coefficients can be computed in polynomial space. Our main theorem is that if (uniform, constant-free) VPSPACE families can be evaluated efficiently then the class PAR of decision problems that can be solved in parallel polynomial time over the real numbers collapses to P. As a result, one must first be able to show that there are VPSPACE families which are hard to evaluate in order to separate over the reals P from NP, or even from PAR., Comment: Full version of the paper (appendices of the first version are now included in the text)

We study the following generalization of the classical edge coloring problem: Given a weighted graph, find a partition of its edges into matchings (colors), each one of weight equal to the maximum weight of its edges, so that the total weight of the partition is minimized. We explore the frontier between polynomial and NP-hard variants of the problem, with respect to the class of the underlying graph, as well as the approximability of NP-hard variants. In particular, we present polynomial algorithms for bounded degree trees and star of chains, as well as an approximation algorithm for bipartite graphs of maximum degree at most twelve which beats the best known approximation ratios.

We present an exactly solvable random-subcube model inspired by the structure of hard constraint satisfaction and optimization problems. Our model reproduces the structure of the solution space of the random k-satisfiability and k-coloring problems, and undergoes the same phase transitions as these problems. The comparison becomes quantitative in the large-k limit. Distance properties, as well the x-satisfiability threshold, are studied. The model is also generalized to define a continuous energy landscape useful for studying several aspects of glassy dynamics., Comment: 21 pages, 4 figures

The original publication is available at www.springerlink.com; International audience; Basic algorithms have been proposed in the field of low-power (Yao, F., et al. in Proceedings of lEEE annual foundations of computer science, pp. 374–382, 1995) which compute the minimum energy-schedule for a set of non-recurrent tasks (or jobs) scheduled under EDF on a dynamically variable voltage processor. In this study, we propose improvements upon existing algorithms with lower average and worst-case complexities. They are based on a new EDF feasibility test that helps to identify the “critical intervals”. The complexity of this feasibility test depends on structural characteristics of the set of jobs. More precisely, it depends on how tasks are included one in the other. The first step of the algorithm is to construct the Hasse diagram of the set of tasks where the partial order is defined by the inclusion relation on the tasks. Then, the algorithm constructs the shortest path in a geometrical representation at each level of the Hasse diagram. The optimal processor speed is chosen according to the maximal slope of each path.

This is a summary of the author’s PhD thesis supervised by Marie- Christine Costa and Frederic Roupin and defended on 20 November 2006 at the Conservatoire National des Arts et Metiers in Paris (France). The thesis is written in French and is available upon request from the author. This work deals with two well-known optimization problems from graph theory: the maximum integral multiflow and the minimum multicut problems. The main contributions of this thesis concern the polynomial-time solvability and the approximation of these two problems (and of some of their variants) in classical classes of graphs: bounded tree-width graphs, planar graphs and grids, digraphs, etc.

International audience; We discuss the main results of the author's PhD thesis (Canon 2005) presented in December 2005 at the Université François-Rabelais de Tours and supervised by J.-C. Billaut and J.-L. Bouquard. This thesis is written in French and is available from the author upon request. It deals with three different problems arising in the call center industry: the problem of dimensioning a call center, the annualisation problem and finally the Shift Design Problem.

This special issue contains four papers presented during the workshop "2nd International Workshop on Asynchronous Cellular Automata and Asynchronous Discrete Models" (ACA 2012), held at the 10th International Conference on Cellular Automata for Research and Industry (ACRI 2012) in Santorini Island (Greece) in the period September 24th-27th, 2012.

This special issue contains four papers presented during the workshop, ‘‘18th International Workshop on Cellular Automata and Discrete Complex Systems’’ (Automata 2012), held in La Marana, Corsica island (France) in the period September 19–21th, 2012. The aim of this workshop is to establish and maintain a permanent, international, multidisciplinary forum for the collaboration of researchers in the field of Cellular Automata (CA) and Discrete Complex Systems (DCS), provide a platform for presenting and discussing new ideas and results, and support the development of theory and applications of CA and DCS. Typical, but not exclusive, topics of the workshop are: dynamics aspects, algorithmic, computational and complexity issues, emergent properties, formal language processing, models of parallelism and distributed systems, phenomenological descriptions, scientific modeling and practical applications. After an additional review process, four papers were selected and included in this special issue. They are now presented in an extended and improved form with respect to the already refereed workshop version that appeared in the proceedings of Automata 2012. The paper ‘‘Computation of Functions on n Bits by Asynchronous Clocking Cellular Automata’’ by Michael Vielhaber aims at proving that different functions on binary vectors can be computed by changing the updating scheme from a fully synchronous to an asynchronous one on some fixed CA local rule. In their paper ‘‘Solving the Parity Problem in One– Dimensional Cellular Automata’’, Heather Betel, Pedro P. B. de Oliveira, and Paola Flocchini deal with the parity problem in one–dimensional cellular automata (CA): a CA local rule solves the parity problem if, starting from any initial configuration, the CA converges to the 0–configuration (resp., the 1–configuration) if and only if the initial configuration contains an even number of 1s (resp., an odd number of 1s). In particular, authors focus on the neighborhood size of CA rules solving the problem. Murillo G. Carneiro and Gina M. B. Oliveira present in the paper ‘‘Synchronous Cellular Automata-Based Scheduler initialized by Heuristic and modeled by a Pseudolinear neighborhood’’ two approaches based on CA to the task scheduling problem in multiprocessor systems. The implementation of cellular automata on processor arrays is considered by Jean-Vivien Millo and Robert de Simone in the paper ‘‘Explicit routing schemes for implementation of cellular automata on processor arrays’’. They deal with the trade-offs between the generality of the CA neighborhood and the limited expressive power provided by physical platforms. This is an extremely hot topic which will help in turning CA towards real extended applications. We would like to warmly thank the authors for their work and effort which made this special issue possible. Special thanks go to all referees for their valuable contributions both during the selection and the final review process. Finally, we also want to thank Professor Grzegorz Rozenberg for offering us the opportunity to publish this special issue in Natural Computing.