Fundamenta Informaticae - Volume 115, issue 1

Authors: Ciucci, Davide | Dennunzio, Alberto | Leporini, Roberto

Article Type: Other

DOI: 10.3233/FI-2012-636

Citation: Fundamenta Informaticae, vol. 115, no. 1, pp. v-vi, 2012

Authors: Beltrametti, Enrico | Dalla Chiara, Maria Luisa | Giuntini, Roberto | Leporini, Roberto | Sergioli, Giuseppe

Article Type: Research Article

Abstract: Quantum computation and quantum computational logics are intrinsically connected with some puzzling epistemic problems. In the framework of a quantum computational approach to epistemic logic we investigate the following question: is it possible to interpret the basic epistemic operations (having information, knowing) as special kinds of Hilbert-space operations? We show that non-trivial knowledge operations cannot be represented by unitary operators. We introduce the notions of strong epistemic quantum computational structure and of epistemic quantum computational structure, where knowledge operations are identified with special examples of quantum operations. This represents the basic tool for developing an epistemic quantum computational semantics, where …epistemic sentences (like “Alice knows that the spin-value in the x-direction is up”) are interpreted as quantum pieces of information that may be stored by quantum objects. Show more

Keywords: quantum computational logics, epistemic structures

DOI: 10.3233/FI-2012-637

Citation: Fundamenta Informaticae, vol. 115, no. 1, pp. 1-14, 2012

Authors: Buhagiar, David | Chetcuti, Emmanuel | Dvurečenskij, Anatolij

Article Type: Research Article

Abstract: In the Eighties G. Cattaneo contributed to Hilbert space quantum mechanics models using the family of splitting subspaces of an inner product space in order to find completeness criteria. In this paper we show how that theory was developed in the last 25 years into a rich theory which has a close connection to quantum information. G. Cattaneo also posed an open problem which was solved only this year.

DOI: 10.3233/FI-2012-638

Citation: Fundamenta Informaticae, vol. 115, no. 1, pp. 15-24, 2012

Authors: Greco, Salvatore | Matarazzo, Benedetto | Słowiński, Roman

Article Type: Research Article

Abstract: We introduce the bipolar complemented de Morgan Brouwer-Zadeh distributive lattice in order to give an algebraic model the to Dominance-based Rough Set Approach. We present also the concept of bipolar approximation space and we show how it can be induced from a bipolar quasi Brouwer-Zadeh lattice.

Keywords: Bipolar Brouwer-Zadeh Lattice, Dominance-based Rough Set Approach, Bipolar Approximation Space

DOI: 10.3233/FI-2012-639

Citation: Fundamenta Informaticae, vol. 115, no. 1, pp. 25-56, 2012

Authors: Ciucci, Davide

Article Type: Research Article

Abstract: An information table can change over time in several different ways: objects enter/exit the system, new attributes are considered, etc. As a consequence rough set instruments also change. At first, we recall a classification of dynamic increase of information with respect to three different factors: objects, attributes, values. Then, the corresponding changes in rough sets are discussed. Results about approximations, positive region and generalized decision are given and algorithms to update reducts and rules provided.

DOI: 10.3233/FI-2012-640

Citation: Fundamenta Informaticae, vol. 115, no. 1, pp. 57-74, 2012

Authors: Di Lena, Pietro | Margara, Luciano

Article Type: Research Article

Abstract: The attractor properties in Cellular Automata dynamical systems have been extensively investigated and well characterized. We consider here two attractor classification for Cellular Automata and we prove the computational undecidability of some questions related to such classifications.

Keywords: Cellular Automata, Attractors, Computational Undecidability

DOI: 10.3233/FI-2012-641

Citation: Fundamenta Informaticae, vol. 115, no. 1, pp. 75-85, 2012

Authors: Dennunzio, Alberto

Article Type: Research Article

Abstract: We enlighten the differences between one-dimensional and two-dimensional cellular automata by considering both the dynamical and decidability aspects. We also show a canonical representation theorem for the slicing constructions, a tool allowing to give the 2D version of important 1D CA notions as closing and positive expansivity and lift 1D results to the 2D settings.

Keywords: Cellular automata, symbolic dynamics, (un)decidability

DOI: 10.3233/FI-2012-642

Citation: Fundamenta Informaticae, vol. 115, no. 1, pp. 87-105, 2012

Authors: Formenti, Enrico | Goles, Eric | Martin, Bruno

Article Type: Research Article

Abstract: This paper investigates the avalanche problem AP for the Kadanoff sandpile model (KSPM). We prove that (a slight restriction of) AP is in NC1 in dimension one, leaving the general case open. Moreover, we prove that AP is P-complete in dimension two. The proof of this latter result is based on a reduction from the monotone circuit value problem by building logic gates and wires which work with an initial sand distribution in KSPM. These results are also related to the known prediction problem for sandpiles which is in NC1 for one-dimensional sandpiles and P-complete for dimension 3 …or higher. The computational complexity of the prediction problem remains open for the Bak's model of two-dimensional sandpiles. Show more

Keywords: Kadanoff Sandpile Model, Bak Sandpile Model, Sandpiles Models, Complexity, Discrete Dynamical Systems, Self-Organized Criticality (SOC)

DOI: 10.3233/FI-2012-643

Citation: Fundamenta Informaticae, vol. 115, no. 1, pp. 107-124, 2012

Authors: Bertoni, Alberto | Goldwurm, Massimiliano | Lin, Jianyi | Saccà, Francesco

Article Type: Research Article

Abstract: In this paper we study the complexity of some size constrained clustering problems with norm Lp . We obtain the following results: (i) A separation property for the constrained 2-clustering problem. This implies that the optimal solutions in the 1-dimensional case verify the so-called “String Property”; (ii) The NP-hardness of the constrained 2-clustering problem for every norm Lp (p > 1); (iii) A polynomial time algorithm for the constrained 2-clustering problem in dimension 1 for every norm Lp with integer p. We also give evidence that this result cannot be extended to norm Lp with rational non-integer …p; (iv) The NP-hardness of the constrained clustering problem in dimension 1 for every norm Lp (p ≥ 1). Show more

Keywords: clustering, size constraints, NP-hardness

DOI: 10.3233/FI-2012-644

Citation: Fundamenta Informaticae, vol. 115, no. 1, pp. 125-139, 2012