ALBERT

Beschreibung: The paper presents a formal description of a subset of the Alvis language designed for the modelling and formal verification of concurrent systems. Alvis combines possibilities of a formal models verification with flexibility and simplicity of practical programming languages. Alvis provides a graphical modelling of interconnections among agents and a high level programming language used for the description of agents behaviour. Its semantic depends on the so-called system layer. The most universal system layer α 0 , described in the paper, makes Alvis similar to other formal languages like Petri nets, process algebras, time automata, etc. Content Type Journal Article Pages 161-176 DOI 10.3233/FI-2014-967 Authors Marcin Szpyrka, AGH University of Science and Technology, Department of Applied Computer Science, Al. Mickiewicza 30, 30-059 Krakow, Poland. {mszpyrka,ptm,Rafal.Mrowka,kotulski}@agh.edu.pl Piotr Matyasik, AGH University of Science and Technology, Department of Applied Computer Science, Al. Mickiewicza 30, 30-059 Krakow, Poland. {mszpyrka,ptm,Rafal.Mrowka,kotulski}@agh.edu.pl Rafał Mrówka, AGH University of Science and Technology, Department of Applied Computer Science, Al. Mickiewicza 30, 30-059 Krakow, Poland. {mszpyrka,ptm,Rafal.Mrowka,kotulski}@agh.edu.pl Leszek Kotulski, AGH University of Science and Technology, Department of Applied Computer Science, Al. Mickiewicza 30, 30-059 Krakow, Poland. {mszpyrka,ptm,Rafal.Mrowka,kotulski}@agh.edu.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 1-2 / 2014

Beschreibung: In this essay, we analyze various often semantically identified notions of separating things. In doing this, we contrast the set–theoretical approach based on the notion of an element/point with the mereological approach based on the notion of a part, hence, pointless. We address time aspect of the notion of a boundary and related notions as well as approximate notions defined in the realm of rough (approximate) mereology. Content Type Journal Article Pages 149-159 DOI 10.3233/FI-2014-966 Authors Lech Polkowski, Polish–Japanese Institute of Information Technology, Koszykowa 86, 02008 Warszawa, Poland. polkow@pjwstk.edu.pl Maria Semeniuk-Polkowska, Chair of Formal Linguistics, Warsaw University, Dobra 55, 00312 Warszawa, Poland. m.polkowska@uw.edu.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 1-2 / 2014

Beschreibung: We discuss an approach for dealing with uncertainty in complex systems. The approach is based on interactive computations over complex objects called here complex granules (c-granules, for short). Any c-granule consists of a physical part and a mental part linked in a special way. We begin from the rough set approach and next we move toward interactive computations on c-granules. From our considerations it follows that the fundamental issues of intelligent systems based on interactive computations are related to risk management in such systems. Our approach is a step toward realization of the Wisdom Technology (WisTech) program. The approach was developed over years of work on different real-life projects. Content Type Journal Article Pages 69-84 DOI 10.3233/FI-2014-961 Authors Andrzej Jankowski, Institute of Computer Science, Warsaw University of Technology, Nowowiejska 15/19, 00-665 Warsaw, Poland. a.jankowski@ii.pw.edu.pl Andrzej Skowron, Institute of Mathematics, The University of Warsaw, Banacha 2, 02-097 Warsaw, Poland. skowron@mimuw.edu.pl Roman W. Swiniarski, Department of Computer Science, San Diego State University, 5500 Campanile Drive San Diego, CA 92182, USA, and Institute of Computer Science Polish Academy of Sciences, Jana Kazimierza 5, 01-248 Warsaw, Poland. rswiniarski@mail.sdsu.edu Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 1-2 / 2014

Beschreibung: Networks of Timed Automata (NTA) and Time Petri Nets (TPNs) are well-established formalisms used to model, analyze and control industrial real-time systems. The underlying theories are usually developed in different scientific communities and both formalisms have distinct strong points: for instance, conciseness for TPNs and a more flexible notion of urgency for NTA. The objective of the paper is to introduce a new model allowing the joint use of both TPNs and NTA for the modeling of timed systems. We call it Clock Transition System (CTS). This new model incorporates the advantages of the structure of Petri nets, while introducing explicitly the concept of clocks. Transitions in the network can be guarded by an expression on the clocks and reset a subset of them as in timed automata. The urgency is introduced by a separate description of invariants. We show that CTS allow to express TPNs (even when unbounded) and NTA. For those two classical models, we identify subclasses of CTSs equivalent by isomorphism of their operational semantics and provide (syntactic) translations. The classical state-space computation developed for NTA and then adapted to TPNs can easily be defined for general CTSs. Armed with these merits, the CTS model seems a good candidate to serve as an intermediate theoretical and practical model to factor out the upcoming developments in the TPNs and the NTA scientific communities. Content Type Journal Article Pages 85-100 DOI 10.3233/FI-2014-962 Authors Claude Jard, Université de Nantes, LINA, Nantes, France. Claude.Jard@univ-nantes.fr Didier Lime, École Centrale de Nantes, IRCCyN, Nantes, France. Didier.Lime@irccyn.ec-nantes.fr Olivier H. Roux, École Centrale de Nantes, IRCCyN, Nantes, France. Olivier-H.Roux@irccyn.ec-nantes.fr Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 1-2 / 2014

Beschreibung: This paper outlines the primary steps to investigate if artificial agents can be considered as true substitutes of humans. Based on a Socially augmented microworld (SAM) human tracking behavior was analyzed using time series. SAM involves a team of navigators jointly steering a driving object along different virtual tracks containing obstacles and forks. Speed and deviances from track are logged, producing high-resolution time series of individual (training) and cooperative tracking behavior. In the current study 52 time series of individual tracking behavior on training tracks were clustered according to different similarity measures. Resulting clusters were used to predict cooperative tracking behavior in fork situations. Results showed that prediction was well for tracking behavior shown at the first and, moderately well at the third fork of the cooperative track: navigators switched from their trained to a different tracking style and then back to their trained behavior. This matches with earlier identified navigator types, which were identified on visual examination. Our findings on navigator types will serve as a basis for the development of artificial agents, which can be compared later to behavior of human navigators. Content Type Journal Article Pages 133-147 DOI 10.3233/FI-2014-965 Authors Vladimir Kurbalija, Department of Mathematics and Informatics, Faculty of Sciences, University of Novi Sad, Trg D. Obradovica 4, 21000 Novi Sad, Serbia. kurba@dmi.uns.ac.rs, mira@dmi.uns.ac.rs Mirjana Ivanović, Department of Mathematics and Informatics, Faculty of Sciences, University of Novi Sad, Trg D. Obradovica 4, 21000 Novi Sad, Serbia. kurba@dmi.uns.ac.rs, mira@dmi.uns.ac.rs Charlotte von Bernstorff, Institute of Psychology, Humboldt University Berlin, Rudower Chaussee 18, 12489 Berlin, Germany. charlotte.bernstorff@hu-berlin.de, jens.nachtwei@hu-berlin.de Jens Nachtwei, Institute of Psychology, Humboldt University Berlin, Rudower Chaussee 18, 12489 Berlin, Germany. charlotte.bernstorff@hu-berlin.de, jens.nachtwei@hu-berlin.de Hans-Dieter Burkhard, Institute of Informatics, Humboldt University Berlin, Rudower Chaussee 25, 12489 Berlin, Germany. hdb@informatik.hu-berlin.de Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 1-2 / 2014

Beschreibung: We present structural properties of languages constructed with catenation and shuffle, comprising iteration lemmata and closure properties of the language classes, as well as decidability results that follow. Content Type Journal Article Pages 117-132 DOI 10.3233/FI-2014-964 Authors Manfred Kudlek, University of Hamburg, Germany Nils Erik Flick, University of Oldenburg, Germany. flick@informatik.uni-oldenburg.de Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 1-2 / 2014

Beschreibung: Unified State Model (USM) is a single data model that allows conveying objects of major programming languages and databases. USM exploits and emphasizes common properties of their data models. USM is equipped with mappings from these data models onto it. With USM at hand, we have faced the next natural research question whether numerous query languages for the data subsumed by USM can be clearly mapped onto a common language. We have designed and proposed such a language called the Unified Query Language (UQL). UQL is intended to be a minimalistic and elegant query language that allows expressing queries of languages of data models covered by USM. In this paper we define UQL and its concise set of operators. Next we conduct a mild introduction into UQL features by showing examples of SQL and ODMG OQL queries and their mapping onto UQL. We conclude by presenting the mapping of the theoretical foundations of these two major query languages onto UQL. They are the multiset relational algebra and the object query algebra. This is an important step towards the establishment of a fully-fledged common query language for USM and its subsumed data models. Content Type Journal Article Pages 177-192 DOI 10.3233/FI-2014-968 Authors Piotr Wiśniewski, Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Poland. pikonrad@mat.umk.pl Krzysztof Stencel, Institute of Informatics, University of Warsaw, Warsaw, Poland. stencel@mimuw.edu.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 1-2 / 2014

Beschreibung: In this paper we study the complexity of HORNETS, an algebraic extension of object nets. We define a restricted class: safe, elementary HORNETS, to guarantee finite state spaces. It will turn out, that the reachability problem for this class requires exponential space, which is a major increase when compared to safe, elementary object nets, which require polynomial space. Content Type Journal Article Pages 101-115 DOI 10.3233/FI-2014-963 Authors Michael Köhler-Bußmeier, University of Hamburg, Department for Informatics, Vogt-Kölln-Straße 30, D-22527 Hamburg, Germany. koehler@informatik.uni-hamburg.de Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 1-2 / 2014

Beschreibung: Computational steering is an interactive remote control of a long running application. The user can adopt it, e.g., to adjust simulation parameters on the fly. Simulation of large-scale biochemical networks is often computationally expensive, particularly stochastic and hybrid simulation. Such extremely time-consuming computations necessitate an interactive mechanism to permit users to try different paths and ask “what-if-questions” while the simulation is in progress. Furthermore, with the progress of computational modelling and the simulation of biochemical networks, there is a need to manage multi-scale models, which may contain species or reactions at different scales. In this context, Petri nets are of special importance, since they provide an intuitive visual representation of reaction networks. In this paper, we introduce a framework and its implementation for combining Petri nets and computational steering for the representation and interactive simulation of biochemical networks. The main merits of the developed framework are: intuitive representation of biochemical networks by means of Petri nets, distributed collaborative and interactive simulation, and tight coupling of simulation and visualisation. Content Type Journal Article Pages 49-67 DOI 10.3233/FI-2014-960 Authors Mostafa Herajy, Department of Mathematics and Computer Science, Faculty of Science, Port Said University, 42521 - Port Said, Egypt. mherajy@sci.psu.edu.eg Monika Heiner, Computer Science Institute, Brandenburg University of Technology, D-03013 Cottbus, Germany. monika.heiner@informatik.tu-cottbus.de Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 1-2 / 2014

Beschreibung: In the paper, we attempt to identify the crucial determinants of innovativeness economy and the correlations between the determinants. We based our research on the Innovativeness Union Scoreboard (IUS) dataset. In order to solve the problem, we propose to use the Double Self-Organizing Feature Map (SOM) approach. In the first step, countries, described by determinants of innovativeness economy, are clustered using SOMs according to five year time series for each determinant separately. In the second step, results of the first step are clustered again using SOM to obtain the final correlation represented in the form of a minimal spanning tree. We propose some modifications of the clustering process using SOMs to improve classification results and efficiency of the learning process. Content Type Journal Article Pages 37-48 DOI 10.3233/FI-2014-959 Authors Marta Czyżewska, University of Information Technology and Management, Sucharskiego Str. 2, 35-225 Rzeszów, Poland. mczyzewska@wsiz.rzeszow.pl, jszkola@wsiz.rzeszow.pl, kpancerz@wsiz.rzeszow.pl Jarosław Szkoła, University of Information Technology and Management, Sucharskiego Str. 2, 35-225 Rzeszów, Poland. mczyzewska@wsiz.rzeszow.pl, jszkola@wsiz.rzeszow.pl, kpancerz@wsiz.rzeszow.pl Krzysztof Pancerz, University of Information Technology and Management, Sucharskiego Str. 2, 35-225 Rzeszów, Poland. mczyzewska@wsiz.rzeszow.pl, jszkola@wsiz.rzeszow.pl, kpancerz@wsiz.rzeszow.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 1-2 / 2014

Beschreibung: The paper describes a new tool for study relationships between length and coverage of exact decision rules. This tool is based on dynamic programming approach. We also present results of experiments with decision tables from UCI Machine Learning Repository. Content Type Journal Article Pages 1-13 DOI 10.3233/FI-2014-956 Authors Talha Amin, Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia. {talha.amin, igor.chikalov, mikhail.moshkov}@kaust.edu.sa; beata.zielosko@us.edu.pl Igor Chikalov, Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia. {talha.amin, igor.chikalov, mikhail.moshkov}@kaust.edu.sa; beata.zielosko@us.edu.pl Mikhail Moshkov, Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia. {talha.amin, igor.chikalov, mikhail.moshkov}@kaust.edu.sa; beata.zielosko@us.edu.pl Beata Zielosko, Computer, Electrical and Mathematical Sciences and Engineering Division, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia. {talha.amin, igor.chikalov, mikhail.moshkov}@kaust.edu.sa; beata.zielosko@us.edu.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 1-2 / 2014

Beschreibung: Petri net structures are used as communication model of network systems where message transfer channels are represented by the nets' edges, communicating agents - by nets' places and actions of communication - by nets' transitions, which here are called transmissions. The role of (structured) tokens play send/receive statements, that arrive at random, which makes the distribution of edges change dynamically. In this sense a net is self-modyfying: although the set of agents-places is fixed, the channels and communicating actions vary in the course of the net activity. Problems of deadlock and fairness is investigated. Content Type Journal Article Pages 27-36 DOI 10.3233/FI-2014-958 Authors Ludwik Czaja, University of Economics and Computer Science Vistula in Warsaw and University of Warsaw, Poland. lczaja@mimuw.edu.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 1-2 / 2014

Beschreibung: This paper presents a new tool for the study of relationships between the total path length or the average depth and the number of misclassifications for decision trees. In addition to algorithm, the paper also presents the results of experiments with datasets from UCI ML Repository [9] and datasets representing Boolean functions with 10 variables. Content Type Journal Article Pages 15-26 DOI 10.3233/FI-2014-957 Authors Igor Chikalov, Computer, Electrical and Mathematical Sciences and Engineering, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia. {igor.chikalov, shahid.hussain, mikhail.moshkov}@kaust.edu.sa Shahid Hussain, Computer, Electrical and Mathematical Sciences and Engineering, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia. {igor.chikalov, shahid.hussain, mikhail.moshkov}@kaust.edu.sa Mikhail Moshkov, Computer, Electrical and Mathematical Sciences and Engineering, King Abdullah University of Science and Technology, Thuwal 23955-6900, Saudi Arabia. {igor.chikalov, shahid.hussain, mikhail.moshkov}@kaust.edu.sa Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 1-2 / 2014

Beschreibung: We derive quantitative results regarding sets of n-bit strings that have different dependency or independency properties. Let C(x) be the Kolmogorov complexity of the string x. A string y has α dependency with a string x if C(y) − C(y | x) ≥ α. A set of strings {x 1 , . . . , x t } is pairwise α-independent if for all i ≠ j, C(x i ) − C(x i | x j ) 〈 α. A tuple of strings (x 1 , . . . , x t ) is mutually α-independent if C(x π(1) . . . x π(t) ) 〉 C(x 1 )+. . .+C(x t ) − α, for every permutation π of [t]. We show that: • For every n-bit string x with complexity C(x) ≥ α + 7 log n, the set of n-bit strings that have α dependency with x has size at least (1/poly(n))2 n−α . In case α is computable from n and C(x) ≥ α + 12 log n, the size of the same set is at least (1/C)2 n−α − poly(n)2 α , for some positive constant C. • There exists a set of n-bit strings A of size poly(n)2 α such that any n-bit string has α-dependency with some string in A. • If the set of n-bit strings {x 1 , . . . , x t } is pairwise α-independent, then t ≤ poly(n)2 α . This bound is tight within a poly(n) factor, because, for every n, there exists a set of n-bit strings {x 1 , . . . , x t } that is pairwise α-dependent with t = (1/poly(n)) · 2 α (for all α ≥ 5 log n). • If the tuple of n-bit strings (x 1 , . . . , x t ) is mutually α-independent, then t ≤ poly(n)2 α (for all α ≥ 7 log n + 6). Content Type Journal Article Pages 485-497 DOI 10.3233/FI-2014-1027 Authors Marius Zimand, Department of Computer and Information Sciences, Towson University, Baltimore, MD, USA. mzimand@towson.edu Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 3-4 / 2014

Beschreibung: We introduce and briefly investigate P systems with controlled computations. First, P systems with label restricted transitions are considered (in each step, all rules used have either the same label, or, possibly, the empty label, λ), then P systems with the computations controlled by languages (as in context-free controlled grammars). The relationships between the families of sets of numbers computed by the various classes of controlled P systems are investigated, also comparing them with length sets of languages in Chomsky and Lindenmayer hierarchies (characterizations of the length sets of ET0L and of recursively enumerable languages are obtained in this framework). A series of open problems and research topics are formulated. Content Type Journal Article Pages 451-464 DOI 10.3233/FI-2014-1025 Authors Kamala Krithivasan, Department of Computer Science and Engineering, Indian Institute of Technology, Madras, Chennai-36, India. kamala@iitm.ac.in Gheorghe Păun, Institute of Mathematics of the Romanian Academy, PO Box 1-764, 014700 Bucureşti, Romania. gpaun@us.es, ghpaun@gmail.com Ajeesh Ramanujan, Department of Computer Science and Engineering, Indian Institute of Technology, Madras, Chennai-36, India. ajeeshramanujan@gmail.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 3-4 / 2014

Beschreibung: This note describes our experiments aiming to empirically test the ability of machine learning models to act as decision oracles for NP problems. Focusing on satisfiability testing problems, we have generated random 3-SAT instances and found out that the correct branch prediction accuracy reached levels in excess of 99%. The branching in a simple backtracking-based SAT solver has been reduced in more than 90% of the tested cases, and the average number of branching steps has reduced to between 1/5 and 1/3 of the one without the machine learning model. The percentage of SAT instances where the machine learned heuristic-enhanced algorithm solved SAT in a single pass reached levels of 80-90%, depending on the set of features used. Content Type Journal Article Pages 441-450 DOI 10.3233/FI-2014-1024 Authors Cristian Grozea, Fraunhofer FOKUS, Kaiserin Augusta Allee 31, 10589 Berlin, Germany. cristian.grozea@fokus.fraunhofer.de Marius Popescu, University of Bucharest, Academiei 14, Bucharest, Romania. popescunmarius@gmail.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 3-4 / 2014

Beschreibung: We propose a novel approach to justify and guide regularisation of an ill-posed one-dimensional global optimisation with multiple solutions using a massively parallel (P system) model of the solution space. Classical optimisation assumes a well-posed problem with a stable unique solution. Most of important practical problems are ill posed due to an unstable or non-unique global optimum and are regularised to get a unique best-suited solution. Whilst regularisation theory exists largely for unstable unique solutions, its recommendations are often routinely applied to inverse optical problems with essentially non-unique solutions, e.g. computer stereo vision or image segmentation, typically formulated in terms of global energy minimisation. In these cases the recommended regularisation becomes purely heuristic and does not guarantee a unique solution. As a result, classical optimisation algorithms: dynamic programming (DP) and belief propagation (BP) – meet with difficulties. Our recent concurrent propagation (CP), leaning upon the P systems paradigm, extends DP and BP to always detect whether the problem is ill posed or not and store in the ill-posed case an entire space of solutions that yield the same global optimum. This suggests a radically new path to proper regularisation: select the best-suited unique solution by exploring statistical and structural features of this space. We propose a P systems based implementation of CP and set out as a case study an application of CP to the image matching problem in stereo vision. Content Type Journal Article Pages 465-483 DOI 10.3233/FI-2014-1026 Authors Radu Nicolescu, Department of Computer Science, The University of Auckland, Auckland, New Zealand. r.nicolescu@auckland.ac.nz Georgy Gimel’farb, Department of Computer Science, The University of Auckland, Auckland, New Zealand. r.nicolescu@auckland.ac.nz John Morris, Department of Computer Science, The University of Auckland, Auckland, New Zealand. r.nicolescu@auckland.ac.nz Patrice Delmas, Department of Computer Science, The University of Auckland, Auckland, New Zealand. r.nicolescu@auckland.ac.nz Rui Gong, Department of Computer Science, The University of Auckland, Auckland, New Zealand. r.nicolescu@auckland.ac.nz Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 3-4 / 2014

Beschreibung: The Halpern–Shoham logic is a modal logic of time intervals. Some effort has been put in last ten years to classify fragments of this beautiful logic with respect to decidability of its satisfiability problem. We complete this classification by showing — what we believe is quite an unexpected result—that the logic of subintervals, the fragment of the Halpern–Shoham logic where only the operator “during”, or D, is allowed, is undecidable over discrete structures. This is surprising as this, apparently very simple, logic is decidable over dense orders and its reflexive variant is known to be decidable over discrete structures. Our result subsumes a lot of previous undecidability results of fragments that include D. Content Type Journal Article Pages 217-240 DOI 10.3233/FI-2014-1011 Authors Jerzy Marcinkowski, Institute of Computer Science, University Of Wrocław, Poland. jma@cs.uni.wroc.pl;jmi@cs.uni.wroc.pl Jakub Michaliszyn, Institute of Computer Science, University Of Wrocław, Poland. jma@cs.uni.wroc.pl;jmi@cs.uni.wroc.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 2 / 2014

Beschreibung: The theory of rough sets provides a widely used modern tool, and in particular, rough sets induced by quasiorders are in the focus of the current interest, because they are strongly interrelated with the applications of preference relations and intuitionistic logic. In this paper, a structural characterisation of rough sets induced by quasiorders is given. These rough sets form Nelson algebras defined on algebraic lattices. We prove that any Nelson algebra can be represented as a subalgebra of an algebra defined on rough sets induced by a suitable quasiorder. We also show that Monteiro spaces, rough sets induced by quasiorders and Nelson algebras defined on T 0 -spaces that are Alexandrov topologies can be considered as equivalent structures, because they determine each other up to isomorphism. Content Type Journal Article Pages 205-215 DOI 10.3233/FI-2014-1010 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 131 Journal Issue Volume 131, Number 2 / 2014

Beschreibung: A widely used class of approximate pattern matching algorithms work in two stages, the first being a filtering stage that uses spaced seeds to quickly discards regions where a match is not likely to occur. The design of effective spaced seeds is known to be a hard problem. In this setting, we propose a family of lossless spaced seeds for matching with up to two errors based on mathematical objects known as perfect rulers. We analyze these seeds with respect to the tradeoff they offer between seed weight and the minimum length of the pattern to be matched. We identify a specific property of rulers, namely their skewness, which is closely related to the minimum pattern length of the derived seeds. In this context, we study in depth the specific case of Wichmann rulers and investigate the generalization of our approach to the larger class of unrestricted rulers. Although our analysis is mainly of theoretical interest, we show that for pattern lengths of practical relevance our seeds have a larger weight, hence a better filtration efficiency, than the ones known in the literature. Content Type Journal Article Pages 187-203 DOI 10.3233/FI-2014-1009 Authors Lavinia Egidi, DiSIT, Computer Science Institute, Università del Piemonte Orientale, Italy. lavinia.egidi@unipmn.it; giovanni.manzini@unipmn.it Giovanni Manzini, DiSIT, Computer Science Institute, Università del Piemonte Orientale, Italy. lavinia.egidi@unipmn.it; giovanni.manzini@unipmn.it Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 2 / 2014

Beschreibung: Powerful algebraic techniques have been developed for classical sequential computation. Many of them are based on regular expressions and the associated regular algebra. For parallel and interactive computation, extensions to handle 2-dimensional patterns are often required. Finite interactive systems, a 2-dimensional version of finite automata, may be used to recognize 2-dimensional languages. In this paper we present a blueprint for getting a formal representation of parallel, interactive programs and of their semantics. It is based on a recently introduced approach for getting regular expressions for 2-dimensional patterns, particularly using words of arbitrary shapes and powerful control mechanisms on composition. We extend the previously defined class of expressions n2RE with new control features, progressively increasing the expressive power of the formalism up to a level where a procedure for generating the words accepted by finite interactive systems may be obtained. Targeted applications come from the area of modelling, specification, analysis and verification of structured interactive programs via the associated scenario semantics. Content Type Journal Article Pages 313-336 DOI 10.3233/FI-2014-1017 Authors Iulia Teodora Banu-Demergian, Department of Computer Science, University of Bucharest, Romania. th_iulia84@yahoo.com; gheorghe.stefanescu@fmi.unibuc.ro Gheorghe Stefanescu, Department of Computer Science, University of Bucharest, Romania. th_iulia84@yahoo.com; gheorghe.stefanescu@fmi.unibuc.ro Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 3-4 / 2014

Beschreibung: We introduce a stochastic extension of CCS endowed with structural operational semantics expressed in terms of measure theory. The set of processes is organised as a measurable space by the sigma-algebra generated by structural congruence. The structural operational semantics associates to each process a set of measures over the space of processes. The measures encode the rates of the transitions from a process (state of a system) to a measurable set of processes. We prove that the stochastic bisimilarity is a congruence, which extends the structural congruence. In addition to an elegant operational semantics, our calculus provides a canonic way to define metrics on processes that measure how similar two processes are in terms of behaviour. Content Type Journal Article Pages 351-371 DOI 10.3233/FI-2014-1019 Authors Luca Cardelli, Microsoft Research Cambridge, UK. luca@microsoft.com Radu Mardare, Dept. of Computer Science, Aalborg University, Denmark. mardare@cs.aau.dk Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 3-4 / 2014

Beschreibung: We extend the study of networks of evolutionary processors accepting words to a similar model, processing rectangular pictures. To this aim, we introduce accepting networks of evolutionary picture processors and investigate their computational power. We show that these networks can accept the complement of any local picture language as well as picture languages that are not recognizable. Some open problems regarding decidability issues and closure properties are finally discussed. Content Type Journal Article Pages 337-349 DOI 10.3233/FI-2014-1018 Authors Paolo Bottoni, Department of Computer Science, “Sapienza”, University of Rome, Via Salaria 113, 00198 Rome, Italy. bottoni@di.uniroma1.it; Anna Labella, Department of Computer Science, “Sapienza”, University of Rome, Via Salaria 113, 00198 Rome, Italy. labella@di.uniroma1.it Victor Mitrana, Department of Computer Science, University of Bucharest, Str. Academiei nr. 14, 010014, Bucharest, Romania. mitrana@fmi.unibuc.ro Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 3-4 / 2014

Beschreibung: We study, on the basis of a simple neural–network like system that we call a spatial network, how several properties of two evolvable systems: a nervous system and computer software, could influence on the evolvability of a genetic algorithm. The following properties are modelled: hierarchical modularity, mirroring, extensive variability and quantitative genetic traits. By mirroring we understand mimicking of the structure of processed data by the structure of the processing algorithm. We estimate the evolvability of several examples of the presented networks, which perform simple image processing tasks, like stereo–to–depth. The evaluation is done by studying the size of these networks' genotype. Content Type Journal Article Pages 253-278 DOI 10.3233/FI-2014-1013 Authors Artur Rataj, Institute of Theoretical and Applied Computer Science, Bałtycka 5, Gliwice, Poland. arataj@iitis.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 2 / 2014

Beschreibung: Rough inclusion functions are mappings considered in rough set theory with which one can measure the degree of inclusion of a set (information granule) in a set (information granule) in line with rough mereology. On the other hand, similarity indices are mappings used in cluster analysis with which one can compare clusterings, and clustering methods with respect to similarity. In this article we show that a large number of similarity indices, known from the literature, can be generated by three simple rough inclusion functions, the standard rough inclusion function included. Content Type Journal Article Pages 149-163 DOI 10.3233/FI-2014-1068 Authors Anna Gomolińska, Institute of Informatics, Białystok University, Sosnowa 64, 15-887 Białystok, Poland. anna.gom@math.uwb.edu.pl Marcin Wolski, Department of Logic and Methodology of Science, Maria Curie-Skłodowska University, pl. Maria Curie-Skłodowska 4, 20-031 Lublin, Poland. marcin.wolski@umcs.lublin.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: The intention of this paper is to introduce a timed extension of transition systems with independence, and to study its categorical interrelations with other time-sensitive models. In particular, we show the existence of a chain of coreflections leading from a category of the model of timed transition systems with independence to a category of a specially defined model of marked Scott domains. As an intermediate semantics we use a timed extension of occurrence transition systems with independence, able to properly capture causality and independence relations which arise in the presence of time delays. Content Type Journal Article Pages 133-147 DOI 10.3233/FI-2014-1067 Authors Roman Dubtsov, A.P. Ershov Institute of Informatics Systems, SB RAS, 6, Acad. Lavrentiev avenue, 630090, Novosibirsk, Russia Elena Oshevskaya, Sobolev Institute of Mathematics, SB RAS, 4, Acad. Koptyug avenue, 630090, Novosibirsk, Russia Irina Virbitskaite, A.P. Ershov Institute of Informatics Systems, SB RAS, 6, Acad. Lavrentiev avenue, 630090, Novosibirsk, Russia. virb@iis.nsk.su Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: A network system is given as a set of Petri net-like structures called agents. Each agent has a singled out place interpreted as a communication port with ingoing edges labelled with send(p 1 , ..., p n ) and receive(q 1 , ..., q m ) commands, where p i , q j are names of ports of its interlocutors. Every such edge exits a transition emiting a request for send or receive message. A transmission channel between the agent and its intelocutors is established when its port holds a send or receive command, while ports of its interlocutors hold respective (matching) communication commands. This gives rise to communication between the agent and its interlocutors, after which the channel is disrupted: hence floating channels. Some behavioural properties of such network system are examined, their decision complexity, deadlock and fairness in their number. Content Type Journal Article Pages 123-132 DOI 10.3233/FI-2014-1066 Authors Ludwik Czaja, Academy of Finance and Business Vistula, Warsaw and Institute of Informatics, The University of Warsaw, Poland lczaja@mimuw.edu.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: We investigate the relation between Combinatory Logic and Wang Tiles with the aim of studying Combinators as a programming language for Self-Assembly and DNA computing. We introduce a subset of Combinatory Logic, SKI # , which is Turing Complete, includes simply Typed Combinatory Logic and contains only combinators whose computations require finitely many different redexes. Then, we define a language of Tiles, SKI-Tile, for the representation and the computation of the terms of SKI # in Self-Assembly. Moreover, we introduce a program development methodology that given any computable function, expressed in SKI # , provides a finite set of Tiles that self-assemble to return the computations of the function applications. Finally, the methodology is applied to the derivation of a SKI-Tile program that self-assemble to compute the factorial function. Content Type Journal Article Pages 105-121 DOI 10.3233/FI-2014-1065 Authors Marco Bellia, Dipartimento di Informatica, Università di Pisa, Italy. {bellia,occhiuto}@di.unipi.it M. Eugenia Occhiuto, Dipartimento di Informatica, Università di Pisa, Italy. {bellia,occhiuto}@di.unipi.it Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: We show how to synthesise parameter values under which a given property, expressed in a certain extension of CTL, called RTCTL P , holds in a parametric timed Kripke structure. We prove the decidability of parameter synthesis for RTCTL P by showing how to restrict the infinite space of parameter valuations to its finite subset and employ a brute-force algorithm. The brute-force approach soon becomes intractable, therefore we propose a symbolic algorithm for RTCTL P parameter synthesis. Similarly to the fixed-point symbolic model checking approach, we introduce special operators which stabilise on the solution. The process of stabilisation is essentially a translation from the RTCTL P parameter synthesis problem to a discrete optimization task. We show that the proposed method is sound and complete and provide some complexity results. We argue that this approach leads to new opportunities in model checking, including the use of integer programming and related tools. Content Type Journal Article Pages 211-226 DOI 10.3233/FI-2014-1072 Authors Michał Knapik, Institute of Computer Science, PAS, Warsaw, Poland. mknapik@ipipan.waw.pl; penczek@ipipan.waw.pl Wojciech Penczek, Institute of Computer Science, PAS, Warsaw, Poland. mknapik@ipipan.waw.pl; penczek@ipipan.waw.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: Process mining is a relatively new field of computer science which deals with process discovery and analysis based on event logs. In this work we consider the problem of discovering workflow nets with cancellation regions from event logs. Cancellations occur in the majority of real-life event logs. In spite of huge amount of process mining techniques little has been done on cancellation regions discovery. We show that the state-based region algorithm gives labeled Petri nets with overcomplicated control flow structure for logs with cancellations. We propose a novel method to discover cancellation regions from the transition systems built on event logs and show the way to construct equivalent workflow net with reset arcs to simplify the control flow structure. Content Type Journal Article Pages 197-209 DOI 10.3233/FI-2014-1071 Authors Anna A. Kalenkova, National Research University Higher School of Economics (HSE), Moscow, 101000, Russia. {akalenkova,ilomazova}@hse.ru Irina A. Lomazova, National Research University Higher School of Economics (HSE), Moscow, 101000, Russia. {akalenkova,ilomazova}@hse.ru Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: In this paper we investigate Timed Petri nets (TPN) with fixed, possibly zero, durations and maximal step semantics. We define a new state representation where a state is a pair of a marking for the places and a marking for the transitions (a matrix of clocks). For this representation of states we provide an algebraic state equation. Such a state equation lets us prove a sufficient condition for the non-reachability of a state in a TPN. This application of the state equation is subsequently illustrated by an example. Content Type Journal Article Pages 305-322 DOI 10.3233/FI-2014-1078 Authors Matthias Werner, Fakultät für Informatik, Technische Universität Chemnitz, Germany. matthias.werner@informatik.tu-chemnitz.de Louchka Popova-Zeugmann, Institut für Informatik, Humboldt-Universität zu Berlin, Germany. popova@informatik.hu-berlin.de Mario Haustein, Fakultät für Informatik, Technische Universität Chemnitz, Germany. mario.haustein@hrz.tu-chemnitz.de E. Pelz, LACL, UPEC, France. pelz@u-pec.fr Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: Parsing Expression Grammar (PEG) encodes a recursive-descent parser with limited backtracking. The parser has many useful properties. Converting PEG to an executable parser is a rather straightforward task. Unfortunately, PEG is not well understood as a language definition tool. It is thus of a practical interest to construct PEGs for languages specified in some familiar way, such as Backus-Naur Form (BNF). The problem was attacked by Medeiros in an elegant way by noticing that both PEG and BNF can be formally defined in a very similar way. Some of his results were extended in a previous paper by this author. We continue here with further extensions. Content Type Journal Article Pages 257-270 DOI 10.3233/FI-2014-1075 Authors Roman R. Redziejowski, Giraf's Research, roman.redz@swipnet.se Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: Our research is focused on creation of a new object-oriented programming language for Physarum polycephalum computing. Physarum polycephalum is a one-cell organism that can be used for developing a biological architecture of different abstract devices, among others, the digital ones. In the paper, we use an abstract graphical language in the form of Petri nets to describe the Physarum polycephalum behavior. Petri nets are a good formalism to assist designers and support hardware design tools, especially in developing concurrent systems. At the beginning stage considered in this paper, we show how to build Petri net models, and next implement them as Physarum polycephalum machines, of basic logic gates AND, OR, NOT, and simple combinational circuits on the example of the 1-to-2 demultiplexer. Content Type Journal Article Pages 271-285 DOI 10.3233/FI-2014-1076 Authors Andrew Schumann, Institute of Biomedical Informatics, University of Information Technology and Management, Sucharskiego Str. 2, 35-225 Rzeszów, Poland. aschumann@wsiz.rzeszow.pl; kpancerz@wsiz.rzeszow.pl Krzysztof Pancerz, Institute of Biomedical Informatics, University of Information Technology and Management, Sucharskiego Str. 2, 35-225 Rzeszów, Poland. aschumann@wsiz.rzeszow.pl; kpancerz@wsiz.rzeszow.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: Concept learning in description logics (DLs) is similar to binary classification in traditional machine learning. The difference is that in DLs objects are described not only by attributes but also by binary relationships between objects. In this paper, we develop the first bisimulation-based method of concept learning in DLs for the following setting: given a knowledge base KB in a DL, a set of objects standing for positive examples and a set of objects standing for negative examples, learn a concept C in that DL such that the positive examples are instances of C w.r.t. KB, while the negative examples are not instances of C w.r.t. KB. We also prove soundness of our method and investigate its C-learnability. Content Type Journal Article Pages 287-303 DOI 10.3233/FI-2014-1077 Authors Thanh-Luong Tran, Faculty of Information Technology, College of Sciences, Hue University, 77 Nguyen Hue, Hue city, Vietnam Quang-Thuy Ha, Faculty of Information Technology, VNU University of Engineering and Technology, 144 Xuan Thuy, Hanoi, Vietnam Thi-Lan-Giao Hoang, Faculty of Information Technology, College of Sciences, Hue University, 77 Nguyen Hue, Hue city, Vietnam Linh Anh Nguyen, Institute of Informatics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland Hung Son Nguyen, Institute of Mathematics, University of Warsaw, Banacha 2, 02-097 Warsaw, Poland. son@mimuw.edu.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: Opacity testing is formalized and studied. We specify opacity testers as well as tested systems by (timed) process algebras. We model various testers according to how sophisticated observations of tested system they can make and which kind of conclusions they can obtain. We use this technique to define several realistic security properties. The properties are studied and compared with other security concepts. Content Type Journal Article Pages 165-179 DOI 10.3233/FI-2014-1069 Authors Damas P. Gruska, Institute of Informatics, Comenius University, Mlynska dolina, 842 48 Bratislava, Slovakia. gruska@fmph.uniba.sk Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: The notion of a boundary belongs in the canon of the most important notions of mereotopology, the topological theory induced by mereological structures; the importance of this notion rests not only in its applications to practical spatial reasoning, e.g., in geographical information systems, where it is usually couched under the term of a contour and applied in systems related to economy, welfare, climate, wildlife etc., but also in its impact on reasoning schemes elaborated for reasoning about spatial objects, represented as regions, about spatial locutions etc. The difficulty with this notion lies primarily in the fact that boundaries are things not belonging in mereological universa of things of which they are boundaries. Various authors, from philosophers through mathematicians to logicians and computer scientists proposed schemes for defining and treating boundaries. We propose two approaches to boundaries; the first aims at defining boundaries as things possibly in the universe in question, i.e., composed of existing things, whereas the second defines them as things in a meta–space built over the mereological universe in question, i.e., we assume a priori that boundaries are in a sense ‘things at infinity’, in an agreement with the topological nature of boundaries. Of the two equivalent topological definitions of a boundary, the first, global, defining the boundary as the difference between the closure and the interior of the set, and the second, local, defining it as the set of boundary points whose all neighborhoods transect the set, the first calls for the first type of the boundary and the second is best fitted for the meta–boundary. In the text that follows, we discuss mereology and rough mereology notions (sects. 2, 3), the topological approach to the notion of a boundary and the model ROM with which we illustrate our discussion (sect. 4), the mereology approach (sect. 5), and the approach based on rough mereology and granular computing in the framework of rough mereology (sect. 6). Content Type Journal Article Pages 241-255 DOI 10.3233/FI-2014-1074 Authors Lech Polkowski, Polish-Japanese Institute of Information Technology, Koszykowa str. 86, 02-008 Warszawa, Poland. polkow@pjwstk.edu.pl Maria Semeniuk–Polkowska, Chair of Formal Linguistics, University of Warsaw, Dobra str. 55, 00-312 Warszawa, Poland. m.polkowska@uw.edu.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: Artificial Neural Networks are of much interest for many practical reasons. As of today, they are widely implemented. Of many possible ANNs, the most widely used one is the back-propagation model with direct connection. In this model the input layer is fed with input data and each subsequent layers are fed with the output of preceding layer. This model can be extended by feeding the input data to each layer. This article argues that this new model, named Cross Forward Connection, is optimal than the widely used Direct Connection. Content Type Journal Article Pages 227-240 DOI 10.3233/FI-2014-1073 Authors Stanisław Płaczek, Vistula University, Warsaw, Poland. stanislaw.placzek@wp.pl, bijaya.adhikari1991@gmail.com Bijaya Adhikari, Vistula University, Warsaw, Poland. stanislaw.placzek@wp.pl, bijaya.adhikari1991@gmail.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: Information granules (infogranules, for short) are widely discussed in the literature. In particular, let us mention here the rough granular computing approach based on the rough set approach and its combination with other approaches to soft computing. However, the issues related to interactions of infogranules with the physical world and to perception of interactions in the physical world by infogranules are not well elaborated yet. On the other hand the understanding of interactions is the critical issue of complex systems. We propose to model complex systems by interactive computational systems (ICS) created by societies of agents. Computations in ICS are based on complex granules (c-granules, for short). In the paper we concentrate on some basic issues related to interactive computations based on c-granules performed by agents in the physical world. Content Type Journal Article Pages 181-196 DOI 10.3233/FI-2014-1070 Authors Andrzej Jankowski, Institute of Computer Science, Warsaw University of Technology, Nowowiejska 15/19, 00-665 Warsaw, Poland. a.jankowski@ii.pw.edu.pl Andrzej Skowron, Institute of Mathematics, The University of Warsaw, Banacha 2, 02-097 Warsaw, Poland. skowron@mimuw.edu.pl Roman W. Swiniarski, Department of Computer Science, San Diego State University, 5500 Campanile Drive San Diego, CA 92182, USA. rswiniarski@mail.sdsu.edu Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 2-3 / 2014

Beschreibung: In this paper, a generalized multi-sawtooth map based image encryption scheme with an efficient permutation-diffusion mechanism is proposed. In the permutation process, a generalized multi-sawtooth map is utilized to generate one chaotic orbit used to get one index order sequence for the permutation of image pixel positions, while in the diffusion process, two generalized multi-sawtooth maps are employed to yield two pseudo-random grey value sequences for a two-way diffusion of pixel grey values. The yielded grey value sequences are not only sensitive to the control parameters and initial conditions of the considered chaotic maps, but also strongly depend on the plain-image processed, therefore the proposed scheme can effectively resist statistical attack, differential attack, known-plaintext as well as chosen-plaintext attack. Experimental results show that the new image encryption scheme has satisfactory security thanks to its large key space and robust permutation-diffusion mechanism, which makes it a potential candidate for designing image encryption schemes. Content Type Journal Article Pages 87-104 DOI 10.3233/FI-2014-1063 Authors Ruisong Ye, Department of Mathematics, Shantou University, Shantou, Guangdong, 515063, P. R. China. rsye@stu.edu.cn Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 1 / 2014

Beschreibung: This study examines the notion of inconsistency in pairwise comparisons for providing an axiomatization for it. It also proposes two inconsistency indicators for pairwise comparisons. The primary motivation for the inconsistency reduction is expressed by a computer industry concept “garbage in, garbage out”. The quality of the output depends on the quality of the input. Content Type Journal Article Pages 485-500 DOI 10.3233/FI-2014-1055 Authors Waldemar W. Koczkodaj, Computer Science, Laurentian University, Sudbury, Ontario P3E 2C6, Canada. wkoczkodaj@cs.laurentian.ca Ryszard Szwarc, Institute of Mathematics, University of Wroclaw, Wroclaw, Poland. szwarc2@gmail.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 4 / 2014

Beschreibung: In this article we propose a general framework incorporating semantic indexing and search of texts within scientific document repositories. In our approach, a semantic interpreter, which can be seen as a tool for automatic tagging of textual data, is interactively updated based on feedback from the users, in order to improve quality of the tags that it produces. In our experiments, we index our document corpus using the Explicit Semantic Analysis (ESA) method. In this algorithm, an external knowledge base is used to measure relatedness between words and concepts, and those assessments are utilized to assign meaningful concepts to given texts. In the paper, we explain how the weights expressing relations between particular words and concepts can be improved by interaction with users or by employment of expert knowledge. We also present some results of experiments on a document corpus acquired from the PubMed Central repository to show feasibility of our approach. Content Type Journal Article Pages 423-438 DOI 10.3233/FI-2014-1052 Authors Wojciech Świeboda, Faculty of Mathematics, Informatics and Mechanics, The University of Warsaw, Banacha 2, 02-097, Warsaw Poland Adam Krasuski, Chair of Computer Science, The Main School of Fire Service, Słowackiego 52/54, 01-629 Warsaw Poland Hung Son Nguyen, Faculty of Mathematics, Informatics and Mechanics, The University of Warsaw, Banacha 2, 02-097, Warsaw Poland. son@mimuw.edu.pl Andrzej Janusz, Faculty of Mathematics, Informatics and Mechanics, The University of Warsaw, Banacha 2, 02-097, Warsaw Poland. A.Janusz@mimuw.edu.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 3 / 2014

Beschreibung: How to evaluate features and select nodes is one of the key issues in constructing decision trees. In this work fuzzy rough set theory is employed to design an index for evaluating the quality of fuzzy features or numerical attributes. A fuzzy rough decision tree algorithm, which can be used to address classification problems described with symbolic, real-valued or fuzzy features, is developed. As node selection, split generation and stopping criterion are three main factors in constructing a decision tree, we design different techniques to determine splits with different kinds of features. The proposed algorithm can directly generate a classification tree without discretization or fuzzification of continuous attributes. Some numerical experiments are conducted and the comparative results show that the proposed algorithm is effective compared with some popular algorithms. Content Type Journal Article Pages 381-399 DOI 10.3233/FI-2014-1050 Authors Shuang An, School of Computer Science and Technology, Tianjin University, Tianjin 300072, P.R. China. huqinghua@tju.edu.cn Hong Shi, School of Computer Science and Technology, Tianjin University, Tianjin 300072, P.R. China. huqinghua@tju.edu.cn Qinghua Hu, School of Computer Science and Technology, Tianjin University, Tianjin 300072, P.R. China. huqinghua@tju.edu.cn Jianwu Dang, School of Computer Science and Technology, Tianjin University, Tianjin 300072, P.R. China. huqinghua@tju.edu.cn Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 3 / 2014

Beschreibung: Eilenberg and al. introduced and studied in the late sixties the family of n-ary relations over the free monoid recognized by finite n-tape automata where the where the n reading heads tapes move simultaneously from left to right. We call these relations synchronous. In the eighties Angluin and Hoover and then Läuchli and Savioz introduced a proper subfamily which the first authors called regular prefix. Our main result shows that given a synchronous relation it is decidable whether or not it is regular prefix. Incidentally we also show that the family of regular prefix relations is uniformizable in the sense that all such relations contain a partial function with the same domain whose graph is a regular prefix relation. Content Type Journal Article Pages 439-459 DOI 10.3233/FI-2014-1053 Authors Christian Choffrut, L.I.A.F.A., Université Paris 7, France. christian.choffrut@sfr.fr Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 4 / 2014

Beschreibung: This paper investigates the numerical solution of uncertain fractional order diffusion equation subject to various external forces. Homotopy Perturbation Method (HPM) is used for the analysis. Uncertainties present in the system are modelled through triangular convex normalised fuzzy sets. A new computational technique has been proposed based on double parametric form of fuzzy numbers to handle the fuzzy fractional diffusion equation. Using the single parametric form of fuzzy numbers, the original fuzzy fractional diffusion equation is converted first to an interval fuzzy fractional differential equation. Next this equation is transformed to crisp form by applying double parametric form of fuzzy numbers. Finally the same is solved by HPM symbolically to obtain the uncertain bounds of the solution. Obtained results are depicted in term of plots. Results obtained by the proposed method are compared with existing results in special cases. Content Type Journal Article Pages 19-34 DOI 10.3233/FI-2014-1060 Authors Smita Tapaswini, Department of Mathematics, National Institute of Technology Rourkela, Odisha - 769 008, India. smitatapaswini@gmail.com; sne_chak@yahoo.com S. Chakraverty, Department of Mathematics, National Institute of Technology Rourkela, Odisha - 769 008, India. smitatapaswini@gmail.com; sne_chak@yahoo.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 1 / 2014

Beschreibung: The classical rough set theory is based on the conventional indiscernibility relation. It is not very good for analyzing incomplete information. Some successful extended rough set models based on different non-equivalence relations have been proposed. The valued tolerance relation is such an extended model of classical rough set theory. However, the general calculation method of tolerance degree needs to know the prior probability distribution of an information system in advance, and it is also difficult to select a suitable threshold. In this paper, a data-driven valued tolerance relation (DVT) is proposed to solve this problem based on the idea of data-driven data mining. The new calculation method of tolerance degree and the auto-selection method of threshold do not require any prior domain knowledge except the data set. Some properties about the DVT are analyzed. Experiment results show that the DVT can get better and more stable classification results than other extended models of the classical rough set theory. Content Type Journal Article Pages 349-363 DOI 10.3233/FI-2014-1048 Authors Guoyin Wang, Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing, P.R. China. wanggy@ieee.org Lihe Guan, Department of Mathematics, Chongqing Jiaotong University, Chongqing, P.R. China. guanlihe@cqjtu.edu.cn Weizhi Wu, School of Mathematics, Physics and Information Science, Zhejiang Ocean University, Zhoushan, Zhejiang, P.R. China. wuwz@zjou.edu.cn Feng Hu, Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing, P.R. China. hufeng@cqupt.edu.cn Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 3 / 2014

Beschreibung: This paper presents a method to capture the computational intensity and computing resource requirements of data analysis in intelligent transportation systems (ITS). These requirements can be transformed into a generic methodological framework for Cyber-ITS, mainly consisting of region-based ITS data divisions and tasks scheduling for processing, to support the efficient use of cyber-infrastructure (CI). To characterize the computational intensity of a particular ITS data analysis, the computational transformation is performed by data-centric and operation-centric transformation functions. The application of this framework is illustrated by two ITS data analysis cases: multi-sensor data fusion for traffic state estimation by integrating rough set theory with Dempster-Shafer (D-S) evidence theory, and geospatial computation on Global Positioning System (GPS) data for advertising value evaluation. To make the design of generic parallel computing solutions feasible for ITS data analysis in these cases, an approach is developed to decouple the region-based division from specific high performance computer (HPC) architecture and implement a prototype of the methodological framework. Experimental results show that the prototype implementation of the framework can be applied to divide the ITS data analysis into a load-balanced set of computing tasks, therefore facilitating the parallelized data fusion and geospatial computation to achieve remarkable speedup in computation time and throughput, without loss in accuracy. Content Type Journal Article Pages 35-53 DOI 10.3233/FI-2014-1061 Authors Yingjie Xia, Hangzhou Institute of Service Engineering, Hangzhou Normal University, Hangzhou, China. xiayingjie@zju.edu.cn Ting Zhang, Hangzhou Institute of Service Engineering, Hangzhou Normal University, Hangzhou, China. xiayingjie@zju.edu.cn Shengbao Wang, Hangzhou Institute of Service Engineering, Hangzhou Normal University, Hangzhou, China. xiayingjie@zju.edu.cn Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 1 / 2014

Beschreibung: Fuzzy Logic a la Pavelka has been reintroduced here in terms of consequence relation instead of consequence operator. Metalogical notions like, consistency and inconsistency are proposed as graded notions. The relationship between consequence relation and inconsistency, both fuzzy here, is studied. Another metalogical notion viz., equivalence of two sets of formulae that originates from Tarski is defined and investigated in this context when the premise is a fuzzy set. Content Type Journal Article Pages 1-18 DOI 10.3233/FI-2014-1059 Authors Soma Dutta, The Institute of Mathematical Sciences, Chennai, India. somadutta9@gmail.com Mihir Kr. Chakraborty, School of Cognitive Science, Jadavpur University, Centre for Soft Computing and Research, Indian Statistical Institute, Kolkata, India. mihirc4@gmail.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 1 / 2014

Beschreibung: In this paper we attempt to measure the accuracy of approximations of regular languages by languages in +−varieties (as defined by Eilenberg). These approximations are upper approximations in the sense of Pawlak’s rough set theory with respect to congruences belonging to the variety of congruences corresponding to the given +−variety. In our approach, the accuracy of an approximation is measured by the relative density of the object language in the approximation language and the asymptotic behavior of this quotient. In particular, we apply our measures of accuracy to k-definite, reverse k-definite, i, j-definite and k-testable approximations. Content Type Journal Article Pages 533-545 DOI 10.3233/FI-2014-1058 Authors Gabriela Martín Torres, Research Group on Mathematical Linguistics, Rovira i Virgili University, Spain. drapurke@yahoo.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 4 / 2014

Beschreibung: The representation and processing of uncertainty information is one of the key basic issues of the intelligent information processing in the face of growing vast information, especially in the era of network. There have been many theories, such as probability statistics, evidence theory, fuzzy set, rough set, cloud model, etc., to deal with uncertainty information from different perspectives, and they have been applied into obtaining the rules and knowledge from amount of data, for example, data mining, knowledge discovery, machine learning, expert system, etc. Simply, This is a cognitive transformation process from data to knowledge (FDtoK). However, the cognitive transformation process from knowledge to data (FKtoD) is what often happens in human brain, but it is lack of research. As an effective cognition model, cloud model provides a cognitive transformation way to realize both processes of FDtoK and FKtoD via forward cloud transformation (FCT) and backward cloud transformation (BCT). In this paper, the authors introduce the FCT and BCT firstly, and make a depth analysis for the two existing single-step BCT algorithms. We find that these two BCT algorithms lack stability and sometimes are invalid. For this reason we propose a new multi-step backward cloud transformation algorithm based on sampling with replacement (MBCT-SR) which is more precise than the existing methods. Furthermore, the effectiveness and convergence of new method is analyzed in detail, and how to set the parameters m, r appeared in MBCT-SR is also analyzed. Finally, we have error analysis and comparison to demonstrate the efficiency of the proposed backward cloud transformation algorithm for some simulation experiments. Content Type Journal Article Pages 55-85 DOI 10.3233/FI-2014-1062 Authors Changlin Xu, School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, P. R. China. xuchlin@163.com Guoyin Wang, Institute of Electronic Information Technology, Chongqing Institute of Green and Intelligent Technology, CAS, Chongqing 400714, P. R. China. wanggy@ieee.org Qinghua Zhang, Chongqing Key Laboratory of Computational Intelligence, Chongqing University of Posts and Telecommunications, Chongqing 400065, P. R. China. zhangqh@cqupt.edu.cn Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 133 Journal Issue Volume 133, Number 1 / 2014

Beschreibung: In this paper, with the aid of the computerized symbolic computation, we present an extended generalized hyperbolic-function method. Being concise and straightforward, it can be applicable to seek more types of solutions for certain nonlinear evolution equations (NLEES). In illustration, we choose the generalized Hamiltonian equations and the (2 + 1)-dimensional Nizhnik-Novikov-Veselov (NNV) equations to demonstrate the validity and advantages of the method. As a result, abundant new exact solutions are obtained including soliton-like solutions, traveling wave solutions etc. The method can be also applied to other nonlinear partial differential equations (NPDEs). Content Type Journal Article Pages 501-517 DOI 10.3233/FI-2014-1056 Authors Jian-Guo Liu, College of Computer, Jiangxi University of Traditional Chinese Medicine, JiangXi 330004, China. 395625298@qq.com Zhi-Fang Zeng, College of Science, Nanchang University, JiangXi 330031, China Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 4 / 2014

Beschreibung: The main objective of our research was to test whether the probabilistic approximations should be used in rule induction from incomplete data. For our research we designed experiments using six standard data sets. Four of the data sets were incomplete to begin with and two of the data sets had missing attribute values that were randomly inserted. In the six data sets, we used two interpretations of missing attribute values: lost values and “do not care” conditions. In addition we used three definitions of approximations: singleton, subset and concept. Among 36 combinations of a data set, type of missing attribute values and type of approximation, for five combinations the error rate (the result of ten-fold cross validation) was smaller than for ordinary (lower and upper) approximations; for other four combinations, the error rate was larger than for ordinary approximations. For the remaining 27 combinations, the difference between these error rates was not statistically significant. Content Type Journal Article Pages 365-379 DOI 10.3233/FI-2014-1049 Authors Patrick G. Clark, Department of Electrical Engineering and Computer Science, University of Kansas, Lawrence, KS 66045, USA. patrick.g.clark@gmail.com; jerzy@ku.edu Jerzy W. Grzymala-Busse, Department of Electrical Engineering and Computer Science, University of Kansas, Lawrence, KS 66045, USA. patrick.g.clark@gmail.com; jerzy@ku.edu Zdzislaw S. Hippe, Department of Expert Systems and Artificial Intelligence, University of Information Technology and Management, 35-225 Rzeszow, Poland. zhippe@wsiz.rzeszow.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 3 / 2014

Beschreibung: In this paper, as variations of a Tai mapping between rooted labeled ordered trees (trees, for short), we introduce a segmental mapping to preserve the parent-children relationship as possible, and also top-down segmengal and bottom-up segmental mappings as the segmental mappings that contain the pair of the roots and the pair of the leaves, respectively. Then, we show that these mappings provide a new hierarchy for the variations of the Tai mapping in addition to a well-known one, in particular, the top-down segmental mapping coincides with a top-down mapping. Also we show that both segmental and bottom-up segmental distances as the minimum costs of segmental and bottom-up segmental mappings are metrics. Next, we design algorithms to compute the segmental and the bottom-up segmental distances in quadratic time and space. Finally, we give experimental results for the segmental distance. Content Type Journal Article Pages 461-483 DOI 10.3233/FI-2014-1054 Authors Tomohiro Kan, Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan. kan@dumbo.ai.kyutech.ac.jp; syou_hig@dumbo.ai.kyutech.ac.jp Shoichi Higuchi, Graduate School of Computer Science and Systems Engineering, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan. kan@dumbo.ai.kyutech.ac.jp; syou_hig@dumbo.ai.kyutech.ac.jp Kouichi Hirata, Department of Artificial Intelligence & Biomedical Informatics R&D Center, Kyushu Institute of Technology, Kawazu 680-4, Iizuka 820-8502, Japan. hirata@ai.kyutech.ac.jp Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 4 / 2014

Beschreibung: The lower and upper approximations in rough set theory will change dynamically over time due to the variation of the information system. Incremental methods for updating approximations in rough set theory and its extensions have received much attention recently. Most existing incremental methods have difficulties in dealing with fuzzy decision systems which decision attributes are fuzzy. This paper introduces an incremental algorithm for updating approximations of rough fuzzy sets under the variation of the object set in fuzzy decision systems. In experiments on 6 data sets from UCI, comparisons of the incremental and non-incremental methods for updating approximations are conducted. The experimental results show that the incremental method effectively reduces the computational time. Content Type Journal Article Pages 401-422 DOI 10.3233/FI-2014-1051 Authors Anping Zeng, School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China. zengap@126.com; trli@swjtu.edu.cn; JunboZhang86@163.com; hm_chen_swjtu@163.com Tianrui Li, School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China. zengap@126.com; trli@swjtu.edu.cn; JunboZhang86@163.com; hm_chen_swjtu@163.com Junbo Zhang, School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China. zengap@126.com; trli@swjtu.edu.cn; JunboZhang86@163.com; hm_chen_swjtu@163.com Hongmei Chen, School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China. zengap@126.com; trli@swjtu.edu.cn; JunboZhang86@163.com; hm_chen_swjtu@163.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 3 / 2014

Beschreibung: We present combinatorial algorithms for solving three problems that appear in the study of the degeneration order ≤ deg for the variety of finite-dimensional modules over a k-algebra Λ, where M ≤ deg N means that a module N belongs to an orbit closure [ ` ( O ( M ) )] of a module M in the variety of Λ-modules. In particular, we introduce algorithmic techniques for deciding whether or not the relation M ≤ deg N holds and for determining all predecessors (resp. succesors) of a given module M with respect to ≤ deg . The order ≤ deg plays an important role in modern algebraic geometry and module theory. Applications of our technique and experimental tests for particular classes of algebras are presented. The results show that a computer algebra technique and algorithmic computer calculations provide important tools in solving theoretical mathematics problems of high computational complexity. The algorithms are implemented and published as a part of an open source GAP package called QPA. Content Type Journal Article Pages 519-532 DOI 10.3233/FI-2014-1057 Authors Andrzej Mróz, Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland. amroz@mat.umk.pl; gzwara@mat.umk.pl Grzegorz Zwara, Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Chopina 12/18, 87-100 Toruń, Poland. amroz@mat.umk.pl; gzwara@mat.umk.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 4 / 2014

Beschreibung: Choquet integral, as an adequate aggregation operator, extends the weighted mean operator by considering interactions among attributes. Choquet integral has been widely used in many real multi-attribute decision making. Weights (fuzzy measures) of attribute sets directly affect the decision results in multi-attribute decision making. In this paper, we aim to propose an objective method based on granular computing for determining the weights of the attribute sets. To address this issue, we first analyze the implied preorder relations under four evaluation forms and construct the corresponding preorder granular structures. Then, we define fuzzy measure of an attribute set by the similarity degree between a special preorder pairs. Finally, we employ two numerical examples for illustrating the feasibility and effectiveness of the proposed method. It is deserved to point out that the weight of each attribute subset can be learned from a given data set by the proposed method, not but be given subjectively by the decision maker. This idea provides a new perspective for multi-attribute decision making. Content Type Journal Article Pages 331-347 DOI 10.3233/FI-2014-1047 Authors Baoli Wang, Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, School of Computer and Information Technology, Shanxi University, Taiyuan 030006, Shanxi, China. pollycomputer@163.com; ljy@sxu.edu.cn; jinchengqyh@126.com Jiye Liang, Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, School of Computer and Information Technology, Shanxi University, Taiyuan 030006, Shanxi, China. pollycomputer@163.com; ljy@sxu.edu.cn; jinchengqyh@126.com Yuhua Qian, Key Laboratory of Computational Intelligence and Chinese Information Processing of Ministry of Education, School of Computer and Information Technology, Shanxi University, Taiyuan 030006, Shanxi, China. pollycomputer@163.com; ljy@sxu.edu.cn; jinchengqyh@126.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 3 / 2014

Beschreibung: In situations where available information or evidence is incomplete or uncertain, probabilistic two-way decisions/classifications with a single threshold on probabilities for making either an acceptance or a rejection decision may be inappropriate. With the introduction of a third non-commitment option, probabilistic three-way decisions use a pair of thresholds and provide an effective and practical decision-making strategy. This paper presents a multifaceted analysis of probabilistic three-way decisions. By identifying an inadequacy of two-way decisions with respect to controlling the levels of various decision errors, we examine the motivations and advantages of three-way decisions. We present a general framework for computing the required thresholds of a three-way decision model as an optimization problem. We investigate two special cases, one is a decision-theoretic rough set model and the other is an information-theoretic rough set model. Finally, we propose a heuristic algorithm for finding the required thresholds. Content Type Journal Article Pages 291-313 DOI 10.3233/FI-2014-1045 Authors Xiaofei Deng, Department of Computer Science, University of Regina, Regina, Saskatchewan S4S 0A2, Canada. {deng200x, yyao}@cs.uregina.ca Yiyu Yao, Department of Computer Science, University of Regina, Regina, Saskatchewan S4S 0A2, Canada. {deng200x, yyao}@cs.uregina.ca Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 3 / 2014

Beschreibung: The paper investigates relationships between chemical structure, surface active properties and antibacterial activity of 70 bis-quaternary imidazolium chlorides. Chemical structure and properties of imidazolium chlorides were described by 7 condition attributes and antimicrobial properties were mapped by a decision attribute. Dominance-based Rough Set Approach (DRSA) was applied to discover a priori unknown rules exhibiting monotonicity relationships in the data, which hold in some parts of the evaluation space. Strong decision rules discovered in this way may enable creating prognostic models of new compounds with favorable antimicrobial properties. Moreover, relevance of the attributes estimated from the discovered rules allows to distinguish which of the structure and surface active properties describe compounds that have the most preferable and the least preferable antimicrobial properties. Content Type Journal Article Pages 315-330 DOI 10.3233/FI-2014-1046 Authors Łukasz Pałkowski, Nicolaus Copernicus University, Collegium Medicum, Department of Pharmaceutical Technology, Jurasza 2, 85-089 Bydgoszcz, Poland. {lukaszpalkowski, jerzy.krysinski}@cm.umk.pl Jerzy Krysiński, Nicolaus Copernicus University, Collegium Medicum, Department of Pharmaceutical Technology, Jurasza 2, 85-089 Bydgoszcz, Poland. {lukaszpalkowski, jerzy.krysinski}@cm.umk.pl Jerzy Błaszczyński, Poznań University of Technology, Institute of Computing Science, Piotrowo 2, 60-965 Poznań, Poland. {jblaszczynski, rslowinski}@cs.put.poznan.pl Roman Słowiński, Poznań University of Technology, Institute of Computing Science, Piotrowo 2, 60-965 Poznań, Poland. {jblaszczynski, rslowinski}@cs.put.poznan.pl Andrzej Skrzypczak, Poznań University of Technology, Institute of Chemical Technology, Skłodowskiej-Curie 2, 60-965 Poznań, Poland Jan Błaszczak, Poznań University of Technology, Institute of Chemical Technology, Skłodowskiej-Curie 2, 60-965 Poznań, Poland Eugenia Gospodarek, Nicolaus Copernicus University, Collegium Medicum, Department of Microbiology, Skłodowskiej-Curie 9, 85-094 Bydgoszcz, Poland Joanna Wróblewska, Nicolaus Copernicus University, Collegium Medicum, Department of Microbiology, Skłodowskiej-Curie 9, 85-094 Bydgoszcz, Poland Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 3 / 2014

Beschreibung: We study unique recovery of cosparse signals from limited-view tomographic measurements of two- and three-dimensional domains. Admissible signals belong to the union of subspaces defined by all cosupports of maximal cardinality ℓ with respect to the discrete gradient operator. We relate ℓ both to the number of measurements and to a nullspace condition with respect to the measurement matrix, so as to achieve unique recovery by linear programming. These results are supported by comprehensive numerical experiments that show a high correlation of performance in practice and theoretical predictions. Despite poor properties of the measurement matrix from the viewpoint of compressed sensing, the class of uniquely recoverable signals basically seems large enough to cover practical applications, like contactless quality inspection of compound solid bodies composed of few materials. Content Type Journal Article Pages 73-102 DOI 10.3233/FI-2014-1113 Authors Andreea Deniţiu, Image and Pattern Analysis Group, University of Heidelberg, Speyerer Str. 6, 69115 Heidelberg, Germany. denitiu@math.uni-heidelberg.de Stefania Petra, Image and Pattern Analysis Group, University of Heidelberg, Speyerer Str. 6, 69115 Heidelberg, Germany. petra@math.uni-heidelberg.de Claudius Schnörr, University of Applied Sciences, Lothstr. 64, 80335 Munich, Germany. schnoerr@cs.hm.edu Christoph Schnörr, Image and Pattern Analysis Group, University of Heidelberg, Speyerer Str. 6, 69115 Heidelberg, Germany. schnoerr@math.uni-heidelberg.de Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 1-2 / 2014

Beschreibung: In tomography, slight differences between the geometry of the scanner hardware and the geometric model used in the reconstruction lead to alignment artifacts. To exploit high-resolution detectors used in many applications of tomography, alignment of the projection data is essential. Markerless alignment algorithms are the preferred choice over alignment with markers, in case a fully automatic tomography pipeline is required. Moreover, marker based alignment is often not feasible or even possible. At the same time, markerless alignment methods often fail in scenarios where only a small number of projections are available. In this case, the angular separation between projection images is large and therefore the correlation between them is low. This is a property that most markerless algorithms rely on. The intermediate reconstruction problem of alignment by projection matching is highly underdetermined in the limited data case. Therefore, we propose a projection matching method that incorporates prior knowledge of the ground truth. We focus on reconstructing binary volumes. A discrete tomography algorithm is employed to generate intermediate reconstructions. This type of reconstruction algorithm does not rely heavily on correlated projection images. Our numerical results suggest that alignment using discrete tomography projection matching produces much better results in the limited angle case, when compared to a projection matching method that employs an algebraic reconstruction method. Content Type Journal Article Pages 21-42 DOI 10.3233/FI-2014-1110 Authors Folkert Bleichrodt, Centrum Wiskunde & Informatica, 1098 XG Amsterdam, The Netherlands. F.Bleichrodt@cwi.nl Jan De Beenhouwer, iMinds - Vision Lab, University of Antwerp, B-2610 Wilrijk, Belgium. jan.debeenhouwer@uantwerpen.be Jan Sijbers, iMinds - Vision Lab, University of Antwerp, B-2610 Wilrijk, Belgium. jan.sijbers@uantwerpen.be Kees Joost Batenburg, Centrum Wiskunde & Informatica, 1098 XG Amsterdam, The Netherlands. K.J.Batenburg@cwi.nl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 1-2 / 2014

Beschreibung: One of the challenges in the development of a content-based image indexing and retrieval application is to achieve an efficient and robust indexing scheme. Color is a fundamental image feature used in content-based image retrieval (CBIR) systems. This paper proposes a robust and effective image retrieval scheme, which is based on the weighed color histogram of visual attention points. Firstly, the fully affine invariant visual attention points are extracted from the origin color image by using the Affine-SIFT (scale-invariant feature transform) detector. Secondly, according to the color complexity measure (CCM) theory, the visual weight values for the significant visual attention points are calculated to reflect the image local variation. Then, the weighed color histogram of visual attention points is constructed. Finally, the similarity between color images is computed by using the weighed color histogram of visual attention points. Experimental results show that the proposed image retrieval is not only more accurate and efficient in retrieving the user-interested images, but also yields higher retrieval accuracy than some state-of-the-art image retrieval schemes for various test DBs. Content Type Journal Article Pages 309-329 DOI 10.3233/FI-2014-1124 Authors Xiang-Yang Wang, School of Computer and Information Technology, Liaoning Normal University, Dalian 116029, P. R. China. wxy37@126.com, yhy_65@126.com Yong-Wei Li, School of Computer and Information Technology, Liaoning Normal University, Dalian 116029, P. R. China. wxy37@126.com, yhy_65@126.com Pan-Pan Niu, School of Computer and Information Technology, Liaoning Normal University, Dalian 116029, P. R. China. wxy37@126.com, yhy_65@126.com Hong-Ying Yang, School of Computer and Information Technology, Liaoning Normal University, Dalian 116029, P. R. China. wxy37@126.com, yhy_65@126.com Dong-Ming Li, School of Computer and Information Technology, Liaoning Normal University, Dalian 116029, P. R. China. wxy37@126.com, yhy_65@126.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 3 / 2014

Beschreibung: Filtered Backprojection is the most widely used reconstruction method in transmission tomography. The algorithm is computationally efficient, but requires a large number of low-noise projections acquired over the full angular range to produce accurate reconstructions. Algebraic reconstruction methods on the other hand are in general more robust with respect to noise and can incorporate the available angular range in the underlying projection model. A drawback of these methods is their higher computational cost. In a recent article, we demonstrated that for linear algebraic reconstruction methods, a filter can be computed such that applying Filtered Backprojection using this filter yields reconstructions that approximate the algebraic method. In the present work, we explore a modification of this approach, where we use more than one algebraic filter in the reconstructions, each covering a different region of the reconstruction grid. We report the results of a series of experiments to determine the how well the reconstruction and approximation accuracy of this approach. Content Type Journal Article Pages 1-19 DOI 10.3233/FI-2014-1109 Authors Linda Plantagie, Centrum Wiskunde & Informatica, Science Park 123, Amsterdam, The Netherlands. linda.plantagie@cwi.nl K. Joost Batenburg, Centrum Wiskunde & Informatica, Science Park 123, Amsterdam, The Netherlands Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 1-2 / 2014

Beschreibung: This paper proposes a framework for analyzing algorithms for inductive processing of bi-connected graphs. The BIBOX algorithm for solving cooperative path-finding problems over bi-connected graphs is submitted for the suggested analysis. The algorithm proceeds according to a decomposition of a given bi-connected graph into handles. After finishing a handle, the handle is ruled out of consideration and the processing task is reduced to a task of the same type on a smaller graph. The handle decomposition for which the BIBOX algorithm performs best is theoretically identified. The conducted experimental evaluation confirms that the suggested theoretical analysis well corresponds to the real situation. Content Type Journal Article Pages 295-308 DOI 10.3233/FI-2014-1123 Authors Pavel Surynek, Department of Theoretical Computer Science and Mathematical Logic, Faculty of Mathematics and Physics, Charles University in Prague, Malostranské náměstí 25, 118 00 Praha 1, Czech Republic. pavel.surynek@mff.cuni.cz Petra Surynková, Department of Mathematics Education, Faculty of Mathematics and Physics, Charles University in Prague, Sokolovská 83, 186 75 Praha 8, Czech Republic. petra.surynkova@mff.cuni.cz Miloš Chromý, Faculty of Mathematics and Physics, Charles University in Prague, Malostranské náměstí 25, 118 00 Praha 1, Czech Republic. miloschromy@gmail.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 3 / 2014

Beschreibung: Computations in Boolean algebra extended by adding an undefined element are investigated in the present paper. These computations (also known as approximative computations) are based on Lukasiewicz three-valued logic and are widely used in those applications where it is necessary to perform logical operations under uncertainty. The approximative computations are carried out as follows: if all instantiations of undefined operands produce the same result then this ascertained result is taken as final; otherwise, the final result is defined to be unknown. The key question in theory of approximative computations is whether a given Boolean formula is closed in the sense that the stepwise approximative computations in compliance with a given formula produce a result as accurate as possible. This question is investigated for the classes of disjunctive and algebraic normal forms. Content Type Journal Article Pages 229-241 DOI 10.3233/FI-2014-1120 Authors Armen Kostanyan, Educational and Research Center of Information Technologies, Yerevan State University, Alex Manoogian 1, 0025 Yerevan, Armenia. armko@ysu.am Paruyr Khnkoyan, Educational and Research Center of Information Technologies, Yerevan State University, Yerevan, Armenia Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 3 / 2014

Beschreibung: In recent years, homomorphisms have been exploited to compare the structures and properties of two generalized information systems. Some of these homomorphisms are based on consistent functions, which are a class of special mappings between universal sets. The purpose of this paper is to unify and extend the consistent functions in the literature into the framework of neighborhood systems. After introducing the notion of consistent functions with respect to neighborhood systems, we explore some important properties of the extended consistent functions such as preserving the inverse images and the intersections of neighborhoods. Our results provide a sound basis for further investigating neighborhood systems via homomorphisms. Content Type Journal Article Pages 331-340 DOI 10.3233/FI-2014-1125 Authors Ping Zhu, School of Science, Beijing University of Posts and Telecommunications, Beijing 100876, China. pzhubupt@gmail.com Huiyang Xie, College of Science, Beijing Forestry University, Beijing 100083, China. xhyang@bjfu.edu.cn Qiaoyan Wen, State Key Laboratory of Networking and Switching, Beijing University of Posts and Telecommunications, Beijing 100876, China. wqy@bupt.edu.cn Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 3 / 2014

Beschreibung: We provide a quadratic-time algorithm for generating hv-convex polyominoes according to a given horizontal projection. The method can be used to generate hv-convex polyominoes with the prescribed projection and with a fixed or arbitrary horizontal dimension, from a uniform random distribution. Content Type Journal Article Pages 103-115 DOI 10.3233/FI-2014-1114 Authors Norbert Hantos, Department of Image Processing and Computer Graphics, University of Szeged, Árpád tér 2. H-6720, Szeged, Hungary. nhantos@inf.u-szeged.hu, pbalazs@inf.u-szeged.hu Péter Balázs, Department of Image Processing and Computer Graphics, University of Szeged, Árpád tér 2. H-6720, Szeged, Hungary. nhantos@inf.u-szeged.hu, pbalazs@inf.u-szeged.hu Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 1-2 / 2014

Beschreibung: A finite graph is one-regular if its automorphism group acts regularly on the set of its arcs. In the present paper, tetravalent one-regular graphs of order 7p 2 , where p is a prime, are classified using computer algebra tools. Content Type Journal Article Pages 211-228 DOI 10.3233/FI-2014-1119 Authors Mohsen Ghasemi, Department of Mathematics, Urmia University, Urmia 57135, Iran. m.ghasemi@urmia.ac.ir Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 3 / 2014

Beschreibung: Geometric distortions that cause displacement between embedding and detection are usually difficult for watermark to survive. It is a challenging work to design a robust image watermarking scheme against geometric distortions, especially for local geometric distortions. Based on probability density and complex angular radial transform theory, a new image watermarking algorithm robust to geometric distortions is proposed in this paper. We firstly extract the steady image feature points by using new image feature point detector, which is based on the probability density. Then we build the affine invariant local feature regions based on probability density auto-correlation matrix. And finally, we present a new image watermarking algorithm robust to geometric distortions, in which the digital watermark is embedded into the local complex angular radial transform (CART) coefficients. Experiments results show that the proposed image watermarking is not only invisible and robust against common image processing operations, but also robust against the geometric distortions. Content Type Journal Article Pages 243-268 DOI 10.3233/FI-2014-1121 Authors Pan-pan Niu, School of Computer and Information Technology, Liaoning Normal University, Dalian 116029, P.R. China. wxy37@126.com; yhy_65@126.com Xiang-yang Wang, School of Computer and Information Technology, Liaoning Normal University, Dalian 116029, P.R. China. wxy37@126.com; yhy_65@126.com Hong-ying Yang, School of Computer and Information Technology, Liaoning Normal University, Dalian 116029, P.R. China. wxy37@126.com; yhy_65@126.com Pei Wang, School of Computer and Information Technology, Liaoning Normal University, Dalian 116029, P.R. China. wxy37@126.com; yhy_65@126.com Ai-long Wang, School of Computer and Information Technology, Liaoning Normal University, Dalian 116029, P.R. China. wxy37@126.com; yhy_65@126.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 3 / 2014

Beschreibung: We investigate a SAT-based bounded model checking (BMC) method for MTL (metric temporal logic) that is interpreted over linear discrete infinite time models generated by discrete timed automata. In particular, we translate the existential model checking problem for MTL to the existential model checking problem for a variant of linear temporal logic (called HLTL), and we provide a SAT-based BMC technique for HLTL. We show how to implement the BMC technique for HLTL and discrete timed automata, and as a case study we apply the technique in the analysis of GTPP, a Generic Timed Pipeline Paradigm modelled by a network of discrete timed automata. Content Type Journal Article Pages 553-568 DOI 10.3233/FI-2014-1140 Authors Bożena Woźna-Szcześniak, IM&CS, Jan Długosz University, Al. Armii Krajowej 13/15, 42-200 Częstochowa, Poland. email: {b.wozna, a.zbrzezny}@ajd.czest.pl Andrzej Zbrzezny, IM&CS, Jan Długosz University, Al. Armii Krajowej 13/15, 42-200 Częstochowa, Poland. email: {b.wozna, a.zbrzezny}@ajd.czest.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 4 / 2014

Beschreibung: In this paper, we complete the study of the geometry of the TDOA map that encodes the noiseless model for the localization of a source from the range differences between three receivers in a plane, by computing the Cartesian equation of the bifurcation curve in terms of the positions of the receivers. From that equation, we can compute its real asymptotic lines. The present manuscript completes the analysis of [12]. Our result is useful to check if a source belongs or is closed to the bifurcation curve, where the localization in a noisy scenario is ambiguous. Content Type Journal Article Pages 199-210 DOI 10.3233/FI-2014-1118 Authors Marco Compagnoni, Dipartimento di Matematica, Politecnico di Milano, I-20133 Milano, Italia. marco.compagnoni@polimi.it, roberto.notari@polimi.it Roberto Notari, Dipartimento di Matematica, Politecnico di Milano, I-20133 Milano, Italia. marco.compagnoni@polimi.it, roberto.notari@polimi.it Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 1-2 / 2014

Beschreibung: In this review paper the synergistic combination of X-ray microtomography, in situ mechanical tests on material samples and full-field kinematic measurements by 3D-Volume Digital Image Correlation is discussed. First, basic features are outlined, concerning X-ray microtomography by either laboratory sources or synchrotron radiation. The main equations for 3D-Volume Digital Image Correlation are then presented, and different provisions regularizing the ill-posed problem of motion estimation are outlined. Thereafter, a survey of the state of the art is provided, with reference to a variety of biological and engineering materials. Limitations and perspectives of the proposed methodology in diverse applications are highlighted. The rapid growth of this research topic is emphasized, due to the truly multi-disciplinary vocation, the synergy between algorithmic and technological solutions, a fusion of experiments and numerical methods. Content Type Journal Article Pages 171-197 DOI 10.3233/FI-2014-1117 Authors Roberto Fedele, Department of Civil and Environmental Engineering (DICA), Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133 Milan, Italy. roberto.fedele@polimi.it Antonia Ciani, Department of Civil and Environmental Engineering (DICA), Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133 Milan, Italy. roberto.fedele@polimi.it Fabrizio Fiori, Università Politecnica delle Marche, Di.S.C.O.-Sezione di Biochimica, Biologia e Fisica, Via Brecce Bianche, 60131 Ancona, Italy Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 1-2 / 2014

Beschreibung: Discrete Tomography (DT), differently from GT and CT, focuses on the case where only few specimen projections are known and the images contain a small number of different colours (e.g. black-and-white). A concise review on main contemporary physical and mathematical CT system problems is offered. Stochastic vs. Combinatorially Optimized Noise generation is compared and presented by two visual examples to emphasise a major double-bind problem at the core of contemporary most advanced instrumentation systems. Automatic tailoring denoising procedures to real dynamic system characteristics and performance can get closer to ideal self-registering and self-linearizing system to generate virtual uniform and robust probing field during its whole designed service life-cycle. The first attempt to develop basic principles for system background low-level noise source automatic characterization, profiling and identification by CICT, from discrete system parameter, is presented. As a matter of fact, CICT can supply us with cyclic numeric sequences perfectly tuned to their low-level multiplicative source generators, related to experimental high-level overall perturbation (according to high-level classic perturbation computational model under either additive or multiplicative perturbation hypothesis). Numeric examples are presented. Furthermore, a practical NTT example is given. Specifically, advanced CT system, HRO and Mission Critical Project (MCP) for very low Technological Risk (TR) and Crisis Management (CM) system will be highly benefitted mostly by CICT infocentric worldview. The presented framework, concepts and techniques can be used to boost the development of next generation algorithms and advanced applications quite conveniently. Content Type Journal Article Pages 135-170 DOI 10.3233/FI-2014-1116 Authors Rodolfo A. Fiorini, Department of Electronics, Information and Bioengineering (DEIB), Politecnico di Milano, P.za Leonardo da Vinci 32, 20133 Milano, Italy. rodolfo.fiorini@polimi.it Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 1-2 / 2014

Beschreibung: We consider words on a finite alphabet Σ and study the structure of its σ-palindromes, i.e. words w satisfying w = σ([( w )\tilde]) for some involution σ on the alphabet. We provide algorithms for the computation of σ-lacunas in w, that is the positions where the longest σ-palindromic suffix is not uni-occurrent. The σ-palindromic defect is explicitly computed for Sturmian words and the Thue-Morse word. Finally, the problem of reconstructing words from a given fixed set of σ-palindromes is decidable. Content Type Journal Article Pages 59-72 DOI 10.3233/FI-2014-1112 Authors Srečko Brlek, Laboratoire de Combinatoire et d'Informatique Mathématique, Université du Québec ă Montréal, C. P. 8888 Succursale “Centre-Ville”, Montréal (QC), Canada H3C 3P8. Brlek.Srecko@uqam.ca, nadia.l@lacim.ca Nadia Lafreniére, Laboratoire de Combinatoire et d'Informatique Mathématique, Université du Québec ă Montréal, C. P. 8888 Succursale “Centre-Ville”, Montréal (QC), Canada H3C 3P8. Brlek.Srecko@uqam.ca, nadia.l@lacim.ca Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 1-2 / 2014

Beschreibung: In this paper we tackle the problem of the reconstruction of object based images, specifically formed by a set of circles inside a ring. By analyzing the projections of the image, we are able to determine some coordinates corresponding to interest points that give significant information about features of the image of aid in the reconstruction. Our approach yields promising results in comparison to other methods in literature. Finally, we discuss how a similar approach could be extended to more complex problems deriving from tomographic applications, in order to develop an efficient method exploiting the prior knowledge assumed on an image. Content Type Journal Article Pages 43-57 DOI 10.3233/FI-2014-1111 Authors Stefano Brocchi, Dipartimento di Matematica e Informatica ‘U. Dini’, Università degli Studi di Firenze, Viale Morgagni 65, 50134 Firenze, Italy. stefano.brocchi@unifi.it Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 1-2 / 2014

Beschreibung: In this paper the well-known problem of reconstructing hv-convex polyominoes is considered from a set of noisy data. Differently from the usual approach of Binary Tomography, this leads to a probabilistic evaluation in the reconstruction algorithm, where different pixels assume different probabilities to be part of the reconstructed image. An iterative algorithm is then applied, which, starting from a random choice, leads to an explicit reconstruction matching the noisy data. Content Type Journal Article Pages 117-134 DOI 10.3233/FI-2014-1115 Authors Alexandre Goupy, ENSTA ParisTech, 828, Bd des Maréchaux, 91762 Palaiseau, France. alexandre.goupy@ensta-paristech.fr Silvia M.C. Pagani, Dipartimento di Matematica “F. Brioschi”, Politecnico di Milano, Piazza Leonardo da Vinci, 32, I-20133 Milano, Italy. silviamaria.pagani@polimi.it Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 1-2 / 2014

Beschreibung: To model and analyze systems with multi-valued information, in this paper, we present an extension of Kripke structures in the framework of complete residuted lattices, which we will refer to as lattice-valued Kripke structures (LKSs). We then show how the traditional trace containment and equivalence relations, can be lifted to the lattice-valued setting, and we introduce two families of lattice-valued versions of the relations. Further, we explore some interesting properties of these relations. Finally, we provide logical characterizations of our relations by a natural extension of linear temporal logic. Content Type Journal Article Pages 269-293 DOI 10.3233/FI-2014-1122 Authors Haiyu Pan, College of Computer Science, Shaanxi Normal University, Xi'an 710062, China. phyu76@126.com Min Zhang, Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, 200062, Shanghai, China. mzhang@sei.ecnu.edu.cn Hengyang Wu, Information Engineer College, Hangzhou Dianzi University, 310018, Hangzhou, China. wuhengy_1974@aliyun.com Yixiang Chen, Shanghai Key Laboratory of Trustworthy Computing, East China Normal University, 200062, Shanghai, China. yxchen@sei.ecnu.edu.cn Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 135 Journal Issue Volume 135, Number 3 / 2014

Beschreibung: While evolutionary development methodologies have become increasingly prevalent, incremental testing methods are lagging behind. Most traditional test generation algorithms – including the Transition Tour method – rebuild test sequences from scratch even if minimal changes to the system have been made. In the current paper we propose two incremental algorithms to update a Transition Tour test sequence after changes in a deterministic finite state machine model. Our solution uses existing information – the Eulerian graph of a previous version of the system and an Euler tour in it – to update the test cases of the system in response to modification. The first algorithm keeps an Eulerian graph up to date, while the second algorithm maintains an Euler tour in the augmented graph. Analytical and practical analyses show that our algorithms are very efficient in the case of changing specifications. We also demonstrate our methods through an example. Content Type Journal Article Pages 279-300 DOI 10.3233/FI-2014-972 Authors Gábor Árpád Németh, High Speed Networks Laboratory, Department of Telecommunications and Media Informatics, Budapest University of Technology and Economics, Magyar tudósok körútja 2, Budapest, H-1117, Hungary. gabor.nemeth@tmit.bme.hu; pap@tmit.bme.hu Zoltán Pap, High Speed Networks Laboratory, Department of Telecommunications and Media Informatics, Budapest University of Technology and Economics, Magyar tudósok körútja 2, Budapest, H-1117, Hungary. gabor.nemeth@tmit.bme.hu; pap@tmit.bme.hu Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 3 / 2014

Beschreibung: In Artificial Intelligence with Coalition Structure Generation (CSG) one refers to those cooperative complex problems that require to find an optimal partition (maximizing a social welfare) of a set of entities involved in a system. The solution of the CSG problem finds applications in many fields such as Machine Learning (set covering machines, clustering), Data Mining (decision tree, discretization), Graph Theory, Natural Language Processing (aggregation), Semantic Web (service composition), and Bioinformatics. The problem of finding the optimal coalition structure is NP-complete. In this paper we present a greedy adaptive search procedure (GRASP) with path-relinking to efficiently search the space of coalition structures. Experiments and comparisons to other algorithms prove the validity of the proposed method in solving this hard combinatorial problem. Content Type Journal Article Pages 251-277 DOI 10.3233/FI-2014-971 Authors Nicola Di Mauro, Department of Computer Science, University of Bari, Italy. {ndm, basile, ferilli, esposito}@di.uniba.it Teresa M.A. Basile, Department of Computer Science, University of Bari, Italy. {ndm, basile, ferilli, esposito}@di.uniba.it Stefano Ferilli, Department of Computer Science, University of Bari, Italy. {ndm, basile, ferilli, esposito}@di.uniba.it Floriana Esposito, Department of Computer Science, University of Bari, Italy. {ndm, basile, ferilli, esposito}@di.uniba.it Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 3 / 2014

Beschreibung: Multi-Relational Data Mining (MRDM) refers to the process of discovering implicit, previously unknown and potentially useful information from data scattered in multiple tables of a relational database. Following the mainstream of MRDM research, we tackle the regression where the goal is to examine samples of past experience with known continuous answers (response) and generalize future cases through an inductive process. Mr-SMOTI, the solution we propose, resorts to the structural approach in order to recursively partition data stored into a tightly-coupled database and build a multi-relational model tree which captures the linear dependence between the response variable and one or more explanatory variables. The model tree is top-down induced by choosing, at each step, either to partition the training space or to introduce a regression variable in the linear models with the leaves. The tight-coupling with the database makes the knowledge on data structures (foreign keys) available free of charge to guide the search in the multi-relational pattern space. Experiments on artificial and real databases demonstrate that in general Mr-SMOTI outperforms both SMOTI and M5' which are two propositional model tree induction systems, and TILDE-RT which is a state-of-art structural model tree induction system. Content Type Journal Article Pages 193-224 DOI 10.3233/FI-2014-969 Authors Annalisa Appice, Dipartimento di Informatica, Università degli Studi Aldo Moro di Bari, Italy. {annalisa.appice, michelangelo.ceci, donato.malerba}@uniba.it Michelangelo Ceci, Dipartimento di Informatica, Università degli Studi Aldo Moro di Bari, Italy. {annalisa.appice, michelangelo.ceci, donato.malerba}@uniba.it Donato Malerba, Dipartimento di Informatica, Università degli Studi Aldo Moro di Bari, Italy. {annalisa.appice, michelangelo.ceci, donato.malerba}@uniba.it Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 3 / 2014

Beschreibung: We introduce a new threshold model of social networks, in which the nodes influenced by their neighbours can adopt one out of several alternatives. We characterize social networks for which adoption of a product by the whole network is possible (respectively necessary) and the ones for which a unique outcome is guaranteed. These characterizations directly yield polynomial time algorithms that allow us to determine whether a given social network satisfies one of the above properties. We also study algorithmic questions for networks without unique outcomes. We show that the problem of determining whether a final network exists in which all nodes adopted some product is NP-complete. In turn, we also resolve the complexity of the problems of determining whether a given node adopts some (respectively, a given) product in some (respectively, all) network(s). Further, we show that the problem of computing the minimum possible spread of a product is NP-hard to approximate with an approximation ratio better than Ω(n), in contrast to the maximum spread, which is efficiently computable. Finally, we clarify that some of the above problems can be solved in polynomial time when there are only two products. Content Type Journal Article Pages 225-250 DOI 10.3233/FI-2014-970 Authors Krzysztof R. Apt, CWI, Amsterdam, the Netherlands and University of Amsterdam, Netherlands. apt@cwi.nl Evangelos Markakis, Athens University of Economics and Business, Athens, Greece. markakis@gmail.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 3 / 2014

Beschreibung: Hyperelliptic curves have been widely researched for cryptographic applications, and some special hyperelliptic curves are often considered for practical applications. For efficient implementation of hyperelliptic curve cryptosystems, it is crucial to have efficient scalar multiplication in the Jacobian groups. For the hyperelliptic curve C q : v 2 = u p − au − b over the field \Fopf q with q a power of an odd prime p, Duursma and Sakurai (2000) presented a scalar multiplication algorithm for q = p, a = 1 and b ∈ \Fopf p . In this paper, by introducing the concept of simple divisors, we prove that a general divisor can be decomposed into the sum of some simple divisors. Based on this fact, we present a formula for p-scalar multiplications for any reduced divisor, then we give two efficient algorithms to speed up scalar multiplications for any parameters a and b over any extension of \Fopf p . Compared with the signed binary method, the computations of our algorithms cost 55% to 76% less. Content Type Journal Article Pages 395-412 DOI 10.3233/FI-2014-978 Authors Lin You, College of Communication Engineering, Hangzhou Dianzi University, Hangzhou 310018, China. mryoulin@gmail.com; ylyangapple@hotmail.com Yilin Yang, College of Communication Engineering, Hangzhou Dianzi University, Hangzhou 310018, China. mryoulin@gmail.com; ylyangapple@hotmail.com Shuhong Gao, Department of Mathematical Sciences, Clemson University, Clemson, SC 29634-0975, USA. sgao@clemson.edu Yongxuan Sang, College of Communication Engineering, Hangzhou Dianzi University, Hangzhou, China. sangyongxuan@126.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 4 / 2014

Beschreibung: Rough sets are efficient to extract rules from information systems. Matroids generalize the linear independency in vector spaces and the cycle in graphs. Specifically, matroids provide well-established platforms for greedy algorithms, while most existing algorithms for many rough set problems including attribute reduction are greedy ones. Therefore, the combination between rough sets and matroids may bring new efficient solutions to those important and difficult problems. In this paper, 2-circuit matroids, abstracted from matroidal characteristics of rough sets, are studied and axiomatized. A matroid is induced by an equivalence relation, and its characteristics including the independent set and duality are represented with rough sets. Based on these rough set representations, this special type of matroid is defined as 2-circuit matroids. Conversely, an equivalence relation is induced by a matroid, and its relationship with the above induction is further investigated. Finally, a number of axioms of the 2-circuit matroid are obtained through rough sets. These interesting and diverse axioms demonstrate the potential for the connection between rough sets and matroids. Content Type Journal Article Pages 377-393 DOI 10.3233/FI-2013-977 Authors Shiping Wang, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China Qingxin Zhu, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China William Zhu, Lab of Granular Computing, Minnan Normal University, Zhangzhou 363000, China. williamfengzhu@gmail.com Fan Min, Lab of Granular Computing, Minnan Normal University, Zhangzhou 363000, China. williamfengzhu@gmail.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 4 / 2014

Beschreibung: Certificateless cryptography is a new type of public key cryptography, which removes the certificate management problem in traditional public key cryptography and the key escrow problem in identity-based public key cryptography. Multi-proxy signature is an extension of proxy signature, which allows an original signer authorizing a group of proxy signers and only the cooperation of all proxy signers in the group can create valid proxy signatures on behalf of the original signer. Recently, Jin and Wen combined certificateless cryptography with multi-proxy signature, and proposed a model as well as a concrete scheme of certificateless multi-proxy signature. They claimed that their scheme is provably secure in their security model. Unfortunately, in this paper by giving two attacks, we will show that their certificateless multi-proxy signature scheme can be broken. The first attack indicates their security model is flawed and the second attack indicates their certificateless multi-proxy signature scheme is insecure. Possible improvements are also suggested to prevent these attacks. Content Type Journal Article Pages 365-375 DOI 10.3233/FI-2013-976 Authors Miaomiao Tian, School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, P.R. China. miaotian@mail.ustc.edu.cn Wei Yang, School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, P.R. China. miaotian@mail.ustc.edu.cn Liusheng Huang, School of Computer Science and Technology, University of Science and Technology of China, Hefei 230026, P.R. China. miaotian@mail.ustc.edu.cn Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 4 / 2014

Beschreibung: We present a set of guidelines for improving quality and efficiency in initial steps of the KDD process by utilizing various kinds of domain knowledge. We discuss how such knowledge may be used to the advantage of system developer and what kinds of improvements can be achieved. We focus on systems that incorporate creation and processing of compound data objects within the RDBMS framework. These basic considerations are illustrated with several examples of implemented database solutions. Content Type Journal Article Pages 341-364 DOI 10.3233/FI-2014-975 Authors Marcin Szczuka, Institute of Mathematics, The University of Warsaw, Warsaw, Poland. szczuka@mimuw.edu.pl Łukasz Sosnowski, Systems Research Institute, Polish Academy of Sciences and Dituel Sp. z o.o., Warsaw, Poland. l.sosnowski@dituel.pl Adam Krasuski, Section of Computer Science, The Main School of Fire Service, Warsaw, Poland. krasuski@inf.sgsp.edu.pl, krenski@inf.sgsp.edu.pl Karol Kreński, Section of Computer Science, The Main School of Fire Service, Warsaw, Poland. krasuski@inf.sgsp.edu.pl, krenski@inf.sgsp.edu.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 4 / 2014

Beschreibung: This paper studies the concepts of definability and canonicity in Boolean logic with a binary relation. Firstly, it provides formulas defining first-order or second-order conditions on frames. Secondly, it proves that all formulas corresponding to compatible first-order conditions on frames are canonical. Content Type Journal Article Pages 301-327 DOI 10.3233/FI-2014-973 Authors Philippe Balbiani, Institut de recherche en informatique de Toulouse, CNRS — Université de Toulouse, 118 route de Narbonne, 31062 Toulouse Cedex 9, France. Philippe.Balbiani@irit.fr Tinko Tinchev, Department of Mathematical Logic and Applications, Sofia University, Blvd James Bouchier 5, 1126 Sofia, Bulgaria. tinko@fmi.uni-sofia.bg Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 4 / 2014

Beschreibung: The longest common subsequence (LCS) problem is a classic and well-studied problem in computer science. Palindrome is a word which reads the same forward as it does backward. The longest common palindromic subsequence (LCPS) problem is a variant of the classic LCS problem which finds a longest common subsequence between two given strings such that the computed subsequence is also a palindrome. In this paper, we study the LCPS problem and give two novel algorithms to solve it. To the best of our knowledge, this is the first attempt to study and solve this problem. Content Type Journal Article Pages 329-340 DOI 10.3233/FI-2014-974 Authors Shihabur Rahman Chowdhury, AlEDA group, Department of CSE, Bangladesh University of Engineering & Technology, Dhaka - 1000, Bangladesh. {shihab, mahbub86, sumaiya, msrahman}@cse.buet.ac.bd Md. Mahbubul Hasan, AlEDA group, Department of CSE, Bangladesh University of Engineering & Technology, Dhaka - 1000, Bangladesh. {shihab, mahbub86, sumaiya, msrahman}@cse.buet.ac.bd Sumaiya Iqbal, AlEDA group, Department of CSE, Bangladesh University of Engineering & Technology, Dhaka - 1000, Bangladesh. {shihab, mahbub86, sumaiya, msrahman}@cse.buet.ac.bd M. Sohel Rahman, AlEDA group, Department of CSE, Bangladesh University of Engineering & Technology, Dhaka - 1000, Bangladesh. {shihab, mahbub86, sumaiya, msrahman}@cse.buet.ac.bd Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 129 Journal Issue Volume 129, Number 4 / 2014

Beschreibung: We give a discretization of behaviors of timed automata, in which timed languages are represented as sets of words containing action symbols, a clock tick symbol 1, and two delay symbols δ − (negative delay) and δ + (positive delay). Unlike the region construction, our discretization commutes with intersection. We show that discretizations of timed automata are, in general, context-sensitive languages over Σ ∪ {1, δ + , δ − }, and give a class of counter automata that accepts exactly the class of languages that are discretizations of timed automata, and show that its emptiness problem is decidable. Content Type Journal Article Pages 389-407 DOI 10.3233/FI-2014-1021 Authors Cătălin Dima, Université Paris-Est, LACL (EA 4219), UPEC, 61 avenue du Général de Gaulle, 94010 Créteil Cedex, France. dima@u-pec.fr Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 3-4 / 2014

Beschreibung: In this paper we define a new class of contextual grammars and study how the languages generated by such grammars can be accepted by go-through automata. The newly introduced class of grammars is a generalization of the formalism previously used to describe the linguistic process of syllabification. Go-through automata which are used here to recognize, and also parse, the languages generated by this new class of grammars are generalizations of push-down automata in the area of context-sensitivity; they have been proved to be an efficient tool for the recognition of languages generated by contextual grammars. The main results of the paper show how the newly introduced generative model is related with other classes of Marcus contextual languages, and how syllabic languages are recognized and parsed using go-through automata. Content Type Journal Article Pages 409-424 DOI 10.3233/FI-2014-1022 Authors Liviu P. Dinu, University of Bucharest, Faculty of Mathematics and Computer Science, Academiei 14, 010014 Bucharest, Romania. ldinu@fmi.unibuc.ro, radu.gramatovici@fmi.unibuc.ro, flm@informatik.uni-kiel.de Radu Gramatovici, University of Bucharest, Faculty of Mathematics and Computer Science, Academiei 14, 010014 Bucharest, Romania. ldinu@fmi.unibuc.ro, radu.gramatovici@fmi.unibuc.ro, flm@informatik.uni-kiel.de Florin Manea, University of Bucharest, Faculty of Mathematics and Computer Science, Academiei 14, 010014 Bucharest, Romania. ldinu@fmi.unibuc.ro, radu.gramatovici@fmi.unibuc.ro, flm@informatik.uni-kiel.de Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 3-4 / 2014

Beschreibung: The paper presents a method of reasoning about the behaviour of asynchronous programs in denotational models designed with metric spaces and continuation semantics for concurrency. Content Type Journal Article Pages 373-388 DOI 10.3233/FI-2014-1020 Authors Gabriel Ciobanu, Institute of Computer Science, Romanian Academy, Iaşi, Romania. gabriel@info.uaic.ro Eneia Nicolae Todoran, Department of Computer Science, Technical University of Cluj-Napoca, Cluj-Napoca, Romania. eneia.todoran@cs.utcluj.ro Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 3-4 / 2014

Beschreibung: Reaction systems are a formal framework for modeling processes driven by biochemical reactions. They are based on the mechanisms of facilitation and inhibition. A main assumption is that if a resource is available, then it is present in sufficient amounts and as such, several reactions using the same resource will not compete concurrently against each other; this makes reaction systems very different as a modeling framework than traditional frameworks such as ODEs or continuous time Markov chains. We demonstrate in this paper that reaction systems are rich enough to capture the essential characteristics of ODE-based models. We construct a reaction system model for the heat shock response in such a way that its qualitative behavior correlates well with the quantitative behavior of the corresponding ODE model. We construct our reaction system model based on a novel concept of dominance graph that captures the competition on resources in the ODE model. We conclude with a discussion on the expressivity of reaction systems as compared to that of ODE-based models. Content Type Journal Article Pages 299-312 DOI 10.3233/FI-2014-1016 Authors Sepinoud Azimi, Computational Biomodeling Laboratory, Turku Centre for Computer Science, Åbo Akademi University, 20520 Turku, Finland. {Sepinoud.Azimi, Bogdan.Iancu, Ion.Petre}@abo.fi Bogdan Iancu, Computational Biomodeling Laboratory, Turku Centre for Computer Science, Åbo Akademi University, 20520 Turku, Finland. {Sepinoud.Azimi, Bogdan.Iancu, Ion.Petre}@abo.fi Ion Petre, Computational Biomodeling Laboratory, Turku Centre for Computer Science, Åbo Akademi University, 20520 Turku, Finland. {Sepinoud.Azimi, Bogdan.Iancu, Ion.Petre}@abo.fi Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 3-4 / 2014

Beschreibung: Scientists have long dreamed of creating machines humans could interact with by voice. Although one no longer believes Turing's prophecy that machines will be able to converse like humans in the near future, real progress has been made in the voice and text-based human-machine interaction. This paper is a light introduction and survey of some deployed natural language systems and technologies and their historical evolution. We review two fundamental problems involving natural language: the language prediction problem and the language understanding problem. While describing in detail all these technologies is beyond our scope, we do comment on some aspects less discussed in the literature such as language prediction using huge models and semantic labeling using Marcus contextual grammars. Content Type Journal Article Pages 425-440 DOI 10.3233/FI-2014-1023 Authors Nicolae Duta, New England Research and Development Center, Microsoft, Cambridge, USA. niduta@microsoft.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 3-4 / 2014

Beschreibung: We introduce and study the nominal groups, providing some algebraic properties of this new structure. We focus on the properties of nominal homomorphisms, and study the correspondence between some results obtained in the Fraenkel-Mostowski framework (where only finitely supported objects are allowed) and those obtained in the classical Zermelo-Fraenkel framework. Content Type Journal Article Pages 279-298 DOI 10.3233/FI-2014-1015 Authors Andrei Alexandru, Institute of Computer Science, Romanian Academy, Iaşi, Romania. gabriel@info.uaic.ro, aalexandru@iit.tuiasi.ro Gabriel Ciobanu, Institute of Computer Science, Romanian Academy, Iaşi, Romania. gabriel@info.uaic.ro, aalexandru@iit.tuiasi.ro Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 3-4 / 2014

Beschreibung: Soccer game is a good playground for testing artificial intelligence of robots and methods for spatial reasoning in real conditions. Decision making and path planning are only two of many tasks performed while playing soccer. This paper describes an application of rough mereology introduced by Polkowski and Skowron (1994) for path planning in robotic soccer game. Our path planning method was based on mereological potential fields introduced by Polkowski and Ośmiałowski (2008) and Ośmiałowski (2009) but was redesigned due to conditions of dynamic soccer environment, so an entirely new method was developed. Content Type Journal Article Pages 241-251 DOI 10.3233/FI-2014-1012 Authors Łukasz Przytuła, Department of Mathematics and Computer Science, University of Warmia and Mazury, Sloneczna 54 2, 10-710 Olsztyn, Poland. lukasz.przytula@uwm.edu.pl Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 131 Journal Issue Volume 131, Number 2 / 2014

Beschreibung: Integration of spatial data into multidimensional models leads to the concept of Spatial OLAP (SOLAP). Usually, SOLAP models exploit discrete spatial data. Few works integrate continuous field data into dimensions and measures. In this paper, we provide a formal multidimensional model that supports measures and dimension as continuous field data, independently of their implementation. We provide also a proposal for a logical model allowing aggregation of field measures in a feasible ROLAP architecture. Content Type Journal Article Pages 267-290 DOI 10.3233/FI-2014-1043 Authors Sandro Bimonte, Irstea, TSCF, Campus des CEZEAUX, 63173 AUBIERE, France. sandro.bimonte@cemagref.fr Myoung-Ah Kang, LIMOS-UMR CNRS 6158, ISIMA, Blaise Pascal University, Campus des CEZEAUX, 63173 AUBIERE, France. kang@isima.fr Luca Paolino, Department of Management and Information Technology (DISTRA), University of Salerno, I-84084 Fisciano (SA), Italy. lpaolino@unisa.it Monica Sebillo, Department of Management and Information Technology (DISTRA), University of Salerno, I-84084 Fisciano (SA), Italy. msebillo@unisa.it Mehdi Zaamoune, Irstea, TSCF, Campus des CEZEAUX, 63173 AUBIERE, France. mehdi.zaamoune@irstea.fr Giuliana Vitiello, Department of Management and Information Technology (DISTRA), University of Salerno, I-84084 Fisciano (SA), Italy. gvitiello@unisa.it Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 2 / 2014

Beschreibung: The majority of today's systems increasingly require sophisticated data management as they need to store and to query large amounts of data for analysis and reporting purposes. In order to keep more “detailed” data available for longer periods, “old” data has to be reduced gradually to save space and improve query performance, especially on resource-constrained systems with limited storage and query processing capabilities. A number of data reduction solutions have been developed, however an effective solution particularly based on gradual data reduction is missing. This paper presents an effective solution for data reduction based on gradual granular data aggregation. With the gradual granular data aggregation mechanism, older data can be made coarse-grained while keeping the newest data fine-grained. For instance, when data is 3 months old aggregate to 1 minute level from 1 second level, when data is 6 months old aggregate to 2 minutes level from 1 minute level and so on. The proposed solution introduces a time granularity based data structure, namely a relational time granularity table that enables long term storage of old data by maintaining it at different levels of granularity and effective query processing due to a reduction in data volume. In addition, the paper describes the implementation strategy derived from a farming case study using standard database technologies. Content Type Journal Article Pages 153-176 DOI 10.3233/FI-2014-1039 Authors Nadeem Iftikhar, Department of Computer Science, Aalborg University, Selma Lagerlöfs Vej 300, 9220 Aalborg Ø, Denmark. naif@ucn.dk; tbp@cs.aau.dk Torben Bach Pedersen, Department of Computer Science, Aalborg University, Selma Lagerlöfs Vej 300, 9220 Aalborg Ø, Denmark. naif@ucn.dk; tbp@cs.aau.dk Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 2 / 2014

Beschreibung: We study the class of word-building games, where two players pick letters from a finite alphabet to construct a finite or infinite word. The outcome is determined by whether the resulting word lies in a prescribed set (a win for player A) or not (a win for player B). We focus on symbolic dynamical games, where the target set is a subshift. We investigate the relation between the target subshift and the set of turn orders for which A has a winning strategy. Content Type Journal Article Pages 131-152 DOI 10.3233/FI-2014-1037 Authors Ville Salo, TUCS – Turku Centre for Computer Science, Finland; University of Turku, Finland. vosalo@utu.fi, iatorm@utu.fi Ilkka Törmä, TUCS – Turku Centre for Computer Science, Finland; University of Turku, Finland. vosalo@utu.fi, iatorm@utu.fi Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 1 / 2014

Beschreibung: An infinite square-free word w over the alphabet Σ 3 = {0, 1, 2} is said to have a k-stem σ if |σ| = k and w = σw 1 w 2 ... where for each i, there exists a permutation π i of Σ 3 which extended to a morphism gives w i = π i (σ). Harju proved that there exists an infinite k-stem word for k = 1, 2, 3, 9 and 13 ≤ k ≤ 19, but not for 4 ≤ k ≤ 8 and 10 ≤ k ≤ 12. He asked whether k-stem words exist for each k ≥ 20. We give a positive answer to this question. Currie has found another construction that answers Harju's question. Content Type Journal Article Pages 109-112 DOI 10.3233/FI-2014-1035 Authors Pascal Ochem, LIRMM, CNRS, Univ. Montpellier 2, France. ochem@lirmm.fr Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 1 / 2014

Beschreibung: In this paper we study heuristic proof systems and heuristic non-deterministic algorithms. We give an example of a language Y and a polynomial-time samplable distribution D such that the distributional problem (Y, D) belongs to the complexity class HeurNP but Y ∉ NP if NP ≠ coNP, and (Y, D) ∉ HeurBPP if (NP,PSamp) \nsubseteq HeurBPP. For a language L and a polynomial q we define the language pad q (L) composed of pairs (x, r) where x is an element of L and r is an arbitrary binary string of length at least q(|x|). If D = { D n } ¥ n =1 is an ensemble of distributions on strings, let D × U q be a distribution on pairs (x, r), where x is distributed according to D n and r is uniformly distributed on strings of length q(n). We show that for every language L in AM there is a polynomial q such that for every distribution D concentrated on the complement of L the distributional problem (pad q (L), D × U q ) has a polynomially bounded heuristic proof system. Since graph non-isomorphism (GNI) is in AM, the above result is applicable to GNI. Content Type Journal Article Pages 113-129 DOI 10.3233/FI-2014-1036 Authors Dmitry Itsykson, Steklov Institute of Mathematics at St. Petersburg, 27 Fontanka, St.Petersburg, 191023, Russia. dmitrits@pdmi.ras.ru, sokolov.dmt@gmail.com Dmitry Sokolov, Steklov Institute of Mathematics at St. Petersburg, 27 Fontanka, St.Petersburg, 191023, Russia. dmitrits@pdmi.ras.ru, sokolov.dmt@gmail.com Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 1 / 2014

Beschreibung: Data warehouses help to store and analyze large multidimensional datasets and provide enterprise decision support. With an increased availability of spatial data in recent years, several new strategies have been proposed to enable their integration into data warehouses and and perform complex OLAP analysis. Cardinal directions have turned out to be very important qualitative spatial relations due to their numerous applications in spatial wayfinding, GIS, qualitative spatial reasoning and in domains such as cognitive sciences, AI and robotics. They are frequently used as selection and restriction criteria in spatial queries. In data warehouses, cardinal directions can be used to perform spatial OLAP and feature navigation operations. In this article, we introduce and develop the Objects Interaction Graticule (OIG) approach to query the cardinal direction relations among spatio-temporal objects in data warehouses. First, we apply a tiling strategy that determines the zones belonging to the nine cardinal directions of each spatial object at a particular time and intersects them. This leads to a collection of grids over time called the Objects Interaction Graticule (OIG). For each grid cell, the information about the spatial objects that intersect it is stored in a Objects Interaction Matrix. In the second phase, an interpretation method is applied to these matrices to determine the cardinal direction between the moving objects. The results obtained for each valid instant over the objects' lifetime describe the variation in the objects movement over time. This is integrated as a spatio-temporal OLAP operation in a novel moving objects data warehouse (MODW) that provides an extensible framework for supporting complex structured objects. Finally, we define new directional predicates that extend MDX querying and leverage OLAP between moving objects. Content Type Journal Article Pages 177-202 DOI 10.3233/FI-2014-1040 Authors Ganesh Viswanathan, Department of Computer & Information Science & Engineering, University of Florida, Gainesville, FL 32611, USA. gv1@cise.ufl.edu; mschneid@cise.ufl.edu Markus Schneider, Department of Computer & Information Science & Engineering, University of Florida, Gainesville, FL 32611, USA. gv1@cise.ufl.edu; mschneid@cise.ufl.edu Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 2 / 2014

Beschreibung: This paper presents a multidimensional model and a language to construct cubes for the purpose of on-line analytical processing. Both the multidimensional model and the cube model are based on the concept of complex object which models complex entities of real world. The multidimensional model is presented at two layers: the class diagram layer and the package layer. Both layers are used by a projection operation that aims at extracting cubes: at the package diagram layer, the projection dynamically assigns the roles of fact and dimensions to the complex objects of the multidimensional model whereas at the class diagram layer, it allows designing the measures. We also provide operations that optimize the construction of new cubes by using existing ones. The set of operations for cube construction are expressed by formal operators, thus forming a language. To show the feasibility of our multidimensional model and operators, we present implementation details of a real case study. Content Type Journal Article Pages 203-238 DOI 10.3233/FI-2014-1041 Authors Doulkifli Boukraa, High School of Computer Science, Oued-Smar, Algiers. d_boukraa@esi.dz Omar Boussaid, Lumière University - Lyon 2, 5 avenue Pierre Mendès-France, 69676 Bron Cedex. omar.boussaid@univ-lyon2.fr Fadila Bentayeb, Lumière University - Lyon 2, 5 avenue Pierre Mendès-France, 69676 Bron Cedex. fadila.bentayeb@univ-lyon2.fr Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 2 / 2014

Beschreibung: We study ideal languages generated by a single word. We provide an algorithm to construct a strongly connected synchronizing automaton for which such a language serves as the language of synchronizing words. Also we present a compact formula to calculate the syntactic complexity of this language. Content Type Journal Article Pages 95-108 DOI 10.3233/FI-2014-1034 Authors Vladimir V. Gusev, Institute of Mathematics and Computer Science, Ural Federal University, Lenina st. 51, Ekaterinburg 620083, Russia. vl.gusev@gmail.com, maslennikova.marina@gmail.com, elena.pribavkina@usu.ru Marina I. Maslennikova, Institute of Mathematics and Computer Science, Ural Federal University, Lenina st. 51, Ekaterinburg 620083, Russia. vl.gusev@gmail.com, maslennikova.marina@gmail.com, elena.pribavkina@usu.ru Elena V. Pribavkina, Institute of Mathematics and Computer Science, Ural Federal University, Lenina st. 51, Ekaterinburg 620083, Russia. vl.gusev@gmail.com, maslennikova.marina@gmail.com, elena.pribavkina@usu.ru Journal Fundamenta Informaticae Online ISSN 1875-8681 Print ISSN 0169-2968 Journal Volume Volume 132 Journal Issue Volume 132, Number 1 / 2014