Fundamenta Informaticae - Volume 139, issue 1

Authors: Clark, Gregory | Teutsch, Jason

Article Type: Research Article

Abstract: We investigate Mark Titchener’s T-complexity , an algorithm which measures the information content of finite strings. After introducing the T-complexity algorithm, we turn our attention to a particular class of “simple” finite strings. By exploiting special properties of simple strings, we obtain a fast algorithm to compute the maximum T-complexity among strings of a given length, and our estimates of these maxima show that T-complexity differs asymptotically from Kolmogorov complexity. Finally, we examine how closely de Bruijn sequences resemble strings with high T-complexity.

DOI: 10.3233/FI-2015-1223

Citation: Fundamenta Informaticae, vol. 139, no. 1, pp. 1-19, 2015

Authors: Janicki, Ryszard | Kleijn, Jetty | Koutny, Maciej | Mikulski, Łukasz

Article Type: Research Article

Abstract: Non-interleaving semantics of concurrent systems is often expressed using posets, where causally related events are ordered and concurrent events are unordered. Each causal poset describes a unique concurrent history, i.e., a set of executions, expressed as sequences or step sequences, that are consistent with it. Moreover, a poset captures all precedence-based invariant relationships between the events in the executions belonging to its concurrent history. However, concurrent histories in general may be too intricate to be described solely in terms of causal posets. In this paper, we introduce and investigate generalised mutex order structures which can capture the invariant causal relationships …in any concurrent history consisting of step sequence executions. Each such structure comprises two relations, viz. interleaving/mutex and weak causality. As our main result we prove that each generalised mutex order structure is the intersection of the step sequence executions which are consistent with it. Show more

Keywords: concurrent history, causal poset, weak causal order, mutex relation, interleaving, step sequence, causality semantics

DOI: 10.3233/FI-2015-1224

Citation: Fundamenta Informaticae, vol. 139, no. 1, pp. 21-42, 2015

Authors: Kumar, Paulraj Ranjith | Babu, P. | Palani, Sankaran

Article Type: Research Article

Abstract: Multiprocessors have emerged as a powerful computing means for running real-time applications, especially where a uniprocessor system would not be sufficient enough to execute all the tasks. The high performance and reliability of multiprocessors have made them a powerful computing resource. Such computing environment requires an efficient algorithm to determine when and on which processor a given task should be executed. In multiprocessor systems, an efficient scheduling of sequential and parallel tasks onto the processors is known to be NP- Hard problem. In this paper, the problem of minimizing schedule length with energy consumption constraint and the problem of minimizing …energy consumption with schedule length constraint on homogeneous and heterogeneous multiprocessor computers through independent sequential and parallel tasks are proposed. These problems emphasize the tradeoff between power and performance and are defined such that the power-performance product is optimized by fixing one factor and minimizing the other and vice versa. The performance of the proposed algorithm with optimal solution is validated using Particle Swarm Optimization (PSO) The PSO algorithm achieves 47.5% and 32% of power savings for scheduling sequential and parallel tasks to the processors respectively and also 45.5% of energy saving are achieved for scheduling both sequential or parallel tasks to the processors. Show more

Keywords: Multiprocessor, Embedded Systems, Energy and Power Optimization, PSO Algorithm

DOI: 10.3233/FI-2015-1225

Citation: Fundamenta Informaticae, vol. 139, no. 1, pp. 43-65, 2015

Authors: Li, Wentao | Xu, Weihua

Article Type: Research Article

Abstract: The decision-theoretic rough set model based on Bayesian decision theory is a main development tendency in the research of rough sets. To extend the theory of decision-theoretic rough set, the article devotes this study to presenting multigranulation decision-theoretic rough set model in ordered information systems. This new multigranulation decision-theoretic rough set approach is characterized by introducing the basic set assignment function in an ordered information system. It is addressed about how to construct probabilistic rough set and multigranulation decision-theoretic rough set models in an ordered information system. Moreover, three kinds of multigranulation decision-theoretic rough set model are analyzed carefully in …an ordered information system. In order to explain probabilistic rough set model and multigranulation decision-theoretic rough set models in an ordered information system, an illustrative example is considered, which is helpful for applying these theories to deal with practical issues. Show more

Keywords: Decision-theoretic rough set, multigranulation, ordered information system, partition function, probability measure

DOI: 10.3233/FI-2015-1226

Citation: Fundamenta Informaticae, vol. 139, no. 1, pp. 67-89, 2015

Authors: Zekri, Meriem | Alem, Karima | Souici-Meslati, Labiba

Article Type: Research Article

Abstract: Immunological computation is one of the largest recent bio-inspired approaches of artificial intelligence. Artificial immune systems (AIS) are inspired by the processes of the biological immune systems like the learning and memory characteristics which are used for solving complex problems. During the last two decades, AIS have been applied in various fields such as optimization, network security and data mining. In this article, we focus on the application of AIS to data mining in bioinformatics, more specifically, the classification task. For this purpose, we suggest three immune models based on clonal selection theory for the identification of G-protein coupled receptors …(GPCRs) to predict their function. Our three classifiers are the artificial immune recognition system (AIRS), the clonal selection algorithm (CLONALG) and the clonal selection classification algorithm (CSCA). The GPCRs represent one of the largest and most important families of multifunctional proteins and are a significant target for bioactive and drug discovery programs. It is estimated that more than half of the drugs on the market currently target GPCRs. However, although thousands of GPCRs sequences are known, many of them remain orphans, have unknown function. Our experiments show that the three immunological classifiers have provided interesting results, however, AIRS obtained the best ones. Therefore, it is, for us, the most suitable immune model for the GPCRs identification problem. Show more

Keywords: Artificial immune system, Protein function prediction, GPCRs Classification, Clonal selection algorithms, Pseudo amino acid composition

DOI: 10.3233/FI-2015-1227

Citation: Fundamenta Informaticae, vol. 139, no. 1, pp. 91-114, 2015