Fundamenta Informaticae - Volume 73, issue 1-2

Authors: Paz, Azaria

Article Type: Research Article

Abstract: The relationship between graphoid independency relations (defined in the text) and such relations induced by Probabilistic Distributions (PD) with binary random variables is investigated. It is shown that there are axioms that are sound for a subset of PD-induced relations with binary variables and are independent of the Graphoid axioms (cannot be logically derived from those axioms).

Keywords: Graphoids, probabilistic distributions, independency relations

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 229-236, 2006

Authors: Santean, Nicolae | Yu, Sheng

Article Type: Research Article

Abstract: Bimachines are important conceptual tools used for the characterization of rational word functions (realized by single-valued transducers). Despite the attention received in the past, these sequential machines are far from being exhaustively studied. A natural question which has not been addressed so far is what family of transductions are realized by bimachines that operate nondeterministically. We show that these machines characterize input-unambiguous (IU) rational transductions, i.e., those transductions that can be written …as a composition of rational functions and finite substitutions. Two more families of rational transductions are defined and related in a natural way to IU transductions: input-deterministic transductions and rational transductions with finite codomain (FC). We have shown that FC transductions are recognizable and that they can be expressed as finite union of subsequential functions. Moreover, they can be realized by nondeterministic bimachines. Finally, we have defined the so called restricted nondeterministic bimachines and shown that, surprisingly, they are more powerful than nondeterministic bimachines: they characterize exactly the family of finitely ambiguous rational transductions. Show more

Keywords: Finite transducer, unambiguous automaton, nondeterministic bimachine, rational function, finite substitution

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 237-264, 2006

Authors: Şerbănuţă, Virgil Nicolae | Şerbănuţă, Traian Florin

Article Type: Research Article

Abstract: We deal with the notion of M-unambiguity [5] in connection with the Parikh matrix mapping introduced by Mateescu and others in [7]. M-unambiguity is studied both in terms of words and matrices and several sufficient criteria for M-unambiguity are provided in both cases, nontrivially generalizing the criteria based on the γ-property introduced by Salomaa in [15]. Also, the notion of M-unambiguity with respect to a word is defined in connection with the extended Parikh matrix morphism …[16] and some of the M-unambiguity criteria are lifted from the classical setting to the extended one. This paper is a revised and extended version of [17]. Show more

Keywords: Subword, scattered subword, Parikh matrix, ambiguity

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 265-283, 2006

Authors: Stefanescu, Gheorghe

Article Type: Research Article

Abstract: We present a model and a core programming language appropriate for modeling and programming interactive computing systems. The model consists of rv-systems (interactive systems with registers and voices); it includes register machines, is space-time invariant, is compositional, may describe computations extending in both time and space, and is applicable to open, interactive systems. To achieve modularity in space the model uses voices (a voice is the time dual of a register) – they provide a high …level organization of temporal data and are used to describe interaction interfaces of processes. The programming language uses novel techniques for syntax and semantics to support computation in space paradigm. We describe rv-programs and base their syntax and operational semantics on FIS-es (finite interactive systems) and their grid languages (a FIS is a kind of 2-dimensional automaton specifying both control and interaction used in rv-programs). We also present specification techniques for rv-systems, using relations between input registers and voices and their output counterparts. The paper includes simple specifications for an OO-system and for an interactive game. Show more

Keywords: Interactive systems, programming languages, syntax, semantics, temporal specifications, registers, voices, object-oriented systems, finite interactive systems, rv-systems, rv-programs, grids, space-time duality

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 285-305, 2006

Authors: Vaida, Dragoş

Article Type: Research Article

Abstract: This note begins a study of some elementary properties related to the order structures applied in the algebraic approach to processes semantics. The support examples come from the partially additive semantics developed by Steenstrup (1985) and Manes and Arbib (1986) and from process algebra of Baeten and Weijland (1990). The main sources for the algebraic theory are F.A. Smith (1966) and Golan (1999). We show that different properties can be extended to partially additive distributive algebras …more general than sum-ordered partial semirings. One establishes that the support examples constitute multilattices, in the sense of Benado (1955). By the examples, the ordering considered, and the references, this preliminary study is related to Rudeanu et al. (2004) and to the algebraic approach to languages due to Mateescu, e.g., (1996), (1989), (1994). Show more

Keywords: Partial additive semantics, process algebra, semirings

Citation: Fundamenta Informaticae, vol. 73, no. 1-2, pp. 307-319, 2006