Fundamenta Informaticae - Volume 171, issue 1-4

Authors: Dennunzio, Alberto | Păun, Gheorghe | Rozenberg, Grzegorz | Zandron, Claudio

Article Type: Other

DOI: 10.3233/FI-2020-1868

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. v-vi, 2020

Authors: Anselmo, Marcella | Giammarresi, Dora | Madonia, Maria

Article Type: Research Article

Abstract: We introduce the two-dimensional rational automata (RA) to recognize languages of pictures, as an extension of the finite automata for strings. A RA processes a picture column by column changing its state. The states are columns of symbols, too. The transition function is realized by a transducer. We prove that RA recognize the family REC of languages recognized by tiling systems. Moreover, RA provide a uniform setting for a lot of important notions, techniques and results presented in the last decades for recognizable two-dimensional languages. The model is also very flexible. In fact, there can be imposed restrictions …or added features to easily interesting new classes and examples or to capture known families of languages. Show more

DOI: 10.3233/FI-2020-1869

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 1-17, 2020

Authors: Bandini, Stefania | Crociani, Luca | Gorrini, Andrea | Nishinari, Katsuhiro | Vizzari, Giuseppe

Article Type: Research Article

Abstract: Models for the automated analysis and simulation of the complex phenomena observable in built environment crowded by pedestrians have been studied for over thirty years. Nonetheless, one of the commonly agreed upon rules guiding regulation of distance among pedestrian, i.e. proxemics, was defined and discussed in static settings, whereas scenarios of interest generally deal with individual and collective movements in crowds. The present paper presents a systemic perspective on the research aimed at defining a dynamic form of proxemics. The paper firstly reports the results of an experiment focused on proxemics and pedestrians personal space, as the hidden dimension of …human spatial behavior in crowded environments. We propose a representation of personal space through discrete potentials and an innovative crowding estimation method (i.e. Cumulative Mean Crowding ), going beyond simple perceived density evaluation. The experimental setting is introduced and applied to appraise the potential impact of this novel pedestrian perception mechanism on innovative simulation models. Show more

Keywords: Modeling and Simulations, Cellular Automata, Pedestrian Crowds, Crowding

DOI: 10.3233/FI-2020-1870

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 19-38, 2020

Authors: Bernardinello, Luca | Ferigato, Carlo | Pomello, Lucia

Article Type: Research Article

Abstract: An orthogonality space is a set endowed with a symmetric and irreflexive binary relation (an orthogonality relation). In a partially ordered set modelling a concurrent process, two such binary relations can be defined: a causal dependence relation and a concurrency relation, and two distinct orthogonality spaces are consequently obtained. When the condition of N-density holds on both these orthogonality spaces, we study the orthomodular poset formed by closed sets defined according to Dacey. We show that the condition originally imposed by Dacey on the orthogonality spaces for obtaining an orthomodular poset from his closed sets is in fact …equivalent to N-density. The requirement of N-density was as well fundamental in a previous work on orthogonality spaces with the concurrency relation. Starting from a partially ordered set modelling a concurrent process, we obtain dual results for orthogonality spaces with the causal dependence relation in respect to orthogonality spaces with the concurrency relation. Show more

DOI: 10.3233/FI-2020-1871

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 39-56, 2020

Authors: Besozzi, Daniela | Manzoni, Luca | Nobile, Marco S. | Spolaor, Simone | Castelli, Mauro | Vanneschi, Leonardo | Cazzaniga, Paolo | Ruberto, Stefano | Rundo, Leonardo | Tangherloni, Andrea

Article Type: Research Article

Abstract: Computational Intelligence (CI) is a computer science discipline encompassing the theory, design, development and application of biologically and linguistically derived computational paradigms. Traditionally, the main elements of CI are Evolutionary Computation, Swarm Intelligence, Fuzzy Logic, and Neural Networks. CI aims at proposing new algorithms able to solve complex computational problems by taking inspiration from natural phenomena. In an intriguing turn of events, these nature-inspired methods have been widely adopted to investigate a plethora of problems related to nature itself. In this paper we present a variety of CI methods applied to three problems in life sciences, highlighting their effectiveness: we …describe how protein folding can be faced by exploiting Genetic Programming, the inference of haplotypes can be tackled using Genetic Algorithms, and the estimation of biochemical kinetic parameters can be performed by means of Swarm Intelligence. We show that CI methods can generate very high quality solutions, providing a sound methodology to solve complex optimization problems in life sciences. Show more

Keywords: Computational Intelligence, Evolutionary Computation, Swarm Intelligence, Genetic Programming, Genetic Algorithm, Particle Swarm Optimization, Protein Folding, Haplotype Assembly, Parameter Estimation

DOI: 10.3233/FI-2020-1872

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 57-80, 2020

Authors: Bonizzoni, Paola | De Felice, Clelia | Zaccagnino, Rocco | Zizza, Rosalba

Article Type: Research Article

Abstract: Circular splicing systems are a mathematical model, inspired by a recombinant behaviour of circular DNA. They are defined by a finite alphabet A , an initial set I of circular words, and a set R of rules. A circular splicing language is a language generated by a circular splicing system. An open problem is to characterize regular circular splicing languages and the corresponding circular splicing systems. In this framework an important role is played by unavoidable sets . These sets have been considered in several contexts. In particular, Ehrenfeucht, Haussler and Rozenberg (1983) proved the following …generalization of a famous Higman’s theorem: the quasi-order induced by insertions of words from a fixed finite set is a well-quasi-order if and only if the finite set is unavoidable . In this paper we survey the known relations between unavoidable sets and regular circular languages. Motivated by these connections we give an alternative and simpler proof of the Ehrenfeucht, Haussler and Rozenberg result. Our proof is strongly based on a known characterization of unavoidable sets in terms of graphs associated with them. Show more

Keywords: Formal languages, Regular languages, Unavoidable sets, Circular splicing languages

DOI: 10.3233/FI-2020-1873

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 81-95, 2020

Authors: Castiglione, Giuseppa | Mantaci, Sabrina | Restivo, Antonio

Article Type: Research Article

Abstract: In this paper we investigate similarity measures based on minimal absent words, introduced by Chairungsee and Crochemore in [1]. They make use of a length-weighted index on a sample set corresponding to the symmetric difference M (x )ΔM (y ) of the minimal absent words M (x ) and M (y ) of two sequences x and y , respectively. We first propose a variant of this measure by choosing as a sample set a proper subset 𝒟(x , y ) of M (x )ΔM (y ), which appears to be more appropriate for distinguishing x and y …. From the algebraic point of view, we prove that 𝒟(x , y ) is the base of the ideal generated by M (x )ΔM (y ). We then remark that such measures are able to recognize whether the sequences x and y share a common structure, but they are not able to detect the difference on the number of occurrences of such a structure in the two sequences. In order to take into account such a multiplicity, we introduce the notion of multifactor, and define a new measure that uses both absent words and multifactors. Surprisingly, we prove that this similarity measure coincides with a distance on sequences introduced by Ehrenfeucht and Haussler in [2], in the context of block-moves strategies. In this way, our result creates a non trivial bridge between similarity measures based on absent words and those based on the block-moves approach. Show more

Keywords: Minimal absent words, similarity measures, sequence comparison

DOI: 10.3233/FI-2020-1874

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 97-112, 2020

Authors: Cruz, Daniel A. | Ferrari, Margherita Maria | Jonoska, Nataša | Nabergall, Lukas | Saito, Masahico

Article Type: Research Article

Abstract: A double occurrence word (DOW) is a word in which every symbol appears exactly twice; two DOWs are equivalent if one is a symbol-to-symbol image of the other. We consider the so called repeat pattern (αα ) and the return pattern (αα R ), with gaps allowed between the α ’s. These patterns generalize square and palindromic factors of DOWs, respectively. We introduce a notion of inserting repeat/return words into DOWs and study how two distinct insertions into the same word can produce equivalent DOWs. Given a DOW w , we characterize the structure of w which allows …two distinct insertions to yield equivalent DOWs. This characterization depends on the locations of the insertions and on the length of the inserted repeat/return words and implies that when one inserted word is a repeat word and the other is a return word, then both words must be trivial (i.e., have only one symbol). The characterization also introduces a method to generate families of words recursively. Show more

DOI: 10.3233/FI-2020-1875

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 113-132, 2020

Authors: Csuhaj-Varjú, Erzsébet | Vaszil, György

Article Type: Research Article

Abstract: P automata are accepting computing devices combining features of classical automata and membrane systems. In this paper we introduce P n -stack-automata, a restricted class of P automata that mimics the behaviour of n -stack automata. We show that for n = 1 these constructs describe the context-free language class and for n = 3 the class of quasi-realtime languages.

DOI: 10.3233/FI-2020-1876

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 133-149, 2020

Authors: Enaganti, Srujan Kumar | Kari, Lila | Ng, Timothy | Wang, Zihao

Article Type: Research Article

Abstract: In this paper we define and investigate a binary word operation that formalizes an experimentally observed outcome of DNA computations, performed to generate a small gene library, and implemented using a DNA recombination technique called Cross-pairing Polymerase Chain Reaction (XPCR). The word blending between two words αwγ 1 and γ 2 wβ that share a non-empty overlap w , results in αwβ . Interestingly, this phenomenon has been observed independently in linguistics, under the name “blend word” or “portmanteau”, and is responsible for the creation of words in the English language such as smog (smo ke + …fog ), labradoodle (labrador + poodle ), and Brangelina (Bra d + Angelina ). Technically, word blending is related to the binary word operation Latin product, the crossover operation, and simple splicing. We study closure properties of the families in the Chomsky hierarchy under word blending, language equations involving this operation, and its descriptional state complexity when applied to regular languages. We also define iterated word blending and show that, for a given alphabet, there are finitely many languages that can be obtained from an initial language by iterated word blending. Show more

DOI: 10.3233/FI-2020-1877

Citation: Fundamenta Informaticae, vol. 171, no. 1-4, pp. 151-173, 2020