Fundamenta Informaticae - Volume 120, issue 2

Authors: Bergstra, J.A. | Middelburg, C.A.

Article Type: Research Article

Abstract: We study several aspects of the behaviours produced by instruction sequences under execution in the setting of the algebraic theory of processes known as ACP. We use ACP to describe the behaviours produced by instruction sequences under execution and to describe two protocols implementing these behaviours in the case where the processing of instructions takes place remotely. We also show that all finite-state behaviours considered in ACP can be produced by instruction sequences under execution.

Keywords: instruction sequence, remote instruction processing, instruction sequence producible process

DOI: 10.3233/FI-2012-753

Citation: Fundamenta Informaticae, vol. 120, no. 2, pp. 111-144, 2012

Authors: Bhandari, Dinabandhu | Murthy, C. A. | Pal, Sankar K.

Article Type: Research Article

Abstract: Genetic Algorithm (GA) has now become one of the leading mechanisms in providing solution to complex optimization problems. Although widely used, there are very few theoretical guidelines for determining when to stop the algorithm. This article establishes theoretically that the variance of the best fitness values obtained in the iterations can be considered as a measure to decide the termination criterion of a GA with elitist model (EGA). The criterion automatically takes into account the inherent characteristics of the objective function. Implementation issues of the proposed stopping criterion are explained. Its difference with some other stopping criteria is also critically …analyzed. Show more

Keywords: Genetic Algorithm with Elitist Model, Stopping Criterion, Markov Chain, Variance

DOI: 10.3233/FI-2012-754

Citation: Fundamenta Informaticae, vol. 120, no. 2, pp. 145-164, 2012

Authors: Dennunzio, Alberto | Formenti, Enrico | Manzoni, Luca

Article Type: Research Article

Abstract: This work studies some aspects of the computational power of fully asynchronous cellular automata (ACA). We deal with some notions of simulation between ACA and Turing Machines. In particular, we characterize the updating sequences specifying which are “universal”, i.e., allowing a (specific family of) ACA to simulate any Turing machine on any input. We also consider the computational cost of such simulations. Finally, we deal with ACA equipped with peculiar updating sequences, namely those generated by random walks.

Keywords: Asynchronous Cellular Automata, Turing Machines, Turing Universality, Computational Complexity

DOI: 10.3233/FI-2012-755

Citation: Fundamenta Informaticae, vol. 120, no. 2, pp. 165-180, 2012

Authors: Niewiadomski, Artur | Penczek, Wojciech | , Agata | Półrola, | Szreter, Maciej | Zbrzezny, Andrzej

Article Type: Research Article

Abstract: Automating the composition of web services is an object of a growing interest. In our paper [13] we proposed a method for converting the problem of the composition to the problem of building a graph of worlds consisting of formally defined objects, and presented the first phase of this composition aimed at building a graph of types of services (an abstract graph). In this work we propose a method of replacing abstract flows of this graph by sequences of concrete services able to satisfy the user’s request. The method is based on SAT-based reachability checking for (timed) automata with discrete …data and parametric assignments. Show more

DOI: 10.3233/FI-2012-756

Citation: Fundamenta Informaticae, vol. 120, no. 2, pp. 181-203, 2012