ALBERT

Description: The availability in machine-readable form of descriptions of the structure of documents, as well as of the document discourse (e.g. the scientific discourse within scholarly articles), is crucial for facilitating semantic publishing and the overall comprehension of documents by both users and machines. In this paper we introduce DoCO, the Document Components Ontology, an OWL 2 DL ontology that provides a general-purpose structured vocabulary of document elements to describe both structural and rhetorical document components in RDF. In addition to describing the formal description of the ontology, this paper showcases its utility in practice in a variety of our own applications and other activities of the Semantic Publishing community that rely on DoCO to annotate and retrieve document components of scholarly articles. Content Type Journal Article Pages - DOI 10.3233/SW-150177 Authors Alexandru Constantin, École Polytechnique Fédérale de Lausanne, PFL IC IIF LSIR, BC 159 (Bâtiment BC), Station 14, CH-1015 Lausanne, Switzerland. E-mail: alex.constantin@epfl.ch Silvio Peroni, Department of Computer Science and Engineering, University of Bologna, Mura Anteo Zamboni 7, 40127 Bologna (BO), Italy. E-mails: silvio.peroni@unibo.it, fabio.vitali@unibo.it Steve Pettifer, School of Computer Science, University of Manchester, Kilburn Building, M13 9PL Manchester, United Kingdom. E-mail: steve.pettifer@manchester.ac.uk David Shotton, Oxford e-Research Centre, University of Oxford, 7 Keble Road, OX1 3QG Oxford, United Kingdom. E-mail: david.shotton@oerc.ox.ac.uk Fabio Vitali, Department of Computer Science and Engineering, University of Bologna, Mura Anteo Zamboni 7, 40127 Bologna (BO), Italy. E-mails: silvio.peroni@unibo.it, fabio.vitali@unibo.it Journal Semantic Web Online ISSN 2210-4968 Print ISSN 1570-0844

Description: This study presents theoretical proof and empirical evidence of the reduction algorithm convergence for the distance-based inconsistency in pairwise comparisons. Our empirical research shows that the convergence very quick. It usually takes less than 10 reductions to bring the inconsistency of the pairwise comparisons matrix below the assumed threshold of 1/3 (sufficient for most applications). We believe that this is the first Monte Carlo study demonstrating such results for the convergence speed of inconsistency reduction in pairwise comparisons. Content Type Journal Article Pages 355-367 DOI 10.3233/FI-2015-1184 Authors Waldemar W. Koczkodaj, Computer Science, Laurentian University, 935 Ramsey Lake Road, Sudbury, ON P3E 2C6, Canada. wkoczkodaj@cs.laurentian.ca Marek Kosiek, Jagiellonian University, Department of Mathematics and Computer Science, Prof. St. Łojasiewicza 6, 30-348 Kraków, Poland. Marek.Kosiek@im.uj.edu.pl Jacek Szybowski, AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Kraków, Poland. szybowsk@agh.edu.pl Ding Xu, Computer Science, Laurentian University, 935 Ramsey Lake Road, Sudbury, ON P3E 2C6, Canada Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 3 / 2015

Description: [Introduction] Schedule management of hospitalization is important to maintain or improve the quality of medical care and application of a clinical pathway is one of the important solutions for the management. Although several kinds of deductive methods for construction for a clinical pathway have been proposed, the customization is one of the important problems. This research proposed an inductive approach to support the customization of existing clinical pathways by using data on nursing actions stored in a hospital information system. [Method] The number of each nursing action applied to a given disease during the hospitalization was counted for each day as a temporal sequence. Temporal sequences were compared by using clustering and multidimensional scaling method in order to visualize the similarities between temporal patterns of clinical actions. [Results] Clustering and multidimensional scaling analysis classified these orders to one group necessary for the treatment for this DPC and the other specific to the status of a patient. The method was evaluated on data sets of ten frequent diseases extracted from hospital information system in Shimane University Hospital. Cataracta and Glaucoma were selected. Removing routine and poorly documented nursing actions, 46 items were selected for analysis. [Discussion] Counting data on executed nursing orders were analyzed as temporal sequences by using similarity-based analysis methods. The analysis classified the nursing actions into the two major groups: one consisted of orders necessary for the treatment and the other consisted of orders dependent on the status of admitted patients, including complicated diseases, such as DM or heart diseases. The method enabled us to inductive construction of standardized schedule management and detection of the conditions of patients difficult to apply the existing or induced clinical pathway. Content Type Journal Article Pages 237-252 DOI 10.3233/FI-2015-1177 Authors Haruko Iwata, Department of Medical Informatics, Faculty of Medicine, Shimane University, 89-1 Enya-cho Izumo 693-8501, Japan. {haruko23,hirano,tsumoto}@med.shimane-u.ac.jp Shoji Hirano, Department of Medical Informatics, Faculty of Medicine, Shimane University, 89-1 Enya-cho Izumo 693-8501, Japan. {haruko23,hirano,tsumoto}@med.shimane-u.ac.jp Shusaku Tsumoto, Department of Medical Informatics, Faculty of Medicine, Shimane University, 89-1 Enya-cho Izumo 693-8501, Japan. {haruko23,hirano,tsumoto}@med.shimane-u.ac.jp Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 2 / 2015

Description: At the end of the eighties, continuous Petri nets were introduced for: (1) alleviating the combinatory explosion triggered by discrete Petri nets (i.e. usual Petri nets) and, (2) modelling the behaviour of physical systems whose state is composed of continuous variables. Since then several works have established that the computational complexity of deciding some standard behavioural properties of Petri nets is reduced in this framework. Here we first establish the decidability of additional properties like coverability, boundedness and reachability set inclusion. We also design new decision procedures for reachability and lim-reachability problems with a better computational complexity. Finally we provide lower bounds characterising the exact complexity class of the reachability, the coverability, the boundedness, the deadlock freeness and the liveness problems. A small case study is introduced and analysed with these new procedures. Content Type Journal Article Pages 1-28 DOI 10.3233/FI-2015-1168 Authors Estíbaliz Fraca, Instituto de Investigación en Ingeniería de Aragón (I3A), Universidad de Zaragoza, Zaragoza, Spain. efraca@unizar.es Serge Haddad, Ecole Normale Supérieure de Cachan, LSV, CNRS UMR 8643, INRIA, Cachan, France. haddad@lsv.ens-cachan.fr Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 1 / 2015

Description: We propose a framework in terms of domain theory for semantic information models. We show how an artificial agent (the computer) can operate within such a model in a multiple attitude environment (fuzziness) where information is conveyed. We illustrate our approach by two examples — taking as the set of the degrees of reliability Kleene's 3-valued strong logic and Belnap-Dunn's 4-valued logic. Content Type Journal Article Pages 207-225 DOI 10.3233/FI-2015-1208 Authors Alexei Y. Muravitsky, Louisiana Scholars' College, Northwestern State University, Natchitoches, LA 71497, USA. alexeim@nsula.edu Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: Yurii Rogozhin's Biography and Publications Content Type Journal Article Pages 273-284 DOI 10.3233/FI-2015-1212 Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: We propose and investigate a formal language operation inspired by the naturally occurring phenomenon of DNA primer extension by a DNA-template-directed DNA Polymerase enzyme. Given two DNA strings u and v, where the shorter string v (called primer) is Watson-Crick complementary and can thus bind to a substring of the longer string u (called template) the result of the primer extension is a DNA string that is complementary to a suffix of the template which starts at the binding position of the primer. The operation of DNA primer extension can be abstracted as a binary operation on two formal languages: a template language L 1 and a primer language L 2 . We call this language operation L 1 -directed extension of L 2 and study the closure properties of various language classes, including the classes in the Chomsky hierarchy, under directed extension. Furthermore, we answer the question under what conditions can a given language of target strings be generated from a given template language when the primer language is unknown. We use the canonic inverse of directed extension in order to obtain the optimal solution (the minimal primer language) to this question. Content Type Journal Article Pages 179-192 DOI 10.3233/FI-2015-1206 Authors Srujan Kumar Enaganti, Department of Computer Science, The University of Western Ontario, London, ON N6A 5B7, Canada. senagant@uwo.ca; lila.kari@uwo.ca; steffen@csd.uwo.ca Lila Kari, Department of Computer Science, The University of Western Ontario, London, ON N6A 5B7, Canada. senagant@uwo.ca; lila.kari@uwo.ca; steffen@csd.uwo.ca Steffen Kopecki, Department of Computer Science, The University of Western Ontario, London, ON N6A 5B7, Canada. senagant@uwo.ca; lila.kari@uwo.ca; steffen@csd.uwo.ca Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: In this paper we investigate the use of general topological spaces in connection with a generalised variant of membrane systems. We provide an approach which produces a fine grain description of local operations occurring simultaneously in sets of compartments of the system by restricting the interactions between objects. This restriction is given by open sets of a topology and multisets of objects associated with them, which dynamically change during the functioning of the system and which together define a notion of vicinity for the objects taking part in the interactions. Content Type Journal Article Pages 193-205 DOI 10.3233/FI-2015-1207 Authors Erzsébet Csuhaj-Varjú, Department of Algorithms and Their Applications, Faculty of Informatics, Eötvös Loránd University, Pázmány Péter sétány 1/c, 1117 Budapest, Hungary. csuhaj@inf.elte.hu Marian Gheorghe, Department of Computer Science, University of Sheffield, Regent Court, 211 Portobello, Sheffield S1 4DP, United Kingdom. m.gheorghe@sheffield.ac.uk, m.stannett@sheffield.ac.uk Mike Stannett, Department of Computer Science, University of Sheffield, Regent Court, 211 Portobello, Sheffield S1 4DP, United Kingdom. m.gheorghe@sheffield.ac.uk, m.stannett@sheffield.ac.uk György Vaszil, Department of Computer Science, Faculty of Informatics, University of Debrecen, Kassai út 26, 4028 Debrecen, Hungary. vaszil.gyorgy@inf.unideb.hu Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: We discuss simple functional transductions defined by invertible Mealy automata under iteration and in particular the question when the orbit relation defined by iteration is rational. We identify a class of these automata that has relatively complicated orbits, yet some of them are still orbit rational and discuss a number of decision problems associated with these devices. Content Type Journal Article Pages 259-272 DOI 10.3233/FI-2015-1211 Authors K. Sutner, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA. sutner@cs.cmu.edu Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: Elementary cellular automata (ECA) are linear arrays of finite-state machines (cells) which take binary states, and update their states simultaneously depending on states of their closest neighbours. We design and study ECA with memory (ECAM), where every cell remembers its states during some fixed period of evolution. We characterize complexity of ECAM in a case study of rule 126, and then provide detailed behavioural classification of ECAM. We show that by enriching ECA with memory we can achieve transitions between the classes of behavioural complexity. We also show that memory helps to ‘discover’ hidden information and behaviour on trivial (uniform, periodic), and non-trivial (chaotic, complex) dynamical systems. Content Type Journal Article Pages 1-16 DOI 10.3233/FI-2015-1194 Authors Genaro J. Martínez, Escuela Superior de Cómputo, Instituto Politécnico Nacional, México D.F., México, International Centre of Unconventional Computing, University of the West of England, BS16 1QY Bristol, United Kingdom. Genaro.Martinez@uwe.ac.uk Andrew Adamatzky, International Centre of Unconventional Computing, University of the West of England, BS16 1QY Bristol, United Kingdom. Andrew.Adamatzky@uwe.ac.uk Ramon Alonso-Sanz, Universidad Politecnica de Madrid. ETSIA (Estadistica,GSC), Madrid, Spain. Ramon.Alonso@upm.es Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: We introduce a filtering methodology based on locality-sensitive hashing (LSH) and whitening transformation to reduce candidate tuples between which encrypted vector databases (EVDBs) must compute similarity for query processing. The LSH hashing methodology is efficient for estimating similarities between two vectors. It hashes a vector space using randomly chosen vectors. We can filter vectors that are less similar to the querying vectors by recording which hashed space each vector belongs to. However, if vectors in EVDBs are found locally, then most vectors are in the same hashed space, so the filter will not work. Because we can treat those cases using whitening transformation to distribute the vectors broadly, our proposed filtering methodology will work effectively on any vector space. We also show that our filter reduces the server's query processing cost. Content Type Journal Article Pages 291-304 DOI 10.3233/FI-2015-1180 Authors Junpei Kawamoto, Graduate School of Systems and Information Engineering, University of Tsukuba, 1-1-1 Tennodai, Tsukuba, Japan. junpei@mdl.cs.tsukuba.ac.jp Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 2 / 2015

Description: This paper introduces a novel, interactive and exploratory, approach to information retrieval (search engines) based on clustering. Presented method allows users to change the clustering structure by applying a free-text clustering context query that is treated as a criterion for document-to-cluster allocation. Exploration mechanisms are delivered by redefining the interaction scenario in which the user can interact with data on the level of topic discovery or cluster labeling. In this paper, the presented idea is realized by a graph structure called the Query-Summarize Graph. This data structure is useful in the definition of the similarity measure between the snippets as well as in the snippet clustering algorithm. The experiments on real-world data are showing that the proposed solution has many interesting properties and can be an alternative approach to interactive information retrieval. Content Type Journal Article Pages 273-290 DOI 10.3233/FI-2015-1179 Authors Michał Meina, Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Poland. mich@mat.umk.pl Hung Son Nguyen, Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Banacha 2, Warsaw, Poland. son@mimuw.edu.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 2 / 2015

Description: A formal framework for data mining with association rules is introduced. The framework is based on a logical calculus of association rules which is enhanced by several formal tools. The enhancement allows the description of the whole data mining process, including formulation of analytical questions, application of an analytical procedure and interpretation of its results. The role of formalized domain knowledge is discussed. Content Type Journal Article Pages 171-217 DOI 10.3233/FI-2015-1175 Authors Jan Rauch, University of Economics, Prague, nám. W. Churchilla 4, 130 67 Prague 3, Czech Republic. rauch@vse.cz Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 2 / 2015

Description: Administrative services such social care, tax reduction, and many others using complex decision processes, request individuals to provide large amounts of private data items, in order to calibrate their proposal to the specific situation of the applicant. This data is subsequently processed and stored by the organization. However, all the requested information is not needed to reach the same decision. We have recently proposed an approach, termed Minimum Exposure, to reduce the quantity of information provided by the users, in order to protect her privacy, reduce processing costs for the organization, and financial lost in the case of a data breach. In this paper, we address the case of decision making processes based on sets of classifiers, typically multi-label classifiers. We propose a practical implementation using state of the art multi-label classifiers, and analyze the effectiveness of our solution on several real multi-label data sets. Content Type Journal Article Pages 219-236 DOI 10.3233/FI-2015-1176 Authors Nicolas Anciaux, INRIA and University of Versailles SMIS team, Domaine de Voluceau, 78153 Le Chesnay, France. nicolas.anciaux@inria.fr Danae Boutara, INRIA and Ecole Polytechnique, Laboratoire d'Informatique de l'Ecole Polytechnique, 91128, Palaiseau, France. dboutara@gmail.com Benjamin Nguyen, INRIA and University of Versailles SMIS team, Domaine de Voluceau, 78153 Le Chesnay, France. benjamin.nguyen@inria.fr Michalis Vazirgiannis, Ecole Polytechnique and Athens University of Economics and Business, Laboratoire d'Informatique de l'Ecole Polytechnique, 91128, Palaiseau, France. mvazirg@aueb.gr Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 2 / 2015

Description: In this paper, a solution is given to the problem proposed by Järvinen in [8]. A smallest completion of the rough sets system determined by an arbitrary binary relation is given. This completion, in the case of a quasi order, coincides with the rough sets system which is a Nelson algebra. Further, the algebraic properties of this completion has been studied. Content Type Journal Article Pages 413-424 DOI 10.3233/FI-2015-1188 Authors Dwaraganathan Umadevi, Department of Mathematics, Kamaraj College of Engineering and Technology, Virudhunagar - 626 001, Tamil Nadu, India. umavasanthy@yahoo.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 3 / 2015

Description: We introduce ω-Petri nets (ωPN), an extension of plain Petri nets with ω-labeled input and output arcs, that is well-suited to analyse parametric concurrent systems with dynamic thread creation. Most techniques (such as the Karp and Miller tree or the Rackoff technique) that have been proposed in the setting of plain Petri nets do not apply directly to ωPN because ωPN define transition systems that have infinite branching. This motivates a thorough analysis of the computational aspects of ωPN. We show that an ωPN can be turned into a plain Petri net that allows us to recover the reachability set of the ωPN, but that does not preserve termination (an ωPN terminates iff it admits no infinitely long execution). This yields complexity bounds for the reachability, boundedness, place boundedness and coverability problems on ωPN. We provide a practical algorithm to compute a coverability set of the ωPN and to decide termination by adapting the classical Karp and Miller tree construction. We also adapt the Rackoff technique to ωPN, to obtain the exact complexity of the termination problem. Finally, we consider the extension of ωPN with reset and transfer arcs, and show how this extension impacts the decidability and complexity of the aforementioned problems. Content Type Journal Article Pages 29-60 DOI 10.3233/FI-2015-1169 Authors Gilles Geeraerts, Université libre de Bruxelles, Département d'informatique, Bruxelles, Belgium. gigeerae@ulb.ac.be Alexander Heußner, Otto-Friedrich-Universität Bamberg, Bamberg, Germany. alexander.heussner@uni-bamberg.de M. Praveen, Laboratoire Bordelais de Recherche en Informatique (LaBRI), France. praveen.manjunatha@labri.fr Jean-François Raskin, Université libre de Bruxelles, Département d'informatique, Bruxelles, Belgium. jraskin@ulb.ac.be Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 1 / 2015

Description: Most real life situations need some sort of approximation to fit mathematical models. The beauty of using topology in approximation is achieved via obtaining approximation for qualitative subsets without coding or using assumption. The aim of this paper is to introduce different approaches to near sets by using general relations and special neighborhoods. Some fundamental properties and characterizations are given. We obtain a comparison between these new approximations and traditional approximations introduced by Peters [23]. Content Type Journal Article Pages 387-402 DOI 10.3233/FI-2015-1186 Authors Emad A. Marei, Department of Mathematics, Faculty of Science and Art, Shaqra University, Saudi Arabia. via_marei@yahoo.com Mohamed E. Abd El-Monsef, Department of Mathematics, Faculty of Science, Tanta University, Egypt Hassan M. Abu-Donia, Department of Mathematics, Faculty of Science, Zagazig University, Egypt Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 3 / 2015

Description: A concurrent system is persistent if throughout its operation no activity which became enabled can subsequently be prevented from being executed by any other activity. This is often a highly desirable (or even necessary) property; in particular, if the system is to be implemented in hardware. Over the past 40 years, persistence has been investigated and applied in practical implementations assuming that each activity is a single atomic action which can be represented, for example, by a single transition of a Petri net. In this paper we investigate the behaviour of GALS (Globally Asynchronous Locally Synchronous) systems in the context of VLSI circuits. The specification of a system is given in the form of a Petri net. Our aim is to re-design the system to optimise signal management, by grouping together concurrent events. Looking at the concurrent reachability graph of the given Petri net, we are interested in discovering events that appear in ‘bundles’, so that they all can be executed in a single clock tick. The best candidates for bundles are sets of events that appear and re-appear over and over again in the same configurations, forming ‘persistent’ sets of events. Persistence was considered so far only in the context of sequential semantics. In this paper, we move to the realm of step based execution and consider not only steps which are persistent and cannot be disabled by other steps, but also steps which are nonviolent and cannot disable other steps. We then introduce a formal definition of a bundle and propose an algorithm to prune the behaviour of a system, so that only bundled steps remain. The pruned reachability graph represents the behaviour of a re-engineered system, which in turn can be implemented in a new Petri net using the standard techniques of net synthesis. The proposed algorithm prunes reachability graphs of persistent and safe nets leaving bundles that represent maximally concurrent steps. Content Type Journal Article Pages 143-170 DOI 10.3233/FI-2015-1173 Authors Johnson Fernandes, School of Electrical & Electronic Eng., Newcastle University, Newcastle upon Tyne, NE1 7RU, U.K. Maciej Koutny, School of Computing Science, Newcastle University, Newcastle upon Tyne NE1 7RU, U.K. Łukasz Mikulski, Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Chopina 12/18, Poland Marta Pietkiewicz-Koutny, School of Computing Science, Newcastle University, Newcastle upon Tyne NE1 7RU, U.K. Danil Sokolov, School of Electrical & Electronic Eng., Newcastle University, Newcastle upon Tyne, NE1 7RU, U.K. Alex Yakovlev, School of Electrical & Electronic Eng., Newcastle University, Newcastle upon Tyne, NE1 7RU, U.K. Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 1 / 2015

Description: The concept of region incrementing in visual cryptography was introduced to encrypt an image into multiple secrecy levels. But, it suffers from the pixel expansion increasing exponentially as the number of participants grows. In this paper, we propose a region incrementing visual secret sharing (RIVSS) scheme based on random grids. The proposed scheme is a general (k, n)-RIVSS scheme, in which any t (k ≤ t ≤ n) shares can be used to reconstruct the secret regions up to t − k + 1 levels. However, no information about the input image can be revealed by any k − 1 or fewer shares. With a nice property of region incrementing, the proposed scheme benefits by sharing an image without any pixel expansion and codebook requirement. We give formal proofs and experimental results to confirm both correctness and feasibility of our scheme. Content Type Journal Article Pages 369-386 DOI 10.3233/FI-2015-1185 Authors Sachin Kumar, Department of Mathematics, Indian Institute of Technology Delhi, Hauz Khas, New Delhi - 110016, India. skiitd09@gmail.com; rksharma@maths.iitd.ac.in Rajendra Kumar Sharma, Department of Mathematics, Indian Institute of Technology Delhi, Hauz Khas, New Delhi - 110016, India. skiitd09@gmail.com; rksharma@maths.iitd.ac.in Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 3 / 2015

Description: The r-th order nonlinearity of Boolean functions is an important cryptographic criterion associated with some attacks on stream and block ciphers. It is also very useful in coding theory, since it is related to the covering radii of Reed-Muller codes. In this paper we investigate the lower bound of the higher-order nonlinearity of Niho Boolean functions f(x) = tr(λx d ) over F 2 n , where l \isin F 2 n * , d = 2 ( n - 1)/2 + 2 ( n - 1)/4 - 1 when n = 1 mod 4 or d = 2 ( n - 1)/2 + 2 (3 n - 1)/4 - 1 when n = 3 mod 4. Content Type Journal Article Pages 403-412 DOI 10.3233/FI-2015-1187 Authors Guanghong Sun, College of Sciences, Hohai University, Nanjing, 210098, China. sgh1976@gmail.com Chuankun Wu, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, 100095, China Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 3 / 2015

Description: In this paper, we consider tolerances induced by irredundant coverings. Each tolerance R on U determines a quasiorder ≤ R by setting x ≤ R y if and only if R(x) ⊆ R(y). We prove that for a tolerance R induced by a covering H of U, the covering H is irredundant if and only if the quasiordered set (U,≤ R ) is bounded by minimal elements and the tolerance R coincides with the product ≥ R º ≤ R . We also show that in such a case H = {↑m | m is minimal in (U,≤ R )}, and for each minimal m, we have R(m) = ↑m. Additionally, this irredundant covering H inducing R consists of some blocks of the tolerance R. We give necessary and sufficient conditions under which H and the set of R-blocks coincide. These results are established by applying the notion of Helly numbers of quasiordered sets. Content Type Journal Article Pages 341-353 DOI 10.3233/FI-2015-1183 Authors Jouni Järvinen, Sirkankuja 1, 20810 Turku, Finland. Jouni.Kalervo.Jarvinen@gmail.com Sándor Radeleczki, Institute of Mathematics, University of Miskolc, 3515 Miskolc-Egyetemváros, Hungary. Matradi@uni-miskolc.hu Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 3 / 2015

Description: A Web service is defined as an autonomous unit of application logic that provides either some business functionality or information to other applications through an Internet connection. Web services are based on a set of eXtensible Markup Language (XML) standards such as Universal Description, Discovery and Integration (UDDI), Web Services Description Language (WSDL), and Simple Object Access Protocol (SOAP). Nowadays Web services are becoming more and more popular for supporting different social applications, thus there are also increasing demands and discussions about Web services privacy protection in information. In general, privacy policies describe an organization's data practices on what information they collect from individuals (e.g., consumers) and what (e.g., purposes) they do with it. To enable privacy protection for Web service consumers across multiple domains and services, the World Wide Web Consortium (W3C) published a document called “Web Services Architecture (WSA) Requirements” that defines some specific privacy requirements for Web services as a future research topic. This paper presents a mathematical model to construct the privacy policies in SOAP Message Exchange Patterns (MEP) for social services. Further, this paper also presents the privacy policies in security tokens with SOAP messages. Content Type Journal Article Pages 253-271 DOI 10.3233/FI-2015-1178 Authors Wuhui Chen, School of Computer Science and Engineering, University of Aizu, Fukushima, Japan. chenwuhui21@gmail.com, paikic@u-aizu.ac.jp Incheon Paik, School of Computer Science and Engineering, University of Aizu, Fukushima, Japan. chenwuhui21@gmail.com, paikic@u-aizu.ac.jp Patrick C.K. Hung, Faculty of Business and Information Technology, University of Ontario Institute of Technology (UOIT), Canada. patrick.hung@uoit.ca Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 2 / 2015

Description: Modularity is a mandatory principle to apply Petri nets to real world-sized systems. Modular extensions of Petri nets allow to create complex models by combining smaller entities. They facilitate the modeling and verification of large systems by applying a divide and conquer approach and promoting reuse. Modularity includes a wide range of notions such as encapsulation, hierarchy and instantiation. Over the years, Petri nets have been extended to include these mechanisms in many different ways. The heterogeneity of such extensions and their definitions makes it difficult to reason about their common features at a general level. We propose in this article an approach to standardize the semantics of modular Petri nets formalisms, with the objective of gathering even the most complex modular features from the literature. This is achieved with a new Petri nets formalism, called the LLAMAS Language for Advanced Modular Algebraic Nets (LLAMAS). We focus principally on the composition mechanism of LLAMAS, while introducing the rest of the language with an example. The composition mechanism is introduced both informally and with formal definitions. Our approach has two positive outcomes. First, the definition of new formalisms is facilitated, by providing common ground for the definition of their semantics. Second, it is possible to reason at a general level on the most advanced verification techniques, such as the recent advances in the domain of decision diagrams. Content Type Journal Article Pages 87-116 DOI 10.3233/FI-2015-1171 Authors Alexis Marechal, Centro de Investigaciones en Nuevas Tecnologías Informáticas, Universidad Privada Boliviana, La Paz, Bolivia. alexismarechal@lp.upb.edu Didier Buchs, Centre Universitaire d'Informatique, University of Geneva, 7 route de Drize, 1227 Carouge, Switzerland. didier.buchs@unige.ch Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 1 / 2015

Description: In this paper we tackle the problem of verifying whether a scenario is executable in a Petri net. In contrast to sequentially ordered runs, a scenario includes both information about dependencies and independencies of events. Consequently, a scenario allows a precise and intuitive specification of a run of a concurrent or distributed system. In this paper we consider Petri nets with arc weights, namely marked place/transition-nets (p/t-nets) and p/t-nets with inhibitor arcs (pti-nets). A scenario of a p/t-net is a labelled partial order (lpo). A scenario of a pti-net is a labelled stratified order structure (lso). Accordingly, the question is either whether a given lpo is in the language of a given p/t-net or whether an lso is in the language of a given pti-net. Different approaches exist to define the partial language of a Petri net. Each definition yields a different verification algorithm, but existing algorithms perform quite poorly in terms of runtime for most examples. We introduce a new compact characterization of the partial language of a Petri net. This characterization is optimized with respect to the verification problem. The paper is a revised and extended version of the conference paper [10]. Content Type Journal Article Pages 117-142 DOI 10.3233/FI-2015-1172 Authors Robin Bergenthum, Department of Software Engineering and Theory of Programming, FernUniversität in Hagen, Germany. robin.bergenthum@fernuni-hagen.de Robert Lorenz, Lecturing Professorship for Computer Science, University of Augsburg, Germany. robert.lorenz@informatik.uni-augsburg.de Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 1 / 2015

Description: We investigate several computational problems of communication-free Petri nets, and develop very efficient (mostly linear time) algorithms for different variations of the boundedness and liveness problems of cf-PNs. For several more complex notions of boundedness, as well as for the covering problem, we show NP-completeness. In the last part, we use our results for cf-PNs to give linear time algorithms for related problems of context-free (commutative) grammars, and, in turn, use known results for such grammars to give a coNEXPTIME-upper bound for the equivalence problem of cf-PNs. Content Type Journal Article Pages 61-86 DOI 10.3233/FI-2015-1170 Authors Ernst W. Mayr, Institut für Informatik, Technische Universität München, Garching, Germany. mayr@in.tum.de; weihmann@in.tum.de Jeremias Weihmann, Institut für Informatik, Technische Universität München, Garching, Germany. mayr@in.tum.de; weihmann@in.tum.de Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 137 Journal Issue Volume 137, Number 1 / 2015

Description: In the field of small universal Turing machines, Yurii Rogozhin holds a special prize: he was first to close off an infinite number of open questions by drawing a closed curve that separates the infinite set of Turing machines that are universal from a finite set of small machines for which we don't yet know. Rogozhin did this by finding the smallest known universal Turing machines at the time, both in terms of number of states and number of symbols. This brief note summarises this and a few of Yurii's other contributions to the field, including his work with Manfred Kudlek on small circular Post machines. Content Type Journal Article Pages 251-258 DOI 10.3233/FI-2015-1210 Authors Damien Woods, California Institute of Technology, Pasadena, CA 91125, USA. woods@caltech.edu Turlough Neary, Institute for Neuroinformatics, University of Zürich and ETH Zürich, Zürich, Switzerland. tneary@ini.phys.ethz.ch Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: We consider the first-order theory of the monoid P(A*) of languages over a finite or infinite alphabet A (with at least two letters) endowed solely with concatenation lifted to sets: no set theoretical predicate or function, no constant. Coding a word u by the submonoid u* it generates, we prove that the operation (u*, v*) → (uv)* and the predicate {(u*,X) | ε ∈ X, u ∈ X} are definable in 〈P(A*); ·,=〉. This allows to interpret the second-order theory of 〈A*; ·,=〉 in the first-order theory of 〈P(A*); ·,=〉 and prove the undecidability of the Π 8 fragment of this last theory. These results involve technical difficulties witnessed by the logical complexity of the obtained definitions: the above mentioned predicates are respectively Δ 5 and Δ 7 . Content Type Journal Article Pages 159-177 DOI 10.3233/FI-2015-1205 Authors Christian Choffrut, LIAFA, CNRS and Université Paris Diderot, Paris 7, Case 7014, France. {Christian.Choffrut, seg}@liafa.univ-paris-diderot.fr Serge Grigorieff, LIAFA, CNRS and Université Paris Diderot, Paris 7, Case 7014, France. {Christian.Choffrut, seg}@liafa.univ-paris-diderot.fr Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: We consider in this paper the assembly of micronuclear genes in stichotrichous ciliates to their macronuclear form. We represent the micronuclear genes and all their intermediate forms from micro- to macro- as signed permutations, where integer i stands for the i-th MDS of the macronuclear gene and ī stands for the inverted form of that MDS; the macronuclear assembled gene is represented as the sorted permutation 1 2 . . . n, while its micronuclear form is an arbitrary signed permutation. We focus on the elementary gene assembly model consisting of two operations on signed permutations: eh (elementary hairpin inverting) and ed (elementary double recombination); gene assembly is modeled in this framework as a permutation sorting process. The general problem we investigate is to give a characterization of all signed permutations that can be sorted by the elementary operations. We make progress towards a full solution for this problem by relating sequences of eh and ed operations applicable to a given permutation to paths in the dependency graph associated to that permutation. Content Type Journal Article Pages 145-158 DOI 10.3233/FI-2015-1204 Authors Vladimir Rogojin, Computational Biomodeling Laboratory, Turku Centre for Computer Science and Department of Information Technologies, Åbo Akademi University, 20520 Turku, Finland. vrogojin@abo.fi, ipetre@abo.fi Ion Petre, Computational Biomodeling Laboratory, Turku Centre for Computer Science and Department of Information Technologies, Åbo Akademi University, 20520 Turku, Finland. vrogojin@abo.fi, ipetre@abo.fi Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: Polynomial-time P systems with active membranes characterise PSPACE by exploiting membranes nested to a polynomial depth, which may be subject to membrane division rules. When only elementary (leaf) membrane division rules are allowed, the computing power decreases to P PP = P #P , the class of problems solvable in polynomial time by deterministic Turing machines equipped with oracles for counting (or majority) problems. In this paper we investigate a variant of intermediate power, limiting membrane nesting (hence membrane division) to constant depth, and we prove that the resulting P systems can solve all problems in the counting hierarchy CH, which is located between P PP and PSPACE. In particular, for each integer k ≥ 0 we provide a lower bound to the computing power of P systems of depth k. Content Type Journal Article Pages 97-111 DOI 10.3233/FI-2015-1201 Authors Alberto Leporati, Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy. {leporati, luca.manzoni, mauri, porreca, zandron}@disco.unimib.it Luca Manzoni, Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy. {leporati, luca.manzoni, mauri, porreca, zandron}@disco.unimib.it Giancarlo Mauri, Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy. {leporati, luca.manzoni, mauri, porreca, zandron}@disco.unimib.it Antonio E. Porreca, Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy. {leporati, luca.manzoni, mauri, porreca, zandron}@disco.unimib.it Claudio Zandron, Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy. {leporati, luca.manzoni, mauri, porreca, zandron}@disco.unimib.it Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: A multiple interpretation scheme is an ordered sequence of morphisms. The ordered multiple interpretation of a word is obtained by concatenating the images of that word in the given order of morphisms. The arbitrary multiple interpretation of a word is the semigroup generated by the images of that word. These interpretations are naturally extended to languages. Four types of ambiguity of multiple interpretation schemata on a language are defined: o-ambiguity, internal ambiguity, weakly external ambiguity and strongly external ambiguity. We investigate the problem of deciding whether a multiple interpretation scheme is ambiguous on regular languages. Content Type Journal Article Pages 85-95 DOI 10.3233/FI-2015-1200 Authors Pedro Pablo Alarcón, Department of Organization and Structure of Information, Polytechnic University of Madrid, Crta. de Valencia km. 7 - 28031 Madrid, Spain. pedrop.alarcon@eui.upm.es Fernando Arroyo, Department of Languages Projects and Computer Information Systems, Polytechnic University of Madrid, Crta. de Valencia km. 7 - 28031 Madrid, Spain. farroyo@eui.upm.es Henning Bordihn, Department of Computer Science, University of Potsdam, August-Bebel-Str. 89, 14482 Potsdam, Germany. henning@cs.uni-potsdam.de Victor Mitrana, Department of Organization and Structure of Information, Polytechnic University of Madrid, Crta. de Valencia km. 7 - 28031 Madrid, Spain. victor.mitrana@upm.es Mike Müller, Department of Computer Science, University of Kiel, Christian-Albrechts-Platz 4, 24098 Kiel, Germany. mimu@informatik.uni-kiel.de Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: Semilinear sets are one of the most important concepts in theoretical computer science, as illustrated by the fact that the set of nonnegative integer solutions to any system of Diophantine equations is semilinear. Parikh's theorem enables us to represent any semilinear set as a pushdown automaton (PDA). We summarize recent results on the descriptional complexity of conversions among different representations of a semilinear set: as a vector set (conventional), a finite automaton (FA), a PDA, etc.. We also discuss semilinearity-preserving operations like union, intersection, and complement. We use Parikh's theorem to enlarge the class of finite-state machines that can represent semilinear sets. In particular, we give a simpler proof of a known result that characterizes semilinear sets in terms of machines with reversal-bounded counters. We then investigate the power of such a machine with only one counter in the context of a long-standing conjecture about repetition on words. Content Type Journal Article Pages 61-76 DOI 10.3233/FI-2015-1198 Authors Oscar H. Ibarra, Department of Computer Science, University of California, Santa Barbara, CA 93106, USA. ibarra@cs.ucsb.edu Shinnosuke Seki, Helsinki Institute for Information Technology (HIIT), Department of Information and Computer Science, Aalto University, P. O. Box 15400, FI-00076, Aalto, Finland. shinnosuke.seki@aalto.fi Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: Computational completeness is known for P systems with two catalysts and purely catalytic P systems with three catalysts as well as for P systems with one bi-stable catalyst. We complete this picture by showing computational completeness for purely catalytic P systems with one bi-stable catalyst and one catalyst. Moreover, we present some concrete universal P systems, e.g., for P systems with one multi-stable catalyst and for P systems with multiple catalysts. Furthermore, we optimize the descriptional complexity of Minsky's reduction from register machines with an arbitrary number of registers to register machines with only two registers. In that way, we are able to transform the universal machines U 22 and U 20 of Korec into weakly universal register machines with only two decrementable registers, one even with unencoded output. Based on these universal register machines, we then construct small universal P systems with one bi-stable catalyst and one catalyst as well as small universal purely catalytic P systems with three catalysts. With respect to the number of rules, the smallest universal P systems can be obtained with multi-stable catalysts and with multiple catalysts. The number of rules in all these systems can be further reduced by adding the concept of toxic objects (a specified subset of objects), where all computation branches not evolving all toxic objects in every computation step do not yield a result. Content Type Journal Article Pages 227-250 DOI 10.3233/FI-2015-1209 Authors Artiom Alhazov, Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Academiei 5, Chişinău, MD-2028, Moldova. artiom@math.md Rudolf Freund, Faculty of Informatics, Vienna University of Technology, Favoritenstr. 9, 1040 Vienna, Austria. rudi@emcc.at Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: This paper concerns new characterizations of language classes in the Chomsky hierarchy in terms of a new type of computing device called FAMM (Finite Automaton with Multiset Memory) in which a multiset of symbol objects is available for the storage of working space. Unlike the stack or the tape for a storage, the multiset might seem to be less powerful in computing task, due to the lack of positional (structural) information of stored data. We introduce the class of FAMMs of degree d (for non-negative integer d) in general form, and investigate the computing powers of some subclasses of those FAMMs. We show that the classes of languages accepted by FAMMs of degree 0, by FAMMs of degree 1, by exponentially-bounded FAMMs of degree 2, and by FAMMs of degree 2 are exactly the four classes of languages REG, CF, CS and RE in the Chomsky hierarchy, respectively. Thus, this unified view from multiset-based computing provides new insight into the computational aspects of the Chomsky hierarchy. Content Type Journal Article Pages 31-44 DOI 10.3233/FI-2015-1196 Authors Fumiya Okubo, Faculty of Arts and Science, Kyushu University, Center Zone, Ito Campus, 744 Motooka, Nishi-ku, Fukuoka 819-0395, Japan. fokubo@artsci.kyushu-u.ac.jp Takashi Yokomori, Department of Mathematics, Faculty of Education and Integrated Arts and Sciences, Waseda University, 1-6-1 Nishiwaseda, Shinjuku-ku, Tokyo 169-8050, Japan. yokomori@waseda.jp Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: In this paper, our results on algorithmic analysis of tiling in hyperbolic spaces are discussed. We overview results and developments obtained by the approach, focusing on the construction of universal cellular automata in hyperbolic spaces with a minimal number of cell states. Content Type Journal Article Pages 113-125 DOI 10.3233/FI-2015-1202 Authors Maurice Margenstern, Université de Lorraine, LITA EA 3097, Campus du Saulcy, 57045 METZ Cédex 1, France. maurice.margenstern@univ-lorraine.fr Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: A membrane system (P system) is a distributed computing model inspired by information processes in living cells. P systems previously provided new characterizations of a variety of complexity classes and their borderlines. Specifically, in tissue-like membrane systems, cell separation rules have been considered joint with communication rules of the form symport/antiport. On the one hand, only tractable problems can be efficiently solved by using cell separation and communication rules with length at most 2. On the other hand, an efficient and uniform solution to the SAT problem by using cell separation and communication rules with length at most 8 has been recently given. In this paper we improve the previous result by showing that the SAT problem can be solved by a family of tissue P systems with cell separation in linear time, by using communication rules with length at most 3. Thus, in the framework of tissue P systems with cell separation, we provide an optimal tractability borderline: passing from length 2 to 3 amounts to passing from non–efficiency to efficiency, assuming that P ≠ NP. Content Type Journal Article Pages 45-60 DOI 10.3233/FI-2015-1197 Authors Mario J. Pérez-Jiménez, Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, 41012 Sevilla, Spain. marper@us.es Petr Sosík, Research Institute of the IT4Innovations Centre of Excellence, Faculty of Philosophy and Science, Silesian University in Opava, 74601 Opava, Czech Republic. petr.sosik@fpf.slu.cz Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: In this article we introduce the operations of insertion and deletion working in random context and semi-conditional modes. We show that conditional application of insertion and deletion rules strictly increases the computational power. In the case of semi-conditional insertion-deletion systems, context-free insertion and deletion rules of one symbol are sufficient to achieve computational completeness. In the random context case, our results expose asymmetry between the computational power of insertion and deletion rules: semi-conditional systems of size (2, 0, 0; 1, 1, 0) (with context-free two-symbol insertion rules, and one-symbol deletion rules with one-symbol left context) are computationally complete, while systems of size (1, 1, 0; 2, 0, 0) (and, more generally, of size (1, 1, 0; p, 1, 1)) are not. Content Type Journal Article Pages 127-144 DOI 10.3233/FI-2015-1203 Authors Sergiu Ivanov, Laboratoire d'Algorithmique, Complexité et Logique, Université Paris Est – Créteil Val de Marne, 61, av. gén. de Gaulle, 94010 Créteil, France. sergiu.ivanov@u-pec.fr, verlan@u-pec.fr Sergey Verlan, Laboratoire d'Algorithmique, Complexité et Logique, Université Paris Est – Créteil Val de Marne, 61, av. gén. de Gaulle, 94010 Créteil, France. sergiu.ivanov@u-pec.fr, verlan@u-pec.fr Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: Multi-agent models and simulations are used to describe complex systems in domains such as biological, geographical or ecological sciences. The increasing model complexity results in a growing need for computing resources and motivates the use of new architectures such as multi-cores and many-cores. Using them efficiently however remains a challenge in many models as it requires adaptations tailored to each program, using low-level code and libraries. In this paper we present MCMAS a generic toolkit allowing an efficient use of many-core architectures through already defined data structures and kernels. The toolkit provides few famous algorithms as diffusion, path-finding or population dynamics that are frequently used in an agent based models. For further needs, MCMAS is based on a flexible architecture that can easily be enriched by new algorithms thanks to development features. The use of the library is illustrated with three models and their performance analysis. Content Type Journal Article Pages 15-31 DOI 10.3233/MGS-150227 Authors Guillaume Laville, FEMTO-ST Institute, CNRS/Université de Franche-Comté, France Christophe Lang, FEMTO-ST Institute, CNRS/Université de Franche-Comté, France Bénédicte Herrmann, FEMTO-ST Institute, CNRS/Université de Franche-Comté, France Laurent Philippe, FEMTO-ST Institute, CNRS/Université de Franche-Comté, France Kamel Mazouzi, Mésocentre de calcul de Franche-Comté Université de Franche-Comté, France Nicolas Marilleau, UMI 209 – UMMISCO, Institut de Recherche Pour le Développement, UPMC, France Journal Multiagent and Grid Systems Online ISSN 1875-9076 Print ISSN 1574-1702 Journal Volume Volume 11 Journal Issue Volume 11, Number 1 / 2015

Description: Coalition formation in multi-agent systems seeks to create efficient agents' alliances in order to perform complex tasks. The main objective of this paper is to measure the impact of the pursuit groups' formation on the capture of different evaders. In order to achieve this goal, we propose a coalition formation algorithm based on Agent-Group-Role organizational model (AGR). This organizational model is used as coordination mechanism with the aim of regrouping the agents in different groups and assigning the roles adequately. Also, we have used Markov Decision process principles (MDP) to control the motion strategies of our agents in the environment. The achieved simulation results reveal the effectiveness of the given method. Content Type Journal Article Pages 1-13 DOI 10.3233/MGS-150226 Authors Mohamed Souidi, Harbin Institute of Technology, Computer Science and Technology, Harbin, Heilongjiang, China Songhao Piao, Harbin Institute of Technology, Computer Science and Technology, Harbin, Heilongjiang, China Guo Li, Harbin Institute of Technology, Computer Science and Technology, Harbin, Heilongjiang, China Lin Chang, Harbin Institute of Technology, Computer Science and Technology, Harbin, Heilongjiang, China Journal Multiagent and Grid Systems Online ISSN 1875-9076 Print ISSN 1574-1702 Journal Volume Volume 11 Journal Issue Volume 11, Number 1 / 2015

Description: Weighted itemset mining has been a widely studied topic in data mining. The reason is that weighted itemset mining considers not only the occurrence of items in transactions but also the individual importance of items. The traditional upper-bound model can be used to handle the weighted itemset mining problem, but a large number of candidates are generated by the model. This work thus presents an improved model to enhance the effectiveness of reducing unpromising candidates. Besides, an effective strategy, projection-based pruning, is proposed as well to tighten upper-bounds of weighted supports for itemsets in the mining process, thus reducing the execution time further. Through a series of experimental evaluation, the results on synthetic and real datasets show that the proposed approach has good performance in both pruning effectiveness and execution efficiency under various parameter settings when compared to some other approaches. Content Type Journal Article Pages 413-429 DOI 10.3233/IDA-150723 Authors Guo-Cheng Lan, Department of Mathematics and Computer Sciences, Fuqling Branch of Fujian Normal University, Fuzhou, Fujian, China Tzung-Pei Hong, Department of Computer Science and Information Engineering, National University of Kaohsiung, Kaohsiung, Taiwan Hong-Yu Lee, Department of Computer Science and Information Engineering, National University of Kaohsiung, Kaohsiung, Taiwan Chun-Wei Lin, IIIRC, School of Computer Science and Technology, Harbin Institute of Technology Shenzhen Graduate School, Shenzhen, Guangdong, China Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 19 Journal Issue Volume 19, Number 2 / 2015

Description: With the development of new technologies more and more information is stored in log files. Analyzing such logs can be very useful for the decision maker. One of the probably best known example is the Web log file analysis where lots of efficient tools have been proposed to extract the top-k accessed pages, the best users or even the patterns describing the behaviors of users on a Web site. These tools take advantages of the well-formed structures of the data. Unfortunately, logs files from the industrial world have very heterogeneous complex structures (e.g., tables, lists, data blocks). For experts, analyzing logs to find messages helping to better understand causes of a failure, if a problem have already occurred in the past or even knowing the main consequences of a failure is a hard, tedious, time-consuming and error-prone task. There is thus a need for new tools helping the experts to easily recognize the appropriate part in logs. Passage retrieval methods have proved to be very useful for extracting relevant parts in documents. In this paper we propose a new approach for automatically split logs files into relevant segments based on their logical units. We characterize the complex logical units found in logs according to their syntactic characteristics. We also introduce the notion of generalized vs-grams which is used to automatically extract the syntactic characteristics of special structures found in log files. Conducted experiments are performed on real datasets from the industrial world to demonstrate the efficiency of our proposal on the recognition of complex logical units. Content Type Journal Article Pages 431-448 DOI 10.3233/IDA-150724 Authors Hassan Saneifar, Raja University, Computer Faculty, Tehran, Iran Stéphane Bonniol, Satin Technologies, MIBI, 672 rue du Mas de Verchant, Montpellier, France Pascal Poncelet, LIRMM – CNRS – University Montpellier 2, Montpellier, France Mathieu Roche, LIRMM – CNRS – University Montpellier 2, Montpellier, France Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 19 Journal Issue Volume 19, Number 2 / 2015

Description: Financial time series analysis is crucial to a successful assets allocation. Applying a matrix factorization technique can generate genuine grouping knowledge for the allocation of assets according to their association with a number of underlying bases. A constrained nonnegative matrix factorization NSMF is proposed to incorporate three penalties in order to compute a solution which can maximize between-base disjointness and volatility difference. A series of quantitative measures are designed for evaluation of bases and their volatility. Different types of real data are used in the experiments and compared regarding clustering consistency. Experimental analysis of historical prices of US blue chip stocks indicates that NSMF is superior to agglomerative clustering and independent component analysis and NSMF can extract bases with a higher discrepancy of volatility. The non-stochasticity constraint increases the dissimilarity of bases and it governs basis deviation over smoothness and sparseness. The clustering results of bases and persistent pairs, which are gained from NSMF, can consolidate our understanding of financial data properties and they provide meaningful knowledge in the construction of a well risk-balanced and diversified portfolio. Content Type Journal Article Pages 315-343 DOI 10.3233/IDA-150719 Authors Jie Wang, Department of Computer Information Systems, Indiana University Northwest, Gary, IN, USA. E-mail: wangjie@iun.edu Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 19 Journal Issue Volume 19, Number 2 / 2015

Description: During the last years, many works focused on the exploitation and the extraction of rare patterns. In fact, these patterns allow conveying knowledge on rare and unexpected events. They are hence useful in several application fields. Nevertheless, a main moan addressed to rare pattern extraction approaches is, on the one hand, their high number and, on the other hand, the low quality of several mined patterns. The latter can indeed not present strong correlations between the items they contain. In order to overcome these limits, we propose to integrate the correlation measure bond aiming at only mining the set of rare patterns fulfilling this measure. A characterization of the resulting set, of rare correlated patterns, is then carried out based on the study of constraints of distinct types induced by the rarity and the correlation. In addition, based on the equivalence classes associated to a closure operator dedicated to the bond measure, we introduce new concise representations of rare correlated patterns as well as the derivation process of the generic bases of the rare correlated association rules. We then design the RcprMiner algorithm allowing an efficient extraction of the proposed concise representations. Carried out experimental studies highlight the very encouraging compactness rates offered by the proposed concise representations and show the good performance of the RcprMiner algorithm. Content Type Journal Article Pages 359-390 DOI 10.3233/IDA-150721 Authors Souad Bouasker, Faculty of Sciences of Tunis, University of Tunis ElManar, LIPAH-LR 11ES14, Tunis, Tunisia Tarek Hamrouni, Faculty of Sciences of Tunis, University of Tunis ElManar, LIPAH-LR 11ES14, Tunis, Tunisia Sadok Ben Yahia, Faculty of Sciences of Tunis, University of Tunis ElManar, LIPAH-LR 11ES14, Tunis, Tunisia Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 19 Journal Issue Volume 19, Number 2 / 2015

Description: Incremental learning is a learning algorithm that can get new information from new training sets without forgetting the acquired knowledge from the previously used training sets. In this paper, an incremental learning algorithm based on ensemble learning is proposed. Then, an application of the proposed algorithm for spam filtering is discussed. The proposed algorithm called incremental RotBoost, assumes the environment is stationary. It trains new weak classifiers for newly arriving data, which are added to the ensemble of classifiers. To evaluate the performance of the proposed algorithm, several computer experiments are conducted. The results of computer experiments show the ability of our proposed algorithm for different tasks in the incremental learning. The results also demonstrate that the proposed algorithm can learn incrementally, and it can learn new classes, as well. Content Type Journal Article Pages 449-468 DOI 10.3233/IDA-150725 Authors Elham Ghanbari, Department of Computer Engineering, Sharif University of Technology, Tehran, Iran Hamid Beigy, Department of Computer Engineering, Sharif University of Technology, Tehran, Iran Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 19 Journal Issue Volume 19, Number 2 / 2015

Description: Evolutionary algorithms are often applied to solve multi-objective optimization problems. Such algorithms effectively generate solutions of wide spread, and have good convergence properties. However, they do not provide any characteristics of the found optimal solutions, something which may be very valuable to decision makers. By performing a post-analysis of the solution set from multi-objective optimization, relationships between the input space and the objective space can be identified. In this study, decision trees are used for this purpose. It is demonstrated that they may effectively capture important characteristics of the solution sets produced by multi-objective optimization methods. It is furthermore shown that the discovered relationships may be used for improving the search for additional solutions. Two multi-objective problems are considered in this paper; a well-studied benchmark function problem with on a beforehand known optimal Pareto front, which is used for verification purposes, and a multi-objective optimization problem of a real-world production system. The results show that useful relationships may be identified by employing decision tree analysis of the solution sets from multi-objective optimizations. Content Type Journal Article Pages 259-278 DOI 10.3233/IDA-150716 Authors Catarina Dudas, Virtual Systems Research Centre, University of Skövde, Skövde, Sweden Amos H.C. Ng, Virtual Systems Research Centre, University of Skövde, Skövde, Sweden Henrik Boström, Department of Computer and Systems Sciences, Stockholm University, Kista, Sweden Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 19 Journal Issue Volume 19, Number 2 / 2015

Description: Holonic multi-agent system (HMAS) offers a promising approach to model complex systems. HMAS is based on self-similar entities defined in a holarchical organization. Although some models and frameworks have been proposed for holonic systems, there is no general reinforcement learning method that can be easily implemented in HMAS. This paper presents a reinforcement learning method for HMAS. The holons in different levels have direct effect on learning process of each other through communication. For hierarchical communications between holons, abstract data flows are defined that are used for state estimation, action selection and reward calculation. The proposed learning method includes a self-similar structure in which the learning processes of the holons are independent of their actual positions in the holarchy. A real-world application is also used to show that how the holons can be implemented in practice. Experimental results show that the proposed holonic reinforcement learning method improves the performance. Content Type Journal Article Pages 211-232 DOI 10.3233/IDA-150714 Authors Monireh Abdoos, Faculty of Computer Science and Engineering, Shahid Beheshti University, Tehran, Iran Nasser Mozayani, School of Computer Engineering, Iran University of Science and Technology, Tehran, Iran Ana L.C. Bazzan, Institute of Informatics, University of Federal Rio Grand do Sul, Porto Alegre, Brazil Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 19 Journal Issue Volume 19, Number 2 / 2015

Description: In this paper, a new co-training algorithm based on modified Fisher's Linear Discriminant Analysis (FLDA) is proposed for semi-supervised learning, which only needs a small set of labeled samples to train classifiers and is thus very useful in applications like brain-computer interface (BCI) design. Two classifiers, one aiming to maximize the normalized between-class diversity and the other to minimize the normalized within-class diversity, are proposed for the co-training process. A method with a confidence criterion is also proposed for selecting unlabeled data to expand training data set. The co-training algorithm is compared with a static FLDA method and a FLDA based on self-training algorithm on the data set 2a for BCI Competition IV, with statistical significance test. Experimental results show that the new co-training algorithm outperformed the other two methods and its average classification accuracy was improved iteration by iteration, demonstrating the convergence of the co-training process. Content Type Journal Article Pages 279-292 DOI 10.3233/IDA-150717 Authors Xue-Min Tan, State Key Laboratory of Power Transmission Equipment & System Security and New Technology, School of Electrical Engineering, Chongqing University, Chongqing, China Min-You Chen, State Key Laboratory of Power Transmission Equipment & System Security and New Technology, School of Electrical Engineering, Chongqing University, Chongqing, China John Q. Gan, School of Computer Science and Electronic Engineering, University of Essex, Colchester, UK Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 19 Journal Issue Volume 19, Number 2 / 2015

Description: We present and study new definitions of universal and programmable universal unary functions and consider a new simplicity criterion: almost decidability of the halting set. A set of positive integers S is almost decidable if there exists a decidable and generic (i.e. a set of natural density one) set whose intersection with S is decidable. Every decidable set is almost decidable, but the converse implication is false. We prove the existence of infinitely many universal functions whose halting sets are generic (negligible, i.e. have density zero) and (not) almost decidable. One result—namely, the existence of infinitely many universal functions whose halting sets are generic (negligible) and not almost decidable—solves an open problem in [9]. We conclude with some open problems. Content Type Journal Article Pages 77-84 DOI 10.3233/FI-2015-1199 Authors Cristian S. Calude, Department of Computer Science, University of Auckland, Private Bag 92019, Auckland, New Zealand. cristian@cs.auckland.ac.nz Damien Desfontaines, École Normale Supérieure, 45 rue d'Ulm, 75005 Paris, France. desfonta@clipper.ens.fr Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: We study the problem of finding small universal reversible Turing machines (URTMs) with four symbols or less. Here, we present two models of URTMs: a 24-state 4-symbol URTM, and a 32-state 3-symbol URTM. Both of them are designed so that they can simulate cyclic tag systems, a kind of string rewriting systems that are universal. By converting the 24-state 4-symbol URTM into a 2-symbol machine, we also obtain a 138-state 2-symbol URTM. Content Type Journal Article Pages 17-29 DOI 10.3233/FI-2015-1195 Authors Kenichi Morita, Hiroshima University, Higashi-Hiroshima, 739-8527, Japan. km@hiroshima-u.ac.jp Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 138 Journal Issue Volume 138, Number 1-2 / 2015

Description: Deterministic domain-independent multiagent planning is an approach to coordination of cooperative agents with joint goals. Provided that the agents act in an uncertain and dynamic environment, such plans can fail. The straightforward approach to recover from such situations is to compute a new plan from scratch, that is to replan. Even though, in a worst case, plan repair or plan re-use does not yield an advantage over replanning from scratch, there is a sound evidence from practical use that approaches trying to repair the failed original plan can outperform replanning in selected problems. One of the possible plan repairing techniques is based on preservation of fragments of the older plans. This work theoretically analyses complexity of plan repairing approaches based on preservation of fragments of the original plan and experimentally studies three practical aspects affecting its efficiency in various multiagent settings. We focus both on the computational, as well as the communication efficiency of plan repair in comparison to replanning from scratch and we report on the influence of the following properties on the efficiency of plan repair: (1) the number of involved agents in the plan repairing process, (2) inter-dependencies among the repaired actions, and finally (3) particular modes of re-use of the older plans. Content Type Journal Article Pages 33-57 DOI 10.3233/MGS-150228 Authors Antonín Komenda, Department of Computer Science, Faculty of Electrical Engineering, Czech Technical University, Prague, Czech Republic Peter Novák, Department of Software and Computer Technology, Faculty of Electrical Engineering, Mathematics and Computer Science, Delft University of Technology, Delft, The Netherlands Michal Pěchouček, Department of Computer Science, Faculty of Electrical Engineering, Czech Technical University, Prague, Czech Republic Journal Multiagent and Grid Systems Online ISSN 1875-9076 Print ISSN 1574-1702 Journal Volume Volume 11 Journal Issue Volume 11, Number 1 / 2015

Description: Information security is an important and growing need. The most common schemes used for detection systems include pattern- or signature-based and anomaly-based. Anomaly-based schemes use a set of metrics, which outline the normal system behavior and any significant deviation from the established profile will be treated as an anomaly. This paper contributes with an anomaly-based scheme that monitors the bandwidth consumption of a subnetwork, at the Universidad Michoacana, in Mexico. A normal behavior model is based on bandwidth consumption of the subnetwork. The presence of an anomaly indicates that something is misusing the network (viruses, worms, denial of service, or any other kind of attack). This work also presents a scheme for an automatic architecture design and parameters optimization of Hidden Markov Models (HMMs), based on Evolutionary Programming (EP). The variables to be used by the HMMs are: the bandwidth consumption of network (IN and OUT), and the associated time where the network activity occurs. The system was tested with univariate and bivariate observation sequences to analyze and detect anomaly behavior. The HMMs, designed and trained by EP, were compared against semi-random HMMs trained by the Baum-Welch algorithm. On a second experiment, the HMMs, designed and trained by EP, were compared against HMMs created by an expert user. The HMMs outperformed the other methods in all cases. Finally, we made the HMMs time-aware, by including time as another variable. This inclusion made the HMMs capable of detecting activity patterns that are normal during a period of time but anomalous at other times. For instance, a heavy load on the network may be completely normal during working times, but anomalous at nights or weekends. Content Type Journal Article Pages 391-412 DOI 10.3233/IDA-150722 Authors Juan J. Flores, Division de Estudios de Posgrado, Facultad de Ingenieria Electrica, Universidad Michoacana, Mexico Felix Calderon, Division de Estudios de Posgrado, Facultad de Ingenieria Electrica, Universidad Michoacana, Mexico Anastacio Antolino, Instituto Tecnologico de Morelia, Depto. de Sistemas y Computacion, Michoacan, Mexico Juan M. Garcia, Instituto Tecnologico de Morelia, Depto. de Sistemas y Computacion, Michoacan, Mexico Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 19 Journal Issue Volume 19, Number 2 / 2015

Description: In this paper we address the problem of clustering interval data, adopting a model-based approach. To this purpose, parametric models for interval-valued variables are used which consider configurations for the variance-covariance matrix that take the nature of the interval data directly into account. Results, both on synthetic and empirical data, clearly show the well-founding of the proposed approach. The method succeeds in finding parsimonious heterocedastic models which is a critical feature in many applications. Furthermore, the analysis of the different data sets made clear the need to explicitly consider the intrinsic variability present in interval data. Content Type Journal Article Pages 293-313 DOI 10.3233/IDA-150718 Authors Paula Brito, FEP & LIAAD INESC TEC, Universidade do Porto, Portugal A. Pedro Duarte Silva, School of Economics and Management and CEGE, Universidade Católica Portuguesa, Portugal José G. Dias, Instituto Universitário de Lisboa (ISCTE-IUL), BRU, Portugal Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 19 Journal Issue Volume 19, Number 2 / 2015

Description: Bayesian Multi-nets (BMNs) are a special kind of Bayesian network (BN) classifiers that consist of several local Bayesian networks, one for each predictable class, to model an asymmetric set of variable dependencies given each class value. Deterministic methods using greedy local search are the most frequently used methods for learning the structure of BMNs based on optimizing a scoring function. Ant Colony Optimization (ACO) is a meta-heuristic global search method for solving combinatorial optimization problems, inspired by the behavior of real ant colonies. In this paper, we propose two novel ACO-based algorithms with two different approaches to build BMN classifiers: ABC-Miner^{mn}_l and ABC-Miner^{mn}_g. The former uses a local learning approach, in which the ACO algorithm completes the construction of one local BN at a time. The latter uses a global approach, which involves building a complete BMN classifier by each single ant in the colony. We experimentally evaluate the performance of our ant-based algorithms on 33 benchmark classification datasets, where our proposed algorithms are shown to be significantly better than other commonly used deterministic algorithms for learning various Bayesian classifiers in the literature, as well as competitive to other well-known classification algorithms. Content Type Journal Article Pages 233-257 DOI 10.3233/IDA-150715 Authors Khalid M. Salama, School of Computing, University of Kent, Canterbury, UK Alex A. Freitas, School of Computing, University of Kent, Canterbury, UK Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 19 Journal Issue Volume 19, Number 2 / 2015

Description: A batch-mode active learning technique taking advantage of the cluster assumption was proposed. It focused on binary classification tasks adopting SVM (support vector machine). In each active learning iteration, unlabeled instances in the SVM margin were first grouped into two clusters. Then from each cluster, points most similar to the other cluster were selected for labeling. Such points lying near the boundary between clusters were expected to become support vectors in the final classification model with high probability. The clustering process was performed in the same kernel space as SVM. With semi-supervised K-medoids, labeled instances were also used to improve the clustering performance. Experiments showed that the proposed method was efficient and robust (to poor initial samples). Content Type Journal Article Pages 345-358 DOI 10.3233/IDA-150720 Authors Chun-Jiang Fu, Department of Automation, Shanghai Jiao Tong University, Key Laboratory of System Control and Information Processing, Ministry of Education, Shanghai, China Yu-Pu Yang, Department of Automation, Shanghai Jiao Tong University, Key Laboratory of System Control and Information Processing, Ministry of Education, Shanghai, China Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 19 Journal Issue Volume 19, Number 2 / 2015

Description: Particle Swarm Optimization (PSO) is a well known technique for solving various kinds of combinatorial optimization problems including scheduling, resource allocation and vehicle routing. However, basic PSO suffers from premature convergence problem. Many techniques have been proposed for alleviating this problem. One of the alternative approaches is hybridization. Genetic Algorithms (GAs) are one of the possible techniques used for hybridization. Most often, a mutation scheme is added to the PSO, but some applications of crossover have been added more recently. Some of these schemes use dynamic parameterization when applying the GA operators. In this work, dynamic parameterized mutation and crossover operators are combined with a PSO implementation individually and in combination to test the effectiveness of these additions. The results indicate that all the PSO hybrids with dynamic probability have shown satisfactory performance in finding the best distance of the Vehicle Routing Problem With Time Windows. Content Type Journal Article Pages 13-25 DOI 10.3233/HIS-140202 Authors S. Masrom, Faculty of Computer and Mathematical Sciences, Universiti Teknologi MARA Perak, Malaysia Siti Z.Z. Abidin, Faculty of Computer and Mathematical Sciences, Universiti Teknologi MARA Shah Alam, Malaysia N. Omar, Faculty of Computer and Mathematical Sciences, Universiti Teknologi MARA Shah Alam, Malaysia K. Nasir, Faculty of Computer and Mathematical Sciences, Universiti Teknologi MARA Shah Alam, Malaysia A.S. Abd Rahman, Faculty of Science and Information Technology, Universiti Teknologi PETRONAS, Perak, Malaysia Journal International Journal of Hybrid Intelligent Systems Online ISSN 1875-8819 Print ISSN 1448-5869 Journal Volume Volume 12 Journal Issue Volume 12, Number 1 / 2015

Description: Distributed Denial of Service (DDoS) attack is a coordinated effort between several machines to attack one or multiple target systems. Indeed, the attack is through imposing additional burden on system resources or flood computation and communication resources, the server services for legitimate users, are unavailable. In general, if we have categorized security into three areas of confidentiality, integrity and availability, distributed denial of service attacks threaten a third option. Since the distributed denial of service attacks caused by improper operation of information system and its users from accessing the services excluded and also to maintain vital system resources, such attacks are detected immediately. Hence, in this paper, we investigate such attacks and some of their detection mechanisms. In this paper, initially introduced such attacks, then are presented the various categories of these attacks, afterwards, several methods have been proposed to detect distributed denial of service attacks. Finally, these methods are compared and the advantages and disadvantages of them are briefly mentioned. Content Type Journal Article Pages 329-345 DOI 10.3233/JCM-140510 Authors Marjan Kuchaki Rafsanjani, Department of Computer Science, Shahid Bahonar University of Kerman, Kerman, Iran Neda Kazeminejad, Department of Computer Science, Shahid Bahonar University of Kerman, Kerman, Iran Journal Journal of Computational Methods in Science and Engineering Online ISSN 1875-8983 Print ISSN 1472-7978 Journal Volume Volume 14 Journal Issue Volume 14, Number 6 / 2014

Description: In this paper, we present a new iterative method of convergence order five for solving nonlinear systems. Per iteration the new method requires the evaluations of two functions, two first derivatives and one matrix inversion. The computational efficiency index is used to compare the efficiency of different methods. Numerical tests are performed, which confirm the theoretical results. From the comparison with the existing methods it is observed that the new method is more efficient in both computational efficiency and computational time. Content Type Journal Article Pages 363-372 DOI 10.3233/JCM-140512 Authors Xiao-Feng Wang, School of Mathematics and Physics, Bohai University, Jinzhou, Liaoning, China Tie Zhang, College of Sciences, Northeastern University, Shenyang, Liaoning, China Fu Zheng, School of Mathematics and Physics, Bohai University, Jinzhou, Liaoning, China Wei-Yi Qian, School of Mathematics and Physics, Bohai University, Jinzhou, Liaoning, China Journal Journal of Computational Methods in Science and Engineering Online ISSN 1875-8983 Print ISSN 1472-7978 Journal Volume Volume 14 Journal Issue Volume 14, Number 6 / 2014

Description: A new hybrid method for minimization of bandwidth and other parameters of large sparse symmetric equation systems is described. The improved efficiency is achieved by a~convenient combination of some new techniques: In the first global phase numbering schemas are developed first in usual operating mode from starting node away, then in backward direction as well, in both cases using jumping. A considerable reduction of the CPU-time consumption accompanied by still competitive results can be achieved through eliminating the number of nearby starting nodes. The solution is further improved by a local iterative second phase. Here, local minima are escaped with the help of partial reversing. The performance of the method is evaluated on both artificial and real meshes. Extremely branched artificial meshes for 12 finite element types from structural engineering have been created by a simple uniform algorithm. Minimal bandwidths achieved are given as etalon values for further research. Source code of the artificial mesh generators is freely available. An in-depth evaluation and comparison with the state-of-the-art methods on 45 real meshes from different engineering areas demonstrates the efficiency of the proposed algorithm. Content Type Journal Article Pages 347-362 DOI 10.3233/JCM-140511 Authors L'ubomír Ondris, Jantárová 8, 040 01 Košice, Slovakia. E-mail: lubomir.ondris@gmail.com Journal Journal of Computational Methods in Science and Engineering Online ISSN 1875-8983 Print ISSN 1472-7978 Journal Volume Volume 14 Journal Issue Volume 14, Number 6 / 2014

Description: We review theoretical studies on the synthesis of the neutron from the hydrogen atom in the core of stars; we outline tests conducted in the 1960s on the laboratory synthesis of the neutron by C. Borghi and his collaborators; we outline the confirmatory tests conducted in the 1990s by R.M. Santilli; and we present new tests apparently confirming that neutrons can be synthesized in laboratory from a hydrogen gas. Content Type Journal Article Pages 405-414 DOI 10.3233/JCM-140509 Authors Ruggero Maria Santilli, Thunder Energies Corporation, Tarpon Springs, FL, USA Alex Nas, Thunder Energies Corporation, Tarpon Springs, FL, USA Journal Journal of Computational Methods in Science and Engineering Online ISSN 1875-8983 Print ISSN 1472-7978 Journal Volume Volume 14 Journal Issue Volume 14, Number 6 / 2014

Description: Regular Papers Content Type Journal Article Pages 165-165 Journal Semantic Web Online ISSN 2210-4968 Print ISSN 1570-0844 Journal Volume Volume 6 Journal Issue Volume 6, Number 2 / 2015

Description: P systems have been proven to be useful as modeling tools in many fields, such as Systems Biology and Ecological Modeling. For such applications, the acceleration of P system simulation is often desired, given the computational needs derived from these kinds of models. One promising solution is to implement the inherent parallelism of P systems on platforms with parallel architectures. In this respect, GPU computing proved to be an alternative to more classic approaches in Parallel Computing. It provides a low cost, and a manycore platform with a high level of parallelism. The GPU has been already employed to speedup the simulation of P systems. In this paper, we look over the available parallel P systems simulators on the GPU, with special emphasis on those included in the PMCGPU project, and analyze some useful guidelines for future implementations and developments. Content Type Journal Article Pages 269-284 DOI 10.3233/FI-2015-1157 Authors Miguel A. Martínez-del-Amor, Research Group on Natural Computing, Universidad de Sevilla, Seville, Spain. mdelamor@us.es Manuel García-Quismondo, University of Minnesota, Minneapolis-St. Paul, United States. mgarciaquismondo@us.es Luis F. Macías-Ramos, Research Group on Natural Computing, Universidad de Sevilla, Seville, Spain. {lfmaciasr,lvalencia,ariscosn,marper}@us.es Luis Valencia-Cabrera, Research Group on Natural Computing, Universidad de Sevilla, Seville, Spain. {lfmaciasr,lvalencia,ariscosn,marper}@us.es Agustin Riscos-Núñez, Research Group on Natural Computing, Universidad de Sevilla, Seville, Spain. {lfmaciasr,lvalencia,ariscosn,marper}@us.es Mario J. Pérez-Jiménez, Research Group on Natural Computing, Universidad de Sevilla, Seville, Spain. {lfmaciasr,lvalencia,ariscosn,marper}@us.es Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 136 Journal Issue Volume 136, Number 3 / 2015

Description: Limited automata are one-tape Turing machines which are allowed to rewrite each tape cell only in the first d visits, for a given constant d. For each d ≥ 2, these devices characterize the class of context-free languages. We investigate the equivalence between 2-limited automata and pushdown automata, comparing the relative sizes of their descriptions. We prove exponential upper and lower bounds for the sizes of pushdown automata simulating 2-limited automata. In the case of the conversion of deterministic 2-limited automata into deterministic pushdown automata the upper bound is double exponential and we conjecture that it cannot be reduced. On the other hand, from pushdown automata we can obtain equivalent 2-limited automata of polynomial size, also preserving determinism. From our results, it follows that the class of languages accepted by deterministic 2-limited automata coincides with the class of deterministic context-free languages. Content Type Journal Article Pages 157-176 DOI 10.3233/FI-2015-1148 Authors Giovanni Pighizzini, Dipartimento di Informatica, Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy. pighizzini@di.unimi.it, andrea.pisoni1@studenti.unimi.it Andrea Pisoni, Dipartimento di Informatica, Università degli Studi di Milano, via Comelico 39, 20135 Milano, Italy. pighizzini@di.unimi.it, andrea.pisoni1@studenti.unimi.it Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 136 Journal Issue Volume 136, Number 1-2 / 2015

Description: Deterministic one-way Turing machines with sublinear space bounds are systematically studied. We distinguish among the notions of strong, weak, and restricted space bounds. The latter is motivated by the study of P automata. The space available on the work tape depends on the number of input symbols read so far, instead of the entire input. The class of functions space constructible by such machines is investigated, and it is shown that every function f that is space constructible by a deterministic two-way Turing machine, is space constructible by a strongly f space-bounded deterministic one-way Turing machine as well. We prove that the restricted mode coincides with the strong mode for space constructible functions. The known infinite, dense, and strict hierarchy of strong space complexity classes is derived also for the weak mode by Kolmogorov complexity arguments. Finally, closure properties under AFL operations, Boolean operations and reversal are shown. Content Type Journal Article Pages 139-155 DOI 10.3233/FI-2015-1147 Authors Martin Kutrib, Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. kutrib@informatik.uni-giessen.de Julien Provillard, Laboratoire I3S, Université Nice Sophia Antipolis, 06903 Sophia Antipolis Cedex, France. julien.provillard@i3s.unice.fr György Vaszil, Department of Computer Science, University of Debrecen, 4028 Debrecen, Kassai út 26, Hungary. vaszil.gyorgy@inf.unideb.hu Matthias Wendlandt, Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. matthias.wendlandt@informatik.uni-giessen.de Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 136 Journal Issue Volume 136, Number 1-2 / 2015

Description: In 2007, tense Łukasiewicz–Moisil algebras were introduced by Diaconescu and Georgescu as an algebraic counterpart of tense n–valued Moisil logic. These algebras constitute a generalization of tense algebras. In this paper we describe a discrete duality for tense Łukasiewicz–Moisil algebras bearing in mind the results indicated by Dzik, Orłowska and van Alten in 2006, for De Morgan algebras. Content Type Journal Article Pages 317-329 DOI 10.3233/FI-2015-1160 Authors Aldo V. Figallo, Instituto de Ciencias Básicas, Universidad Nacional de San Juan, San Juan, Argentina. avfigallo@gmail.com; gpelaitay@gmail.com Gustavo Pelaitay, Instituto de Ciencias Básicas, Universidad Nacional de San Juan, San Juan, Argentina. avfigallo@gmail.com; gpelaitay@gmail.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 136 Journal Issue Volume 136, Number 4 / 2015

Description: The protein structure folding is one of the most challenging problems in the field of bioinformatics. The main problem of protein structure prediction in the 3D toy model is to find the lowest energy conformation. Although many heuristic algorithms have been proposed to solve the protein structure prediction (PSP) problem, the existing algorithms are far from perfect since PSP is an NP-problem. In this paper, we proposed an artificial bee colony (ABC) algorithm based on the toy model to solve PSP problem. In order to improve the global convergence ability and convergence speed of the ABC algorithm, we adopt a new search strategy by combining the global solution into the search equation. Experimental results illustrate that the suggested algorithm can get the lowest energy when the algorithm is applied to the Fibonacci sequences and to four real protein sequences which come from the Protein Data Bank (PDB). Compared with the results obtained by PSO, LPSO, PSO-TS, PGATS, our algorithm is more efficient. Content Type Journal Article Pages 241-252 DOI 10.3233/FI-2015-1155 Authors Yanzhang Li, Key Laboratory of Advanced Design and Intelligent Computing, Ministry of Education, Dalian University, No.10 Xuefu Street, Jinzhou New District, Dalian, Liaoning Province, China. zhouchangjun@dlu.edu.cn; liyan8815@126.com; zhengxuedong@dlu.edu.cn Changjun Zhou, Key Laboratory of Advanced Design and Intelligent Computing, Ministry of Education, Dalian University, No.10 Xuefu Street, Jinzhou New District, Dalian, Liaoning Province, China. zhouchangjun@dlu.edu.cn; liyan8815@126.com; zhengxuedong@dlu.edu.cn Xuedong Zheng, Key Laboratory of Advanced Design and Intelligent Computing, Ministry of Education, Dalian University, No.10 Xuefu Street, Jinzhou New District, Dalian, Liaoning Province, China. zhouchangjun@dlu.edu.cn; liyan8815@126.com; zhengxuedong@dlu.edu.cn Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 136 Journal Issue Volume 136, Number 3 / 2015

Description: A web service is an application that is published on the web and can be discovered and used automatically. In many cases, a web service cannot provide the capability that the user has requested. Therefore, according to the user request, it should be possible to combine various services and produce a new composite service for user request. AI planning techniques are used for automated web service composition. Also, context is the information that can be used to characterize the situation of an entity. JSHOP2 is one of the techniques of planning. In this paper, the design and implementation of the proposed framework for context-aware web service composition is presented and is used JSHOP2 and the proposed framework reduces the number of failures and composition time. Content Type Journal Article Pages 185-197 DOI 10.3233/MGS-140222 Authors Maryam Omid, Department of Computer Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran Faramarz Safi-Esfahani, Department of Computer Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran Mohammad-Hossein Nadimi-Shahraki, Department of Computer Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran Journal Multiagent and Grid Systems Online ISSN 1875-9076 Print ISSN 1574-1702 Journal Volume Volume 10 Journal Issue Volume 10, Number 4 / 2014

Description: In previous researches of cloud manufacturing services, trust evaluation models were not flexible enough and subjective preferences of agents were not reflected either. For this issue, a five-dimensional trust evaluation system is built, and a reputation-based trust evaluation algorithm (RBTE) is also proposed. The direct trust rank (DT), friend reputation (RF) and platform reputation (RP) of the agent could be integrated into the trust rank (TR) with the weight vector through this algorithm. Combined with similarities of trust evaluation process, a trust network building approach is put forward in this research. The trust rank update algorithm also achieved dynamic rewards or punishments over time. Experimental results has shown good executing efficiency, and reflected the subjective preference of the transaction agent to a certain extent. Content Type Journal Article Pages 233-246 DOI 10.3233/MGS-140225 Authors Wei Meng, Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu, Sichuan, China Shaobo Li, Chengdu Institute of Computer Application, Chinese Academy of Sciences, Chengdu, Sichuan, China Guanci Yang, Key Laboratory of Advanced Manufacturing Technology of Ministry of Education, Guizhou University, Guiyang, Guizhou, China Zhonghe Wei, Department of Computer Science, Guizhou University, Guiyang, Guizhou, China Journal Multiagent and Grid Systems Online ISSN 1875-9076 Print ISSN 1574-1702 Journal Volume Volume 10 Journal Issue Volume 10, Number 4 / 2014

Description: Lexvo.org brings information about languages, words, and other linguistic entities to the Web of Linked Data. It defines URIs for terms, languages, scripts, and characters, which are not only highly interconnected but also linked to a variety of resources on the Web. Additionally, new datasets are being published to contribute to the emerging Linked Data Cloud of Language-Related information. Content Type Journal Article Pages - DOI 10.3233/SW-150171 Authors Gerard de Melo, IIIS, FIT 1-208, Tsinghua University, Beijing 10084, China. E-mail: demelo@icsi.berkeley.edu Journal Semantic Web Online ISSN 2210-4968 Print ISSN 1570-0844

Description: 2nd Special Issue on Linked Dataset Descriptions Content Type Journal Article Pages 101-101 Journal Semantic Web Online ISSN 2210-4968 Print ISSN 1570-0844 Journal Volume Volume 6 Journal Issue Volume 6, Number 2 / 2015

Description: We consider the weighted satisfiability problem for Boolean circuits and propositional formulæ, where the weight of an assignment is the number of variables set to true. We study the parameterized complexity of these problems and initiate a systematic study of the complexity of its fragments. Only the monotone fragment has been considered so far and proven to be of same complexity as the unrestricted problems. Here, we consider all fragments obtained by semantically restricting circuits or formulæ to contain only gates (connectives) from a fixed set B of Boolean functions. We obtain a dichotomy result by showing that for each such B, the weighted satisfiability problems are either W[P]-complete (for circuits) or W[SAT]-complete (for formulæ) or efficiently solvable. We also consider the related enumeration and counting problems. Content Type Journal Article Pages 297-316 DOI 10.3233/FI-2015-1159 Authors Nadia Creignou, Aix-Marseille Université, CNRS, LIF UMR 7279, 13288, Marseille, France. creignou@lif.univ-mrs.fr Heribert Vollmer, Institut für Theoretische Informatik, Leibniz Universität Hannover, Appelstr. 4, 30167 Hannover, Germany. vollmer@thi.uni-hannover.de Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 136 Journal Issue Volume 136, Number 4 / 2015

Description: It is known that the Common Algorithmic Problem (CAP) has the nice property that several other NP-complete problems can be reduced to it in linear time. The decision version of this problem is known to be efficiently solved by a family of recognizer P systems with active membranes with three electrical charges working in the maximally parallel way. We here work with a variant of P systems with active membranes without polarizations and present a uniform solution to CAP in the minimally parallel mode. Content Type Journal Article Pages 285-296 DOI 10.3233/FI-2015-1158 Authors Yunyun Niu, School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China. niuyunyun1003@163.com Ibrahim Venkat, School of Computer Sciences, Universiti Sains Malaysia, Penang 11800, Malaysia. ibrahim@cs.usm.my, tajudin@cs.usm.my, kgsmani1948@yahoo.com Ahamad Tajudin Khader, School of Computer Sciences, Universiti Sains Malaysia, Penang 11800, Malaysia. ibrahim@cs.usm.my, tajudin@cs.usm.my, kgsmani1948@yahoo.com K.G. Subramanian, School of Computer Sciences, Universiti Sains Malaysia, Penang 11800, Malaysia. ibrahim@cs.usm.my, tajudin@cs.usm.my, kgsmani1948@yahoo.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 136 Journal Issue Volume 136, Number 3 / 2015

Description: Synchronous systems of parallel communicating one-way finite automata have already been investigated. There, all components work stepwise in parallel, and the communication between the components is realized by requesting states in a one-directional manner. This means that one component can request information in form of the current state from another component, where the latter one sends its current state without realizing that a communication takes place. Here, we introduce asynchronous systems of parallel communicating one-way and two-way finite automata with a bidirectional communication protocol. A communication only takes place, when both components - the requesting and the responding component - are ready to communicate. It is shown that almost all language classes that are characterized by these systems coincide with the language classes that are characterized by multi-head finite automata. Moreover, our communication protocol uses blocking point-to-point communications, i.e. a communication takes place between two components, and a communicating component is blocked until the communication has been finished. There have also been studied asynchronous systems of finite automata with non-blocking communication in the literature. Thus, we compare synchronous and asynchronous systems on the one hand and asynchronous systems with blocking and non-blocking communication on the other hand. Finally, we give some results on the communication complexity of our systems, where the amount of communication is measured by counting each message which is sent from one component to another during a computation of a system. Particularly, we show that with constantly many communications our systems can only accept regular languages, and at most linearly (polynomially) many communications are needed for systems of one-way (two-way) components depending on the length of the input. Further, there exists no system that executes more than constantly many and less than linearly many communications. Content Type Journal Article Pages 177-197 DOI 10.3233/FI-2015-1149 Authors Marcel Vollweiler, Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany. vollweiler@theory.informatik.uni-kassel.de Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 136 Journal Issue Volume 136, Number 1-2 / 2015

Description: Spiking neural P systems with astrocytes (SNPA systems, for short) are a class of distributed parallel computing devices inspired from the way spikes pass along the synapses between neurons. In this work, we investigate the computational power of SNPA systems as language generators. Specifically, representations of recursively enumerable languages and of regular languages are given by means of SNPA systems without forgetting rules. Furthermore, a simple finite language is produced which can be generated by SNPA systems, while it cannot be generated by usual spiking neural P systems. These results show that the astrocytes are a powerful ingredient for spiking neural P systems as language generators. Content Type Journal Article Pages 231-240 DOI 10.3233/FI-2015-1154 Authors Yuan Kong, Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China. kongyuan1122@126.com; leaf@mail.hust.edu.cn; yangliu30@gmail.com Zheng Zhang, Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China. kongyuan1122@126.com; leaf@mail.hust.edu.cn; yangliu30@gmail.com Yang Liu, Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China. kongyuan1122@126.com; leaf@mail.hust.edu.cn; yangliu30@gmail.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 136 Journal Issue Volume 136, Number 3 / 2015

Description: Single k-reversible restarting automata are a special version of restarting automata which can be effectively learned from samples. We show that their power lies between GCSL and CSL. We show that their subclasses form an infinite hierarchy of classes of languages with respect to the reversibility level k and we also show that limiting types of allowed rewrites lowers the power of the model. Finally, we study their relation to strictly locally testable restarting automata. Content Type Journal Article Pages 85-112 DOI 10.3233/FI-2015-1145 Authors Petr Hoffmann, Faculty of Mathematics and Physics, Charles University in Prague, Malostranské nám. 25, 118 00, Praha 1, Czech Republic. krysar78@gmail.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 136 Journal Issue Volume 136, Number 1-2 / 2015

Description: Spiking neural P systems with astrocytes (SNPA systems, for short) are a class of distributed parallel computing devices inspired from the way neurons communicate by means of spikes. In this work, we investigate the reversibility in SNPA systems as well as the computational power of reversible SNPA systems. It is proved that reversible SNPA systems are universal, where the forgetting rules and the feature of delay in spiking rules are not used, and each neuron contains only one spiking rule. The result suggests that the astrocytes play a key role in the functioning of reversible SNPA systems. Content Type Journal Article Pages 219-230 DOI 10.3233/FI-2015-1153 Authors Yuan Kong, Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China. kongyuan1122@126.com; xiaolongshi@mail.hust.edu.cn; xujinbang@163.com Xiaolong Shi, Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China. kongyuan1122@126.com; xiaolongshi@mail.hust.edu.cn; xujinbang@163.com Jinbang Xu, Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China. kongyuan1122@126.com; xiaolongshi@mail.hust.edu.cn; xujinbang@163.com Xinquan Huang, School of Computer Science, Wuhan University of Science and Technology, Wuhan 430081, Hubei, China. 245817568@qq.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 136 Journal Issue Volume 136, Number 3 / 2015

Description: We show how to minimize biautomata with adaptations of classical minimization algorithms for ordinary deterministic finite automata and moreover by a Brzozowski-like minimization algorithm by applying reversal and power-set construction twice to the biautomaton under consideration. Biautomata were recently introduced in [O. KLÍMA, L. POLÁK: On biautomata. RAIRO—Theor. Inf. Appl., 46(4), 2012] as a generalization of ordinary finite automata, reading the input from both sides. The correctness of the Brzozowski-like minimization algorithm needs a little bit more argumentation than for ordinary finite automata since for a biautomaton its dual or reverse automaton, built by reversing all transitions, does not necessarily accept the reversal of the original language. To this end we first use the recently introduced notion of nondeterminism for biautomata [M. HOLZER, S. JAKOBI: Nondeterministic Biautomata and Their Descriptional Complexity. In: 15th DCFS, Number 8031 of LNCS, 2013] and take structural properties of the forward- and backward-transitions of the automaton into account. This results in a variety of biautomata models, the accepting power of which is characterized. As a byproduct we give a simple structural characterization of cyclic regular and commutative regular languages in terms of deterministic biautomata. Content Type Journal Article Pages 113-137 DOI 10.3233/FI-2015-1146 Authors Markus Holzer, Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. {holzer,sebastian.jakobi}@informatik.uni-giessen.de Sebastian Jakobi, Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. {holzer,sebastian.jakobi}@informatik.uni-giessen.de Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 136 Journal Issue Volume 136, Number 1-2 / 2015

Description: Spiking neural P systems (SN P systems for short) are a class of neural-like computing models in the framework of membrane computing. Inspired by the neurophysiological structure of the brain, SN P systems have been extended in various ways. P–Lingua is a standard language for the definition of P systems, where pLinguaCore library provides particular implementations of parsers and simulators for the models specified in P–Lingua. A support for simulating SN P systems in P–Lingua was introduced recently and soon expanded to cover further features of these systems. In this paper, we present an extension of P–Lingua related to asynchronous SN P systems, in order to incorporate simulation capabilities for limited asynchronous SN P systems and asynchronous SN P systems with local synchronization. Content Type Journal Article Pages 253-267 DOI 10.3233/FI-2015-1156 Authors Luis F. Macías-Ramos, Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n. 41012 Sevilla, Spain. lfmaciasr@us.es, marper@us.es Mario J. Pérez-Jiménez, Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n. 41012 Sevilla, Spain. lfmaciasr@us.es, marper@us.es Tao Song, Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China. lqpan@mail.hust.edu.cn Linqiang Pan, Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China. lqpan@mail.hust.edu.cn Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 136 Journal Issue Volume 136, Number 3 / 2015

Description: Opportunistic grid computing is an emergent paradigm that combines idle volunteer nodes from enterprises in different geographic locations into a cost effective, converged high performance commodity computing grid. This paper presents the MAOG design; an implementation process for an infrastructure optimized for sharing computational cycles and disk space from commodity computers utilizing Multi-Agent Systems. The proposed approach brings transparent and pervasive grid user access to resources which would otherwise not be available to their disposal. An appraisal of the code mobility model to be utilized for the MAOG design in two phases (Mobile Agent and Remote Evaluation design paradigms), adopting the Contract Net Protocol is analyzed. This paper presents in detail, the main components that make up the Mobile Agent design, including the message passing model for achieving the specified service objectives. Content Type Journal Article Pages 199-212 DOI 10.3233/MGS-140223 Authors Raymond Muranganwa, Telkom Centre of Excellence in ICT for Development, Department of Computer Science, University of Fort Hare, Alice, South Africa Mamello Thinyane, Telkom Centre of Excellence in ICT for Development, Department of Computer Science, University of Fort Hare, Alice, South Africa Journal Multiagent and Grid Systems Online ISSN 1875-9076 Print ISSN 1574-1702 Journal Volume Volume 10 Journal Issue Volume 10, Number 4 / 2014

Description: In this paper we present a methodology to produce efficient multistep methods with constant coefficients for second order initial or boundary value problems with periodical and/or oscillating solutions. The methodology which we knew until now was the developed by Simos and co-workers (see [6]) and was based on the minimization of the phase-lag. With this methodology we couldn't know for the specific coefficients the order of the phase-lag derivatives. With the proposed methodology we can determine the free coefficients of a multistep method not only via the minimization of the phase-lag but via also the the minimization of the derivatives of the phase-lag. With this new methodology we can know at the end of analysis the order of phase-lag but also the order of the derivatives of the phase-lag. Content Type Journal Article Pages 373-382 DOI 10.3233/JCM-150520 Authors Yu Wang, Beijing Polytechnic, Beijing 100176, China. E-mail: wangywangyu@163.com Journal Journal of Computational Methods in Science and Engineering Online ISSN 1875-8983 Print ISSN 1472-7978 Journal Volume Volume 14 Journal Issue Volume 14, Number 6 / 2014

Description: Volume of red blood cell is an important factor in distinguishing its abnormalities. Mean corpuscular volume (MCV) of red blood cells contributes much to differentiation of several blood diseases like iron deficiency and other types of anemia. This paper proposes an automated system to classify blood samples using cell microscopic images instead of pathology test results. Adaptive local thresholding is first used to segment cell images. The volumes of red cells are then estimated by assuming torus geometry for cells. Finally, an adaptive network-based fuzzy inference system (ANFIS) is used to classify blood samples to normal and abnormal. Accuracy of the proposed system and area under Receiver Operating Characteristics (ROC) curve are 100% and 1 respectively. Content Type Journal Article Pages 385-394 DOI 10.3233/JCM-140507 Authors Nahid Babazadeh Khameneh, Department of Artificial Intelligence, Science and Research Branch, Islamic Azad University, Tehran, Iran Hossein Arabalibeik, Research Center for Biomedical Technology and Robotics (RCBTR), Tehran University of Medical Sciences, Tehran, Iran Saeed Setayeshi, Medical Radiation Engineering Department, Amirkabir University of Technology, Tehran, Iran Journal Journal of Computational Methods in Science and Engineering Online ISSN 1875-8983 Print ISSN 1472-7978 Journal Volume Volume 14 Journal Issue Volume 14, Number 6 / 2014

Description: The Cooperative Motion Algorithm is an efficient lattice method to simulate dense polymer systems and is often used with two different criteria to generate a Markov chain in the configuration space. While the first method is the well-established Metropolis algorithm, the other one is an heuristic algorithm which needs justification. As an introductory step towards justification for the 3D lattice polymers, we study a simple system which is the binary equimolar fluid on a 2D triangular lattice. Since all lattice sites are occupied only selected type of motions are considered, such the vacancy movements, swapping neighboring lattice sites (Kawasaki dynamics) and cooperative loops. We compare both methods, calculating the energy as well as heat capacity as a function of temperature. The critical temperature, which was determined using the Binder cumulant, was the same for all methods with the simulation accuracy and in agreement with the exact critical temperature for the Ising model on the 2D triangular lattice. In order to achieve reliable results at low temperatures we employ the parallel tempering algorithm which enables simultaneous simulations of replicas of the system in a wide range of temperatures. Content Type Journal Article Pages 395-404 DOI 10.3233/JCM-140508 Authors P. Knychała, The President Stanislaw Wojciechowski Higher Vocational State School in Kalisz ul, Kalisz, Poland M. Banaszak, Faculty of Physics, A. Mickiewicz University, Poznan, Poland Journal Journal of Computational Methods in Science and Engineering Online ISSN 1875-8983 Print ISSN 1472-7978 Journal Volume Volume 14 Journal Issue Volume 14, Number 6 / 2014

Description: This paper investigates the performance of an adaptive controller using a multi-layer quantum neural network (QNN) comprising qubit-inspired neurons as information processing units. The control system is a self-tuning controller whose control parameters are tuned online by the QNN to track plant output relative to the desired plant output generated by a reference model. A proportional-integral-derivative (PID) controller is utilized as a conventional controller, with its parameters tuned by the QNN. Computational experiments to control a single-input single-output discrete-time non-linear plant are conducted to evaluate the capability and characteristics of the quantum neural self-tuning controller. The experiment results demonstrate the feasibility and effectiveness of the proposed controller. Content Type Journal Article Pages 41-52 DOI 10.3233/HIS-140204 Authors Kazuhiko Takahashi, Information Systems Design, Doshisha University, Kyoto, Japan Yuka Shiotani, Information Systems Design, Doshisha University, Kyoto, Japan Masafumi Hashimoto, Intelligent Information Engineering and Science, Doshisha University, Kyoto, Japan Journal International Journal of Hybrid Intelligent Systems Online ISSN 1875-8819 Print ISSN 1448-5869 Journal Volume Volume 12 Journal Issue Volume 12, Number 1 / 2015

Description: Reversals are operations of great biological significance for the analysis of the evolutionary distance between organisms. Genome rearrangement through reversals, consists in finding the shortest sequence of reversals to transform one genome represented as a signed or unsigned permutation into another. When genes are non oriented and correspondingly permutations are unsigned, sorting by reversals came arise as a challenging problem in combinatorics of permutations. In fact, this problem is known to be NP-hard, but the question whether it is NP-complete remains open for more than twenty years. When permutations are signed and correspondingly genes are oriented, the problem is known to be in P. A parallelization of a standard GA (Genetic Algorithm) is proposed for the problem of sorting unsigned permutations. This GA was previously reported in the literature as the most competitive regarding precision for which as control mechanism an 1.5-approximation algorithm was used. For the parallelization, the MPI Library of the C language was used and experiments were performed for calculating the execution time and precision. By increasing the number of individuals, experiment showed improvement in relation to previous approaches. Additionally, a virtualization of the GA using a MicroBlaze processor from Xilinx was performed on OVP for which the average number of executed instructions was of approximately 1.40 Giga instruction per second. In this extended version of this works originally presented in NaBIC 2013 biological data was generated and it was shown how the parallelization can be applied for their analysis. Specifically, the evolutionary distances between different pairs of organism were computed based on the set of non common genes in their mitochondrial DNA genome and the reversal distance between the sequences of common genes. Content Type Journal Article Pages 53-64 DOI 10.3233/HIS-140205 Authors José Luis Soncco-Álvarez, Departments of Computer Science, University of Brasilia, Brasilia, Brazil Gabriel Marchesan Almeida, Institute for Information Processing Technology, Karlsruhe Institute of Technology, Karlsruhe, Germany Juergen Becker, Institute for Information Processing Technology, Karlsruhe Institute of Technology, Karlsruhe, Germany Mauricio Ayala-Rincón, Departments of Computer Science, University of Brasilia, Brasilia, Brazil Journal International Journal of Hybrid Intelligent Systems Online ISSN 1875-8819 Print ISSN 1448-5869 Journal Volume Volume 12 Journal Issue Volume 12, Number 1 / 2015

Description: Recently, it was proposed a novel hybrid approach to train MLPs which combines the advantages of a powerful artificial immune system, called GAIS, with the advantages of Extreme Learning Machine (ELM). In that proposal, the GAIS algorithm is responsible for finding a proper set of input weights whereas the output weights are determined by the Moore-Penrose generalized inverse. The methodology was evaluated only in classification problems and its performance compares favorably with that presented by state-of-the-art-algorithms. Motivated by this scenario, this paper better formalizes the proposal and performs a deeper investigation of its usefulness for synthesizing MLP and RBF neural networks on several real-world classification and regression problems. The computational experiments have shown that the proposed methodology outperforms other approaches in both quantitative and qualitative aspects. Content Type Journal Article Pages 1-12 DOI 10.3233/HIS-140201 Authors Pablo A.D. Castro, Federal Institute of Education, Science and Technology of São Paulo (IFSP), São Carlos, São Paulo, Brazil. E-mail: dalbem@ifsp.edu.br Journal International Journal of Hybrid Intelligent Systems Online ISSN 1875-8819 Print ISSN 1448-5869 Journal Volume Volume 12 Journal Issue Volume 12, Number 1 / 2015

Description: We have developed an approach to identification and tracking of currently unfolding news stories extracted from the news articles published on the Web. Our approach employs a set of agents to retrieve those articles from the Web that might refer to some developing news story. The set of agents is inspired by social insects, in particular by a bee colony. Bees identify popular terms, referred to as story words, relevant to the ongoing news stories and use them in foraging articles. This allows for a dynamic approach that reflects the changes in article space as new stories unfold and new articles are added. Subsequently a graph representation of the article space is constructed that contains retrieved articles and identified story words interconnected by edges according to relationships of relevance identified between elements of the graph. Stories are then extracted from the constructed graph by using Louvain method, commonly used to identify communities within modular graphs. Using this approach we have been able to identify news stories in a stream of articles retrieved from the Web with precision of 75.56%, with best precision generally achieved for recent news stories described by popular story words. Further we developed ways of visualization of multiple stories represented by sets of articles ordered in time. We propose two new metaphors both employing an exponential timeline. Both galactic streams and concurrent streams are highly suitable for visualizing multiple developing stories. Content Type Journal Article Pages 27-39 DOI 10.3233/HIS-140203 Authors Stefan Sabo, Faculty of Informatics and Information Technologies, Slovak University of Technology, Bratislava, Slovakia Alena Kovarova, Faculty of Informatics and Information Technologies, Slovak University of Technology, Bratislava, Slovakia Pavol Navrat, Faculty of Informatics and Information Technologies, Slovak University of Technology, Bratislava, Slovakia Journal International Journal of Hybrid Intelligent Systems Online ISSN 1875-8819 Print ISSN 1448-5869 Journal Volume Volume 12 Journal Issue Volume 12, Number 1 / 2015

Description: This thesis is focused on the study of the Autonomic Computing (AC) paradigm within the scope of Multimedia Communication Systems (MCSs). Specifically, it analyzes the set of autonomic properties and identifies the properties that can be observed in MCSs, specially those suitable to be implemented in a synchronous e-learning platform. Based on this analysis, the aim of this thesis is to design a self-managed multimedia distribution platform for developing synchronous e-learning activities, providing an efficient data delivery service and minimizing the required human intervention. The self-healing and self-optimization techniques of this platform use heuristics to select optimal data distribution paths is spite of failures and member joining and leaving. Content Type Journal Article Pages - DOI 10.3233/AIC-150663 Authors Pelayo Nuño Huergo, Department of Computer Science, University of Oviedo, Gijón, Spain. E-mails: nunopelayo@uniovi.es, jcgranda@uniovi.es Juan Carlos Granda Candás, Department of Computer Science, University of Oviedo, Gijón, Spain. E-mails: nunopelayo@uniovi.es, jcgranda@uniovi.es Journal AI Communications Online ISSN 1875-8452 Print ISSN 0921-7126

Description: The Linked Dataset special issue gathers descriptions of mature and useful datasets thereby awarding researchers and practitioners who create and maintain those datasets with academic recognition. In this editorial, we briefly summarise the contributions to the 2nd special issue on Linked Dataset Descriptions at the Semantic Web Journal. Content Type Journal Article Category Editorial Pages - DOI 10.3233/SW-150170 Authors Jens Lehmann, University of Leipzig, Institute of Computer Science, AKSW Group, Leipzig, Germany. E-mail: lehmann@informatik.uni-leipzig.de Oscar Corcho, Ontology Engineering Group, Universidad Politécnica de Madrid, Boadilla del Monte, Spain. E-mail: ocorcho@fi.upm.es Journal Semantic Web Online ISSN 2210-4968 Print ISSN 1570-0844

Description: Pattern Databases are among the most capable means for solving hard combinatorial problems. Since their conception, they have been enhanced along different directions. Recently, it has been shown that Pattern Databases can induce non-consistent heuristic functions and it has been conjectured that this sort of heuristic functions can be better informed than others. As a matter of fact, non-consistent heuristic functions allow specific rules to take place in order to propagate these inconsistencies with the hope of improving the heuristic estimates at some nodes. Also, it has been studied how to recognize infeasible values in Pattern Databases with the hope of being able to introduce corrections that would allow for more prunes. In this work, a new approach is suggested that fulfills both ideas simultaneously: inducing naturally non-consistent heuristic functions just by recognizing feasible, yet admissible, heuristic values which serve to improve even further the bidirectional pathmax propagation rules. Appealing as it might seem, this idea has various pros and cons which are examined. Experiments on different benchmarks show a noticeable improvement in the number of generated nodes over classical Pattern Databases when applicable, though the difference does not necessarily payoff in running time. Content Type Journal Article Pages - DOI 10.3233/AIC-150666 Authors Carlos Linares López, Computer Science Department, Universidad Carlos III de Madrid, Spain. E-mail: carlos.linares@uc3m.es Journal AI Communications Online ISSN 1875-8452 Print ISSN 0921-7126

Description: Many real life problems that can be modeled as Constraint Satisfaction Problems (CSPs) come from uncertain and dynamic environments, so the original solution found might become invalid after changes. Here, we study the problem of finding robust solutions for CSPs under the assumptions that domains are significantly ordered and that changes take the form of restrictions or relaxations at the borders of the solution space of the CSPs. Content Type Journal Article Pages - DOI 10.3233/AIC-150657 Authors Laura Climent, INSIGHT Center for Data Analytics, University College Cork, Cork, Ireland. E-mails: laura.climent@insight-centre.org, E-mail: richard.wallace@insight-centre.org Miguel A. Salido, Instituto de Automática e Informática Industrial, Universidad Politécnica de Valencia, Valencia, Spain. E-mails: msalido@dsic.upv.es, fbarber@dsic.upv.es Richard J. Wallace, INSIGHT Center for Data Analytics, University College Cork, Cork, Ireland. E-mails: laura.climent@insight-centre.org, E-mail: richard.wallace@insight-centre.org Federico Barber, Instituto de Automática e Informática Industrial, Universidad Politécnica de Valencia, Valencia, Spain. E-mails: msalido@dsic.upv.es, fbarber@dsic.upv.es Journal AI Communications Online ISSN 1875-8452 Print ISSN 0921-7126

Description: Reasoning and change over inconsistent ontologies (i-ont(s)) is of utmost relevance in sciences like medicine and law. Argumentation may be an appropriate formalism to cope with both problems: (reasoning) through an Argumentation Framework (AF) constructed from the i-ont, and (change) by handling the dynamics of its arguments. We propose a new family of abstract AFs referred as generalized (GenAF), due to its ability of adapting to different representation languages. Afterwards, we propose a possible instantiation of the GenAF's abstract language for arguments to the basic ALC description logic for reasoning over i-onts. For dynamics of arguments, a revision operation modifies the graph of arguments in an AF for provoking the argumentation semantics to accept an argument. Thus, revising an ALC-GenAF would introduce a novel methodology for handling evolution of i-onts. To such end, we propose a revision operation by relying upon classic belief revision theory, although contrary to it, consistency restoration is avoided in order to handle evolution with inconsistency tolerance. Content Type Journal Article Pages - DOI 10.3233/AIC-150662 Authors Martín O. Moguillansky, CONICET, AI R&D Lab (LIDIA), Universidad Nacional del Sur (UNS), Bahía Blanca, Argentina. E-mail: mom@cs.uns.edu.ar Journal AI Communications Online ISSN 1875-8452 Print ISSN 0921-7126

Description: Genetic algorithms are commonly used in many types of applications. Yet they suffer from longer execution time and premature convergence. To improve both these factors, the research work proposes two new procedural modifications in the basic genetic algorithm procedure and a new population initialization mechanism. The proposed algorithms are implemented in two types of real world problems of different sizes and the results confirm the superiority of the algorithms over existing ones both in terms of execution time and optimality. Content Type Journal Article Pages - DOI 10.3233/AIC-150661 Authors R. Sivaraj, Velalar College of Engineering and Technology, ???, Tamil Nadu, India. E-mail: rsivarajcse@gmail.com Journal AI Communications Online ISSN 1875-8452 Print ISSN 0921-7126

Description: In the Canadian Traveler Problem (CTP) a traveling agent is given a graph where some of the edges may be blocked with a known probability. The agent has to travel from a given start state to a given goal state. A solution for CTP is a policy, that has the smallest expected traversal cost. CTP is known to be intractable. Previous work has focused on the task of performing a single trip. We generalize CTP to its repeated task version where a number of trips from the start to the goal should be performed (either by the same agent or by multiple agents) while the aim is to minimize the total travel cost in all trips. We provide optimal algorithms for the special case of repeated-task CTP on disjoint path graphs. Based on these findings, we provide a scheme for solving the problem on general graphs. According to this scheme, we first solve a simplified variant of the problem and then apply the solution to the original problem. Empirical results show the benefits of the suggested scheme. For small graphs, where we could compare to optimal policies, our approach achieves near-optimal results with only a fraction of the computation cost. We also provide suboptimal solutions based on UCT that use our heuristics scheme. Experimental results show the benefits of using our scheme for UCT. Content Type Journal Article Pages - DOI 10.3233/AIC-150665 Authors Zahy Bnaya, ??? Ariel Felner, ??? Dror Fried, ??? Olga Maksin, ??? Solomon Eyal Shimony, ??? Journal AI Communications Online ISSN 1875-8452 Print ISSN 0921-7126

Description: The resource perspective has received much less attention than other business process (BP) perspectives, e.g., control flow. This thesis focuses on human resource management in BPs, and addresses challenges related to resource specification and resource analysis by introducing novel techniques for resource specification that rely on a new resource selection language called RAL, and providing automated support for a set of analysis operations at design time and at run time based on the formal semantics of RAL defined in description logics (DLs), leveraging existing DL reasoners. All the contributions have been validated. Content Type Journal Article Pages - DOI 10.3233/AIC-150656 Authors Cristina Cabanillas, Institute for Information Business, Vienna University of Economics and Business, Austria. E-mail: cristina.cabanillas@wu.ac.at Journal AI Communications Online ISSN 1875-8452 Print ISSN 0921-7126

Description: Databases often contain missing values caused in different scenarios. Even though many methods are available to treat such missing values, they are specific to only certain types of missingness and are not commonly applicable to all scenarios. To address this issue, this thesis proposes a novel technique called Bayesian Genetic Algorithm (BAGEL) which combines both Bayesian principles and Genetic Algorithm to impute values in different kinds of missing scenarios and different kinds of attributes in mixed attribute datasets. Content Type Journal Article Pages - DOI 10.3233/AIC-150660 Authors R. Devi Priya, Kongu Engineering College, Tamil Nadu, India. E-mail: scrpriya@gmail.com Journal AI Communications Online ISSN 1875-8452 Print ISSN 0921-7126

Description: Social networking sites are increasingly subject to malicious activities such as self-propagating worms, confidence scams and drive-by-download malwares. The high number of users associated with the presence of sensitive data, such as personal or professional information, is certainly an unprecedented opportunity for attackers. These attackers are moving away from previous platforms of attack, such as emails, towards social networking websites. In this paper, we present a full stack methodology for the identification of campaigns of malicious profiles on social networking sites, composed of maliciousness classification, campaign discovery and attack profiling. The methodology named REPLOT, for REtrieving Profile Links On Twitter, contains three major phases. First, profiles are analysed to determine whether they are more likely to be malicious or benign. Second, connections between suspected malicious profiles are retrieved using a late data fusion approach consisting of temporal and authorship analysis based models to discover campaigns. Third, the analysis of the discovered campaigns is performed to investigate the attacks. In this paper, we apply this methodology to a real world dataset, with a view to understanding the links between malicious profiles, their attack methods and their connections. Our analysis identifies a cluster of linked profiles focusing on propagating malicious links, as well as profiling two other major clusters of attacking campaigns. Content Type Journal Article Pages - DOI 10.3233/AIC-150659 Authors Perez Charles, University of Technology of Troyes, France Emails: charles.perez@utt.fr, babiga.birregah@utt.fr, marc.lemercier@utt.fr Birregah Babiga, University of Technology of Troyes, France Emails: charles.perez@utt.fr, babiga.birregah@utt.fr, marc.lemercier@utt.fr Layton Robert, Federation University, Australia. E-mail: r.layton@icsl.com.au Lemercier Marc, University of Technology of Troyes, France Emails: charles.perez@utt.fr, babiga.birregah@utt.fr, marc.lemercier@utt.fr Watters Paul, Massey University, New Zealand. E-mail: P.A.Watters@massey.ac.nz Journal AI Communications Online ISSN 1875-8452 Print ISSN 0921-7126

Description: Rapidly-exploring Random Trees (RRTs) are data structures and search algorithms designed to be used in continuous path planning problems. They are one of the most successful state-of-the-art techniques in motion planning, as they offer a great degree of flexibility and reliability. However, their use in other fields in which search is a commonly used approach has not been thoroughly analyzed. In this work we propose the use of RRTs as a search algorithm for automated planning. We analyze the advantages and disadvantages that this approach has over previously used search algorithms and the challenges of adapting RRTs for implicit and discrete search spaces. Content Type Journal Article Pages - DOI 10.3233/AIC-150658 Authors Vidal Alcázar, Computer Science Department, Universidad Carlos III de Madrid, Madrid, Spain. E-mails: vidal.alcazar.saiz@gmail.com, sfarregu@inf.uc3m.es, dborrajo@ia.uc3m.es Susana Fernández, Computer Science Department, Universidad Carlos III de Madrid, Madrid, Spain. E-mails: vidal.alcazar.saiz@gmail.com, sfarregu@inf.uc3m.es, dborrajo@ia.uc3m.es Daniel Borrajo, Computer Science Department, Universidad Carlos III de Madrid, Madrid, Spain. E-mails: vidal.alcazar.saiz@gmail.com, sfarregu@inf.uc3m.es, dborrajo@ia.uc3m.es Manuela Veloso, Computer Science Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA. E-mail: mmv@cs.cmu.edu Journal AI Communications Online ISSN 1875-8452 Print ISSN 0921-7126

Description: Artificial Agent Societies are analogous to human societies in which a collection of agents (analogous to humans) are residing or inhabiting a specific locality and are interacting with each other, for some solving common/individual purpose. Social networks, electronic markets and disaster management organizations can be viewed as such artificial (open) agent societies and hence can be best understood as computational societies. The members of such artificial agent societies are heterogeneous intelligent software agents, which are operating locally, cooperating and coordinating with each other in order to achieve goals of an agent society. These open agent societies have some kind of dynamics existing in them, in terms of dynamics of Agent Migration, Role-Assignment, Norm-Emergence, Security and Agent-Interaction. All these dynamic aspects are very closely interrelated to each other, as change in one reflects changes in others also. In this paper, we have presented a survey of all these dynamic aspects of an open agent society at its design-time and have tried to relate them to its member as well as non-member (external) agents. We have also related them, to the migration of a new agent in an open agent society, i.e., how role-assignment will be done for it, various issues related to security and trust of a society upon its arrival, issues related to norm-identification and norm-emergence for it and its communication with the rest of the member agents of the society, that also, during and after its migration. In addition to this, we have also outlined various research challenges and directions available in the area of dynamics of artificial agent societies. Content Type Journal Article Pages - DOI 10.3233/AIC-150664 Authors Harjot Kaur, Department of Computer Science and Engineering, Guru Nanak Dev University, Amritsar, Punjab, India. E-mails: harjotkaursohal@rediffmail.com, karanvkahlon@yahoo.com Karanjeet Singh Kahlon, Department of Computer Science and Engineering, Guru Nanak Dev University, Amritsar, Punjab, India. E-mails: harjotkaursohal@rediffmail.com, karanvkahlon@yahoo.com Journal AI Communications Online ISSN 1875-8452 Print ISSN 0921-7126

Description: Experimental evaluation of algorithms for solving problems with combinatorial explosion Content Type Journal Article Category Guest editorial Pages - DOI 10.3233/AIC-140655 Authors Toni Mancini, Sapienza University, Rome, Italy. E-mail: tmancini@di.uniroma1.it Angelo Oddi, ISTC-CNR, Rome, Italy. E-mail: angelo.oddi@istc.cnr.it Journal AI Communications Online ISSN 1875-8452 Print ISSN 0921-7126

Description: Constrained data clustering algorithms allow the incorporation of a priori knowledge for specific problems into the clustering task in the form of constraints. The quality of the constraints have great impact in the performance of the constrained clustering algorithms. Therefore, special care must be taken while building the sets of constraints. In order to take the maximum advantage of the constrained clustering algorithms, these constraints must be highly informative and non-redundant. We propose two constraint acquisition methods based on user-feedback. The first method searches for non-redundant intra-cluster and inter-cluster query-candidates supported by information contained in an initial partition of the data set, ranks the candidates by decreasing order of interest and, finally, prompts the user the most relevant query-candidates. The constraints may optionally be used for learning a new data representation, which may enhance the performance of clustering. The second method iterates between using the previous method for expanding the set of constraints, and producing an updated partition of the data. The motivation is to iteratively increment the set of constraints by including new informative and non-redundant constraints at each iteration. Experimental results advocate that the proposed constraint acquisition methods increase the performance of data clustering. Content Type Journal Article Pages S47-S64 DOI 10.3233/IDA-140708 Authors João M.M. Duarte, LIAAD-INESC TEC, Porto, Portugal Ana L.N. Fred and, Instituto de Telecomunicações, Instituto Superior Técnico, Lisbon, Portugal F. Jorge F. Duarte, GECAD-ISEP, Institute of Engineering, Polytechnic of Porto, Porto, Portugal Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 18 Journal Issue Volume 18, Supplement 6/ 2014

Description: Fuzzy Cognitive Maps (FCM) may be defined as Recurrent Neural Networks that allow causal reasoning. According to the transformation function used for updating the activation value of concepts they can be characterized as discrete or continuous. It is remarkable that FCM having discrete neurons never exhibit chaotic states, but this premise cannot be guaranteed for FCM having continuous concepts. On the other hand, complex Sigmoid FCM resulting from experts or learning algorithms often show chaotic or cyclic patterns, therefore leading to confusing interpretation of the investigated system. The first contribution of this paper is focused on explaining why most studies on FCM stability are not applicable to FCM used on classification or decision-making tasks. Next we describe a non-direct learning methodology based on Swarm Intelligence for improving the system stability once the causal weight estimation is done. The objective here is to find a specific threshold function for each map neuron simulating an external stimulus, instead of using the same transformation function for all concepts. At the end, we can compute more stable maps, so better consistency in hidden patterns is achieved. Content Type Journal Article Pages S77-S88 DOI 10.3233/IDA-140710 Authors Gonzalo Nápoles, Universidad Central "Marta Abreu" de Las Villas, Villa Clara, Cuba Rafael Bello, Universidad Central "Marta Abreu" de Las Villas, Villa Clara, Cuba Koen Vanhoof, Hasselt University, Hasselt, Belgium Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 18 Journal Issue Volume 18, Supplement 6/ 2014

Description: This paper proposes a novel method for image indexing based on an online learning approach which can deal with large repositories of images. The proposed method is based on a semantic embedding strategy which models a mapping between visual and text representations. This method enhances the image representation by taking advantage of the text annotations associated to the images, which have a rich and clean semantic interpretation. Once the mapping is learned, a new (annotated or unannotated) image can be projected to the space defined by semantic annotations. In this manner, this method can be used to search into the collection using an image as query (query-by-example strategy) and to annotate new unannotated images. The main drawback of semantic embedding strategies is that the associated algorithms are computationally expensive, making them infeasible for large data collections. In order to address this issue, the proposed method is formulated as an online learning algorithm using the stochastic gradient descent approach, which can scale to deal with large image collections. According with the experimental evaluation, the proposed method, in comparison with several baseline methods, is faster and consumes less memory, without degradation in the performance in content-based image search. Content Type Journal Article Pages S101-S114 DOI 10.3233/IDA-140712 Authors Jorge A. Vanegas, MindLab Research Group, Universidad Nacional de Colombia, Bogotá, Colombia Fabio A. González, MindLab Research Group, Universidad Nacional de Colombia, Bogotá, Colombia Journal Intelligent Data Analysis Online ISSN 1571-4128 Print ISSN 1088-467X Journal Volume Volume 18 Journal Issue Volume 18, Supplement 6/ 2014