Fundamenta Informaticae - Volume 27, issue 1

Authors: Sopena, Eric

Article Type: Research Article

Abstract: Graph relabeling systems (GRS's) have been introduced as a suitable tool for coding and proving sequential or distributed algorithms on graphs or networks. These systems do not change the underlying structure of the graph on which they work, but only the labeling of its components (edges or vertices). Each relabeling step is fully determined by the knowledge of a fixed size subgraph, the relabeled occurrence. We introduce an extension of that model, the so-called expanding graph relabeling systems (e-GRS's), which allows the generation of sets of graphs by means of component relabeling. We study the generating power of these systems …and prove that they enable us to generate any recursively enumerable set of graphs. We first show how the “from left to right” natural orientation of a string-graph, that is a graph representation of a string, can be translated by means of vertex labels in such a way that any local transformation of the string can be simulated by a local relabeling of the string-graph vertices. Using this translation, we show that any phrase-structure string grammar can be simulated by an e-GRS. Finally, we provide a way of encoding graphs as strings and an e-GRS, called the decoder, which can convert any string representation of the encoding of a graph into the graph itself. Show more

DOI: 10.3233/FI-1996-27101

Citation: Fundamenta Informaticae, vol. 27, no. 1, pp. 1-25, 1996

Authors: La Torre, Salvatore | Napoli, Margherita | Parente, Domenico

Article Type: Research Article

Abstract: We study the parallel word substitution operation: in a text t, all non overlapping occurrences of a word ω are simultaneously substituted in each possible decomposition of t with respect to ω. We give necessary conditions on the reversibility of t under parallel word substitution.

DOI: 10.3233/FI-1996-27102

Citation: Fundamenta Informaticae, vol. 27, no. 1, pp. 27-36, 1996

Authors: Bergstra, J.A. | Ştefănescu, Gh.

Article Type: Research Article

Abstract: This paper proposes a framework for the integration of the algebra of communicating processes (ACP) and the algebra of flownomials (AF). Basically, this means to combine axiomatisations of parallel and looping operators. To this end a model of process graphs with multiple entries and exits is introduced. In this model the usual operations of both algebras are defined, e.g. alternative composition, sequential composition, feedback, parallel composition, left merge, communication merge, encapsulation, etc. The main results consist of correct and complete axiomatisations for process graphs modulo isomorphism and modulo bisimulation.

DOI: 10.3233/FI-1996-27103

Citation: Fundamenta Informaticae, vol. 27, no. 1, pp. 37-56, 1996

Authors: Liau, Churn-Jung

Article Type: Research Article

Abstract: In this paper, we would like to investigate the relationship between evidential structures (ES)—the basic qualitative structures of Dempster-Shafer theory, and the data table based knowledge representation systems(KRS) subject to rough set analysis. It is shown that an ES has a natural representation as a data table and from a given data table and two of its attributes, an ES can be extracted. We also show that some important operations on ES's can be realized in relational algebra. The results are then generalized to the fuzzy case. Consequently, we further clarify the connection between evidence theory and rough set theory.

DOI: 10.3233/FI-1996-27104

Citation: Fundamenta Informaticae, vol. 27, no. 1, pp. 57-76, 1996

Authors: Marcus, Leo

Article Type: Research Article

Abstract: We present an algorithm that takes a first-order sentence φ in full arithmetic with arrays (with quantification over numbers, and with numerical terms serving as array indices), and builds a test formula that can be used to determine which indices of φ's constituent arrays “really” occur. We call this concept syntactic dependence. We show how to use syntactic dependence as a test for semantic dependence, i.e., the true dependence of φ on the value of an array element. This is useful in truth-maintenance systems or symbolic execution systems, where a sentence may be true in one state but false in …the next. More specifically, if we are given an initial state, a sentence (such as φ above) that is true in the initial state, and a list of array elements that may be changing value during a state transition, the algorithm can be used to determine whether φ must remain true after the state transition. Show more

DOI: 10.3233/FI-1996-27105

Citation: Fundamenta Informaticae, vol. 27, no. 1, pp. 77-100, 1996