Fundamenta Informaticae - Volume 154, issue 1-4

Authors: Păun, Gheorghe | Rozenberg, Grzegorz | Salomaa, Arto

Article Type: Other

DOI: 10.3233/FI-2017-1547

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. vii-vii, 2017

Authors: Badouel, Eric | Schlachter, Uli

Article Type: Research Article

Abstract: Process discovery aims at constructing a model from a set of observations given by execution traces (a log). Petri nets are a preferred target model in that they produce a compact description of the system by exhibiting its concurrency. This article presents a process discovery algorithm using Petri net synthesis, based on the notion of region introduced by A. Ehrenfeucht and G. Rozenberg and using techniques from linear algebra. The algorithm proceeds in three successive phases which make it possible to find a compromise between the ability to infer behaviours of the system from the set of observations while ensuring …a parsimonious model, in terms of fitness, precision and simplicity. All used algorithms are incremental which means that one can modify the produced model when new observations are reported without reconstructing the model from scratch. Show more

Keywords: Region theory, Petri net synthesis, process discovery

DOI: 10.3233/FI-2017-1548

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 1-13, 2017

Authors: Barash, Mikhail | Petre, Ion

Article Type: Research Article

Abstract: Constructing large biomodels de-novo is a computationally expensive process, requiring large sets of high-quality data. An alternative approach is to construct them from smaller existing models through various operations such as union, intersection, difference, and refinement. We introduce in this paper a foundational framework for biomodel construction capturing these operations, and we discuss some of their properties.

Keywords: Biomodeling, model refinement, model union, model intersection, model difference, model complement

DOI: 10.3233/FI-2017-1549

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 15-24, 2017

Authors: Bernardinello, Luca | Ferigato, Carlo | Pomello, Lucia | Puerto Aubel, Adrián

Article Type: Research Article

Abstract: The set of elementary regions of a transition system, ordered by set inclusion, forms an orthomodular poset, also referred to as quantum logic, which is regular and rich. Starting from an abstract regular and rich quantum logic, one can construct an elementary transition system such that the orginal logic embeds into its set of regions, and which is saturated of transitions. We study the problem of selecting subsets of transitions on the same set of states, which generate the same set of regions.

DOI: 10.3233/FI-2017-1550

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 25-36, 2017

Authors: Bojańczyk, Mikołaj

Article Type: Research Article

Abstract: The following problem is shown undecidable: given regular languages L , K of finite trees, decide if there exists a deterministic tree-walking automaton which accepts all trees in L and rejects all trees in K . The proof uses a technique of Kopczyński from [1].

DOI: 10.3233/FI-2017-1551

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 37-46, 2017

Authors: Bonizzoni, Paola | Carrieri, Anna Paola | Della Vedova, Gianluca | Rizzi, Raffaella | Trucco, Gabriella

Article Type: Research Article

Abstract: The perfect phylogeny is a widely used model in phylogenetics, since it provides an effective representation of evolution of binary characters in several contexts, such as for example in haplotype inference. The model, which is conceptually the simplest among those actually used, is based on the infinite sites assumption, that is no character can mutate more than once in the whole tree. Since a large number of biological phenomena cannot be modeled by the perfect phylogeny, it becomes important to find generalizations that retain the computational tractability of the original model, but are more flexible in modeling biological data when …the infinite site assumption is violated, e.g. because of back mutations. In this paper, we introduce a new model—called species-driven persistent phylogeny—and we study the relations between three different formulations: perfect phylogeny, persistent phylogeny, galled trees, and species-driven persistent phylogeny. The species-driven persistent phylogeny model is intermediate between the perfect and the persistent phylogeny, since a perfect phylogeny allows no back mutations and a persistent phylogeny allows each character to back mutate only once. We describe an algorithm to compute a species-driven persistent phylogeny and we prove that every matrix admitting a galled-tree also admits a species-driven persistent phylogeny. Show more

Keywords: perfect phylogeny, persistent perfect phylogeny, galled-tree

DOI: 10.3233/FI-2017-1552

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 47-63, 2017

Authors: Cassaigne, Julien | Karhumäki, Juhani | Puzynina, Svetlana | Whiteland, Markus A.

Article Type: Research Article

Abstract: Two words u and v are said to be k -abelian equivalent if, for each word x of length at most k , the number of occurrences of x as a factor of u is the same as for v . We study some combinatorial properties of k -abelian equivalence classes. Our starting point is a characterization of k -abelian equivalence by rewriting, so-called k -switching. Using this characterization we show that, over any fixed alphabet, the language of lexicographically least representatives of k -abelian equivalence classes is a regular language. From this we infer …that the sequence of the numbers of equivalence classes is ℕ-rational. Furthermore, we show that the above sequence is asymptotically equal to a certain polynomial depending on k and the alphabet size. Show more

Keywords: k-abelian equivalence, Regular languages, Rational sequences

DOI: 10.3233/FI-2017-1553

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 65-94, 2017

Authors: Dutta, Soma | Jankowski, Andrzej | Skowron, Andrzej

Article Type: Research Article

Abstract: We present an extension of logical structures, called interactive logical structures, for reasoning about interactive computations performed by Intelligent Systems or Complex Adaptive Systems. Reasoning based on such structures is called adaptive judgment and it goes beyond deduction, induction, and abduction. An extension of logical structures, based on complex granules, couples the abstract world and the physical world of an agent’s environment, and transmits the features of interactions of physical objects realized in the physical world to the abstract world. This allows us to consider the problems of perception and action.

Keywords: complex granule, granular computing, information granule, interaction, (control of) interactive computations, (closed, open) logical structure, physical object, rough set

DOI: 10.3233/FI-2017-1554

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 95-108, 2017

Authors: Gabow, Harold N.

Article Type: Research Article

Abstract: Several papers have achieved time O n m for cardinality matching, starting from first principles. This results in a long derivation. We simplify the task by employing well-known concepts for maximum weight matching. We use Edmonds’ algorithm to derive the structure of shortest augmenting paths. We extend this to a complete algorithm for maximum cardinality matching in time O n m .

DOI: 10.3233/FI-2017-1555

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 109-130, 2017

Authors: Genova, Daniela | Hoogeboom, Hendrik Jan

Article Type: Research Article

Abstract: We investigate regular languages in the context of the forbidding-enforcing systems introduced by Ehrenfeucht and Rozenberg in the variant where one fe-system defines a single language. In general, these systems may have infinite sets of rules, allowing one to define arbitrary languages. On the other hand when restricted to finite sets, one obtains a strict subclass of the regular languages, between the strictly locally testable and locally testable languages. We further investigate classes of enforcing systems that characterize the regular languages. These systems have infinite sets of enforcers, but can be defined using regular languages (finite state automata).

Keywords: forbidding-enforcing systems, regular languages, (strictly) locally testable, natural computing, biomolecular computing

DOI: 10.3233/FI-2017-1556

Citation: Fundamenta Informaticae, vol. 154, no. 1-4, pp. 131-144, 2017