Advertisement

Marcus Contextual Languages and their Cut-and-Paste Properties

  • Rodica Ceterchi
Conference paper
  • 570 Downloads
Part of the Lecture Notes in Computer Science book series (LNCS, volume 1424)

Abstract

We explore the relationship between Marcus contextual languages and CP-languages. We prove that external and internal contextual languages without choice are 2CP- and 3CP-languages. We extend these results to contextual languages with choice, by appropriately defining a concept of selective CP-language.

Keywords

Formal Language Choice Function Partial Function Simple Type Derivation Relation 
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. 1.
    R. Ceterchi, Cut-and-Paste Languages (submitted)Google Scholar
  2. 2.
    S. Istrail, A fixed-point approach to contextual languages, Rev. Roum. Math. Pures Appl., 25 (1980), 861–869zbMATHMathSciNetGoogle Scholar
  3. 3.
    S. Marcus, Contextual grammars, Rev. Roum. Math. Pures Appl., 14 (1969), 1525–1534zbMATHGoogle Scholar
  4. 4.
    S. Marcus, Contextual grammars and natural languages, chapter 5 in vol.2 of A. Salomaa (eds.), The Handbook of Formal Languages, 3 volumes, Springer-Verlag, Berlin, Heidelberg, 1997 [10]}, 215–235Google Scholar
  5. 5.
    A. Mateescu, Marcus contextual grammars with shuffled contexts, in Mathematical Aspects of Natural and Formal Languages, (Gh. Paun, ed.), World Sci. Publ., Singapore, 1994, 275–284Google Scholar
  6. 6.
    Gh. Paun, X. M. Nguyen, On the inner contextual grammars, Rev. Roum. Math. Pures Appl., 25(1980), 641–651zbMATHGoogle Scholar
  7. 7.
    Gh. Paun, Contextual Grammars, The Publ. House of the Romanian Academy, Bucharest, 1982 (in Romanian; 144 pages)zbMATHGoogle Scholar
  8. 8.
    Gh. Paun, Marcus Contextual Grammars, Kluwer Academic Publishers, Dordrecht, Boston, london, 1997zbMATHGoogle Scholar
  9. 9.
    Gh. Paun, G. Rozenberg, A. Salomaa, DNA Computing. New Computing Paradigms, Springer-Verlag, Berlin, Heidelberg, 1998zbMATHGoogle Scholar
  10. 10.
    G. Rozenberg, A. Salomaa (eds.), The Handbook of Formal Languages, 3 volumes, Springer-Verlag, Berlin, Heidelberg, 1997Google Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 1998

Authors and Affiliations

  • Rodica Ceterchi
    • 1
  1. 1.Faculty of MathematicsBucharest UniversityBucureştiRomania

Personalised recommendations