Fundamenta Informaticae - Volume 131, issue 3-4

Authors: Calude, Cristian S. | Gheorghe, Marian

Article Type: Other

DOI: 10.3233/FI-2014-1014

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. i-iv, 2014

Authors: Alexandru, Andrei | Ciobanu, Gabriel

Article Type: Research Article

Abstract: 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.

Keywords: Fraenkel-Mostowski set theory, finitely supported objects, nominal groups, homomorphisms

DOI: 10.3233/FI-2014-1015

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 279-298, 2014

Authors: Azimi, Sepinoud | Iancu, Bogdan | Petre, Ion

Article Type: Research Article

Abstract: 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. Show more

Keywords: Reaction systems, heat shock response, quantitative model, qualitative model, model comparison

DOI: 10.3233/FI-2014-1016

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 299-312, 2014

Authors: Banu-Demergian, Iulia Teodora | Stefanescu, Gheorghe

Article Type: Research Article

Abstract: 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. Show more

Keywords: parallel programming, interactive programming, regular expressions, regular algebra, Kleene theorem, network algebra, 2-dimensional languages, finite interactive systems, relational semantics, specification, verification, structured interactive programming

DOI: 10.3233/FI-2014-1017

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 313-336, 2014

Authors: Bottoni, Paolo | Labella, Anna | Mitrana, Victor

Article Type: Research Article

Abstract: 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.

Keywords: Rectangular picture, local picture language, recognizable picture language, evolutionary picture processor, network of evolutionary picture processors

DOI: 10.3233/FI-2014-1018

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 337-349, 2014

Authors: Cardelli, Luca | Mardare, Radu

Article Type: Research Article

Abstract: 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. Show more

Keywords: Markov processes, stochastic process algebras, structural operational semantics

DOI: 10.3233/FI-2014-1019

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 351-371, 2014

Authors: Ciobanu, Gabriel | Todoran, Eneia Nicolae

Article Type: Research Article

Abstract: 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.

Keywords: Metric semantics, continuations for concurrency, asynchronous communication

DOI: 10.3233/FI-2014-1020

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 373-388, 2014

Authors: Dima, Cătălin

Article Type: Research Article

Abstract: 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.

DOI: 10.3233/FI-2014-1021

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 389-407, 2014

Authors: Dinu, Liviu P. | Gramatovici, Radu | Manea, Florin

Article Type: Research Article

Abstract: 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. Show more

Keywords: Contextual Grammars, Syllabic Languages, Go-through Automata

DOI: 10.3233/FI-2014-1022

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 409-424, 2014

Authors: Duta, Nicolae

Article Type: Research Article

Abstract: 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. Show more

Keywords: Natural language understanding, language modeling, language prediction

DOI: 10.3233/FI-2014-1023

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 425-440, 2014