Fundamenta Informaticae - Volume 144, issue 2

Authors: Bottoni, Paolo | Guerra, Esther | de Lara, Juan

Article Type: Research Article

Abstract: Model-based development relies on models in different phases for different purposes, with modelling patterns being used to document and gather knowledge about good practices in specific domains, to analyse the quality of existing designs, and to guide the construction and refactoring of models. Providing a formal basis for the use of patterns would also support their integration with existing approaches to model transformation. To this end, we turn to the commonly used, in this context, machinery of graph transformations and provide an algebraic-categorical formalization of modelling patterns, which can express variability and required/forbidden application contexts. This allows the definition of …transformation rules having patterns in left and right-hand sides, which can be used to express refactorings towards patterns, change the use of one pattern by a different one, or switch between pattern variants. A key element in our proposal is the use of operations to abstract models into patterns, so that they can be manipulated by pattern rules, thus leading to a rewriting mechanism for classes of graphs described by patterns and not just individual graphs. The proposal is illustrated with examples in object-oriented software design patterns and enterprise architecture patterns, but can be applied to any other domain where patterns are used for modelling. Show more

Keywords: Model-based development, Modelling patterns, Graphs, Trees, Category theory, Graph transformation, Refactorings, Pattern variants

DOI: 10.3233/FI-2016-1325

Citation: Fundamenta Informaticae, vol. 144, no. 2, pp. 109-160, 2016

Authors: Eom, Hae-Sung | Han, Yo-Sub | Jirásková, Galina

Article Type: Research Article

Abstract: We consider the state complexity of basic operations on non-returning regular languages. For a non-returning minimal DFA, the start state does not have any in-transitions. We establish the precise state complexity of four Boolean operations (union, intersection, difference, symmetric difference), catenation, reverse, and Kleene-star for non-returning regular languages. Our results are usually smaller than the state complexities for general regular languages and larger than the state complexities for suffix-free regular languages. In the case of catenation and reversal, we define witness languages over a ternary alphabet. Then we provide lower bounds for a binary alphabet. For every operation, we also …study the unary case. Show more

Keywords: Finite automata, non-returning regular languages, basic operations, state complexity

DOI: 10.3233/FI-2016-1326

Citation: Fundamenta Informaticae, vol. 144, no. 2, pp. 161-182, 2016

Authors: Radzikowska, Anna Maria

Article Type: Research Article

Abstract: In this paper we present relational representation theorems for lattice-based modal algebras and their axiomatic extensions taking into account well-known schemas of modal logics. The underlying algebraic structures are bounded, not necessarily distributive lattices. Our approach is based on the Urquhart’s result for non-distributive lattices and Allwein and Dunn developments for algebras of liner logics.

Keywords: Representation theorems, Modal algebras, Algebraic semantics, Kripke-style semantics, Duality theory

DOI: 10.3233/FI-2016-1327

Citation: Fundamenta Informaticae, vol. 144, no. 2, pp. 183-203, 2016

Authors: Wu, Tingfang | Zhang, Zhiqiang | Păun, Gheorghe | Pan, Linqiang

Article Type: Research Article

Abstract: A control strategy on the computations in a one-catalyst P system is provided: the rules are assumed “colored” and in each step only rules of the same “color” are used. Such control leads to Turing universality for one-catalyst P systems with one membrane. Turing universality is also reached for purely catalytic P systems with two catalysts, and for purely catalytic P systems with only one catalyst and cooperating rules working in the so-called terminal mode.

Keywords: Bio-inspired computing, Membrane computing, Catalytic P system, Catalyst, Universality

DOI: 10.3233/FI-2016-1328

Citation: Fundamenta Informaticae, vol. 144, no. 2, pp. 205-212, 2016