Fundamenta Informaticae - Volume 25, issue 3-4

Authors: P$\check{A}$un, Gheorghe | Rozenberg, Grzegorz | Salomaa, Arto

Article Type: Research Article

Abstract: Continuing the work begun in [14], we consider contextual grammars (as introduced in [6] with linguistic motivation) with parallel derivations, in which the whole current string participates to a derivation step in the sense that it is splitted into substrings to which contexts are adjoined in a parallel manner. The generative power of such grammars is investigated, when the parallelism is total or partial, and when the selection of contexts is limited to strings in sets of a given type (finite, regular etc.) Then we consider the languages consisting of strings which cannot be further derived (we call them blocking …languages). Some open problems are also formulated. Show more

DOI: 10.3233/FI-1996-253410

Citation: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 381-397, 1996

Authors: Giammarresi, Dora | Restivo, Antonio

Article Type: Research Article

Abstract: The purpose of this paper is to investigate about a new notion of finite state recognizability for two-dimensional (picture) languages. This notion takes as starting point the characterization of one-dimensional recognizable languages in terms of local languages and projections. Such notion can be extended in a natural way to the two-dimensional case. We first introduce a notion of local picture language and then we define,a recognizable picture language as a projection of a local picture language. The family of recognizable picture languages is denoted by REC. We study some combinatorial and language-theoretic properties of family REC. In particular we prove …some closure properties with respect to different kinds of operations. From this, we derive that some natural families of two-dimensional languages (finite languages, regular languages, locally testable languages) are recognizable. Further we give some necessary conditions for recognizability which provides tools to show that certain languages are not recognizable. Although REC shares several properties of recognizable string languages, however, differently from the case of words, we prove here that REC is not closed under complementation and that the emptyness problem is undecidable for this family of languages. Finally, we report some characterizations of family REC by means of machine-based models and logic-based formalisms. Show more

DOI: 10.3233/FI-1996-253411

Citation: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 399-422, 1996

Authors: Guo, L. | Salomaa, K. | Yu, S.

Article Type: Research Article

Abstract: New constructs for synchronization termed synchronization expressions (SEs) have been developed as high-level language constructs for parallel programming languages [8, 9]. Statements that are constrained by certain synchronization requirements are tagged, and synchronization requests are specified as expressions of statement tags. In this paper, we introduce a new family of languages named synchronization languages which we use to give a precise semantic description for SEs. Under this description, relations such as equivalence and inclusion between SEs can be easily understood and tested. In practice, it also provides us with a systematic way for the implementation as well as the simplification …of SEs in parallel programming languages. We show that each synchronization language is closed under the following rewriting rules: (1) as bs → bs as , (2) at bt → bt at , (3) as bt → bt as , (4) at as bt bs → bt bs at as and also h(at as bt bs ) → h(bt bs at as ) for any morphism h that satisfies certain conditions which will be specified in the paper. We conjecture that closure under the above rewriting rules is a sufficient condition for a regular st-language to be a synchronization language. Several other properties of synchronization languages are also studied. Show more

DOI: 10.3233/FI-1996-253412

Citation: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 423-436, 1996