Fundamenta Informaticae - Volume 25, issue 3-4

Authors: Rozenberg, Grzegorz | Salomaa, Arto

Article Type: Other

DOI: 10.3233/FI-1996-253413

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

Authors: Berstel, J. | Boasson, L.

Article Type: Research Article

Abstract: The purpose of the paper is to present the implications of a new definition of context-free languages. The main interests of this approach are first to allow full formal proofs and second to enlight the crucial role of rational closures. The proposed formalism is based on a theorem of Wechler. It is very near to the “radical algebras” of Conway.

DOI: 10.3233/FI-1996-253401

Citation: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 217-239, 1996

Authors: Diekert, Volkert | Muscholl, Anca

Article Type: Research Article

DOI: 10.3233/FI-1996-253402

Citation: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 241-246, 1996

Authors: Gécseg, F. | Jürgensen, H.

Article Type: Research Article

Abstract: The notions of independence and dimension as introduced by Cohn for universal algebras are quite significantly different from the standard ones. This paper compares some of these notions. In particular, necessary and sufficient conditions for spanning and generating to coincide are derived. Moreover, the paper exhibits a new class of algebras which have bases and well-defined dimensions. This class extends that of v* -algebras and is incomparable with the class of v** -algebras.

DOI: 10.3233/FI-1996-253403

Citation: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 247-256, 1996

Authors: Honkala, Juha | Kuich, Werner

Article Type: Research Article

Abstract: We study ETOL power series introduced by Kuich. We show that the ETOL power series coincide with the linear extended Lindenmayerian series introduced by Honkala.

DOI: 10.3233/FI-1996-253404

Citation: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 257-270, 1996

Authors: Hromkovič, Juraj | Kari, Jarkko | Kari, Lila | Pardubská, Dana

Article Type: Research Article

Abstract: The lower bounds on communication complexity measures of language generation by Parallel Communicating Grammar Systems (PCGS) are investigated. The first result shows that there exists a language that can be generated by some dag-PCGS (PCGS with communication structures realizable by directed acyclic graphs) consisting of 3 grammars, but by no PCGS with tree communication structure. The second result shows that dag-PCGS have their communication complexity of language generation either constant or linear.

DOI: 10.3233/FI-1996-253405

Citation: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 271-284, 1996

Authors: Derencourt, D. | Karhumäki, J. | Latteux, M. | Terlutte, A.

Article Type: Research Article

Abstract: Weighted Finite Automata are automata with multiplicities used to compute real functions by reading infinite words. The aim of this paper is to study what kind of functions can be computed by level automata, a particular subclass of WFA. Several results concerning the continuity and the smoothness of these functions are shown. In particular, the only smooth functions that can be obtained are the polynomials. This enables to decide whether a function computed by a level automaton is smooth or not.

DOI: 10.3233/FI-1996-253406

Citation: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 285-293, 1996

Authors: Drewes, F. | Kreowski, H.-J.

Article Type: Research Article

Abstract: Collage grammars are based on hyperedge replacement in a geometric environment and provide context-free syntactic devices for the generation of picture languages. An intriguing question is which geometric properties of the generated pictures can be decided by inspecting the generating collage grammars. The results presented in this paper address the question in two respects. (1) The decidability results known for hyperedge replacement grammars generating graph languages, based on the notion of compatibility, can be carried over to collage grammars. Unfortunately, compatible properties seem rare in the geometric setting. In this paper three concrete ones are presented. (2) In some other …cases being only a minor extensions of situations for which compatibility is obtained, we can prove undecidability results. Show more

DOI: 10.3233/FI-1996-253407

Citation: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 295-325, 1996

Authors: Lange, Klaus-Jörn

Article Type: Research Article

Abstract: The following survey reviews some connections between formal languages and complexity theory. Families of formal languages are treated with complexity theoretical methods. In particular, the concept of unambiguity, common to both areas, is treated in detail. Some complexity theoretical aspects of operations on formal languages are indicated. This picture is completed by taking parallel models into account.

DOI: 10.3233/FI-1996-253408

Citation: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 327-352, 1996

Authors: Hoogeboom, Hendrik Jan | Pas, Paulienten

Article Type: Research Article

Abstract: A text can be defined as a word w together with a (second) linear order on its domain {1,..., |w|}. This second order may be used to define a hierarchical, tree-like, structure representing the text. The family of context-free sets of texts is investigated, i.e., sets of texts defined by context-free text grammars. In particular, those sets of texts are studied in the framework of universal algebra. This allows to compare the classical notions of equational and recognizable families in an algebra with context-free sets in the “algebra of texts”. Within this algebra the notion of equational sets coincides with …the context-free sets. A grammatical characterization of the family of recognizable sets is given as a subfamily of the context-free sets of texts. Show more

DOI: 10.3233/FI-1996-253409

Citation: Fundamenta Informaticae, vol. 25, no. 3-4, pp. 353-380, 1996

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