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

Authors: Grozea, Cristian | Popescu, Marius

Article Type: Research Article

Abstract: This note describes our experiments aiming to empirically test the ability of machine learning models to act as decision oracles for NP problems. Focusing on satisfiability testing problems, we have generated random 3-SAT instances and found out that the correct branch prediction accuracy reached levels in excess of 99%. The branching in a simple backtracking-based SAT solver has been reduced in more than 90% of the tested cases, and the average number of branching steps has reduced to between 1/5 and 1/3 of the one without the machine learning model. The percentage of SAT instances where the machine learned heuristic-enhanced …algorithm solved SAT in a single pass reached levels of 80-90%, depending on the set of features used. Show more

Keywords: ML, machine learning, satisfiability, SAT, NP, heuristics

DOI: 10.3233/FI-2014-1024

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 441-450, 2014

Authors: Krithivasan, Kamala | Păun, Gheorghe | Ramanujan, Ajeesh

Article Type: Research Article

Abstract: We introduce and briefly investigate P systems with controlled computations. First, P systems with label restricted transitions are considered (in each step, all rules used have either the same label, or, possibly, the empty label, λ), then P systems with the computations controlled by languages (as in context-free controlled grammars). The relationships between the families of sets of numbers computed by the various classes of controlled P systems are investigated, also comparing them with length sets of languages in Chomsky and Lindenmayer hierarchies (characterizations of the length sets of ET0L and of recursively enumerable languages are obtained in this framework). …A series of open problems and research topics are formulated. Show more

Keywords: Membrane computing, P system, control word, Chomsky language, Lindenmayer language

DOI: 10.3233/FI-2014-1025

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 451-464, 2014

Authors: Nicolescu, Radu | Gimel’farb, Georgy | Morris, John | Delmas, Patrice | Gong, Rui

Article Type: Research Article

Abstract: We propose a novel approach to justify and guide regularisation of an ill-posed one-dimensional global optimisation with multiple solutions using a massively parallel (P system) model of the solution space. Classical optimisation assumes a well-posed problem with a stable unique solution. Most of important practical problems are ill posed due to an unstable or non-unique global optimum and are regularised to get a unique best-suited solution. Whilst regularisation theory exists largely for unstable unique solutions, its recommendations are often routinely applied to inverse optical problems with essentially non-unique solutions, e.g. computer stereo vision or image segmentation, typically formulated in terms …of global energy minimisation. In these cases the recommended regularisation becomes purely heuristic and does not guarantee a unique solution. As a result, classical optimisation algorithms: dynamic programming (DP) and belief propagation (BP) – meet with difficulties. Our recent concurrent propagation (CP), leaning upon the P systems paradigm, extends DP and BP to always detect whether the problem is ill posed or not and store in the ill-posed case an entire space of solutions that yield the same global optimum. This suggests a radically new path to proper regularisation: select the best-suited unique solution by exploring statistical and structural features of this space. We propose a P systems based implementation of CP and set out as a case study an application of CP to the image matching problem in stereo vision. Show more

Keywords: concurrent propagation, ill-posed problems, regularisation, multiple solutions, stereo matching, P systems, membrane computing, parallel and distributed computing models, actor model

DOI: 10.3233/FI-2014-1026

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 465-483, 2014

Authors: Zimand, Marius

Article Type: Research Article

Abstract: We derive quantitative results regarding sets of n-bit strings that have different dependency or independency properties. Let C(x) be the Kolmogorov complexity of the string x. A string y has α dependency with a string x if C(y) − C(y | x) ≥ α. A set of strings {x1 , . . . , xt } is pairwise α-independent if for all i ≠ j, C(xi ) − C(xi | xj ) < α. A tuple of strings (x1 , . . . , xt ) is mutually α-independent if C(xπ(1) . . . xπ(t) ) > C(x1 …)+. . .+C(xt ) − α, for every permutation π of [t]. We show that: • For every n-bit string x with complexity C(x) ≥ α + 7 log n, the set of n-bit strings that have α dependency with x has size at least (1/poly(n))2n−α . In case α is computable from n and C(x) ≥ α + 12 log n, the size of the same set is at least (1/C)2n−α − poly(n)2α , for some positive constant C. • There exists a set of n-bit strings A of size poly(n)2α such that any n-bit string has α-dependency with some string in A. • If the set of n-bit strings {x1 , . . . , xt } is pairwise α-independent, then t ≤ poly(n)2α . This bound is tight within a poly(n) factor, because, for every n, there exists a set of n-bit strings {x1 , . . . , xt } that is pairwise α-dependent with t = (1/poly(n)) · 2α (for all α ≥ 5 log n). • If the tuple of n-bit strings (x1 , . . . , xt ) is mutually α-independent, then t ≤ poly(n)2α (for all α ≥ 7 log n + 6). Show more

DOI: 10.3233/FI-2014-1027

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 485-497, 2014

Article Type: Other

Citation: Fundamenta Informaticae, vol. 131, no. 3-4, pp. 499-500, 2014