Fundamenta Informaticae - Volume 120, issue 1

Authors: Chalopin, Jérémie | Métivier, Yves | Morsellino, Thomas

Article Type: Research Article

Abstract: We address the enumeration and the leader election problems over partially anonymous and multi-hop broadcast networks. We consider an asynchronous communication model where each process broadcasts a message and all its neighbours receive this message after arbitrary and unpredictable time. In this paper, we present necessary conditions that must be satisfied by any graph to solve these problems and we show that these conditions are sufficient by providing an enumeration algorithm on the one hand and a leader election algorithm on the other hand. For both problems, we highlight the importance of the initial knowledge. Considering the enumeration problem, each …process only knows the size of the graph and, contrary to related works, the number of its neighbouring processes is unknown. Whereas for the election problem, we show that this combination of knowledge is not sufficient. Our algorithm assumes that each process initially knows a map of the network (without knowing its position in this map). From the complexity viewpoint, our algorithms offer polynomial complexities (memory at each process, number and size of exchanged messages). Show more

Keywords: Distributed Computing, Multi-hop, Broadcast, Election, Naming, Enumeration, Fibrations

DOI: 10.3233/FI-2012-747

Citation: Fundamenta Informaticae, vol. 120, no. 1, pp. 1-27, 2012

Authors: Mazzanti, Stefano

Article Type: Research Article

Abstract: Function classes closed with respect to substitution and concatenation recursion on notation are characterized as the substitution closure of finite function sets. Consequently, the sets of TC0 , NC1 and L computable functions are characterized as the substitution closure of a finite function set.

Keywords: concatenation recursion on notation, substitution basis

DOI: 10.3233/FI-2012-748

Citation: Fundamenta Informaticae, vol. 120, no. 1, pp. 29-58, 2012

Authors: Qin, Chuan | Wang, Zhi-Hui | Chang, Chin-Chen | Chen, KuoNan

Article Type: Research Article

Abstract: Reversible/lossless image data hiding schemes provide the capability to embed secret information into a cover image where the original carrier can be totally restored after extracting the secret information. This work presents a high performance reversible image data hiding scheme especially in stego image quality control using image inpainting, an efficient image processing skill. Embeddable pixels chosen from a cover image are initialized to a fixed value as preprocessing for inpainting. Subsequently, these initialized pixels are repaired using inpainting technique based on partial differential equations (PDE). These inpainted pixels can be used to carry secret bits and generate a stego …image. Experimental results show that the proposed scheme produces low distortion stego images and it also provides satisfactory hiding capacity. Show more

Keywords: reversible data hiding, lossless data hiding, hiding capacity, image inpainting, image quality

DOI: 10.3233/FI-2012-749

Citation: Fundamenta Informaticae, vol. 120, no. 1, pp. 59-70, 2012

Authors: Salomaa, Arto | Salomaa, Kai | Szilard, Andrew L.

Article Type: Research Article

DOI: 10.3233/FI-2012-750

Citation: Fundamenta Informaticae, vol. 120, no. 1, pp. 71-74, 2012

Authors: Suchenek, Marek A.

Article Type: Research Article

Abstract: The worst-case behavior of the heap-construction phase of Heapsort escaped mathematically precise characterization by a closed-form formula for almost five decades. This paper offers a proof that the exact number of comparisons of keys performed in the worst case during construction of a heap of size N is: 2N − 2s2 (N) − e2 (N), where s2 (N) is the sum of all digits of the binary representation of N and e2 (N) is the exponent of 2 in the prime factorization of N. It allows for derivation of this best-known upper bound on the number of comparisons of Heapsort: …(2N − 1)$\lceil$lgN$\rceil$ − 2$\lceil$lgN$\rceil$+1 − 2s2 (N) − e2 (N) + 5. Show more

Keywords: Heapsort, worst-case analysis, sum of digits

DOI: 10.3233/FI-2012-751

Citation: Fundamenta Informaticae, vol. 120, no. 1, pp. 75-92, 2012

Authors: Zhu, Ping

Article Type: Research Article

Abstract: To capture the uncertainty of information or knowledge in information systems, various information granulations, also known as knowledge granulations, have been proposed. Recently, several axiomatic definitions of information granulation have been introduced. In this paper, we try to improve these axiomatic definitions and give a universal construction of information granulation by relating information granulations with a class of functions of multiple variables. We show that the improved axiomatic definition has some concrete information granulations in the literature as instances.

Keywords: Information system, equivalence relation, information granulation, knowledge granulation, granulation measure

DOI: 10.3233/FI-2012-752

Citation: Fundamenta Informaticae, vol. 120, no. 1, pp. 93-109, 2012