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