Quelques proprietes des langages a un Compteur | SpringerLink
Skip to main content
Springer Nature Link
Log in

Quelques proprietes des langages a un Compteur

  • Conference paper
  • First Online:
Theoretical Computer Science

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 104))

Abstract

We study restricted one counter languages, that is, languages belonging to Rocl, the full trio generated by D1′*, the restricted Dyck language over one pair of parentheses. We show that every generator of Rocl is a bifaithfull one and that there exists a one counter language which dominates the other ones by length preserving rational transduction. Then, we establish that the pumping lemma for linear languages is almost true for restricted one counter languages. At last, we prove that Rocl contains no non-rational AFL and, if Rocl is included in the smallest full AFL containing a full semi-AFL L, then Rocl is included in L. Moreover, if Rocl is included in the smallest full AFL closed under substitution containing a context-free full trio L, then Rocl is included in L.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. J.M. AUTEBERT, “Non-principalité du cylindre des langages à compteur”, Math. Systems Theory 11 (1977), 157–167.

    Article  Google Scholar 

  2. J. BEAUQUIER, “Contribution à l'étude de la complexité structurelle des langages algébriques”, Thèse Sc. Math., Paris, 1977.

    Google Scholar 

  3. J. BEAUQUIER, “Indépendance of linear and one-counter generators”, Fundamental of computation theory, Akademie-Verlag, Berlin, 1979, 45–51.

    Google Scholar 

  4. J. BERSTEL, “Transductions and context-free languages”, Teubner Verlag 1979.

    Google Scholar 

  5. J. BERSTEL et L. BOASSON, “Une suite décroissante de cônes rationnels”, in Automata Languages and Programming, Loeckx (Ed.), Lecture Notes in Computer Science 14 (1974), 383–397.

    Google Scholar 

  6. L. BOASSON, “Two iteration theorems for some families of languages”, J. of Comput. and Syst. Sciences 7 (1973), 583–596.

    Google Scholar 

  7. L. BOASSON et M. NIVAT, “Sur diverses familles de languages fermées par transductions rationnelles”, Acta Informatica 2 (1973), 180–188.

    Google Scholar 

  8. R. BOOK, S. GREIBACH et C. WRATHALL, “Reset Machines”, J. of Comput. and Syst. Sciences 19 (1979), 256–276.

    Article  Google Scholar 

  9. R. BOOK et M. NIVAT, “Linear languages and the intersection closures of classes of languages”, SIAM J. Comput. 7 (1978), 167–177.

    Article  Google Scholar 

  10. S. EILENBERG, “Automata languages and machines”, vol. A, Academic Press, New York, 1974.

    Google Scholar 

  11. S. GINSBURG, J. GOLDSTINE et S. GREIBACH, “Uniformly erasable AFL”, J. of Comput. and Syst. Sciences 10 (1975), 165–182.

    Google Scholar 

  12. S. GINSBURG, J. GOLDSTINE et S. GREIBACH, “Some uniformly erasable families of languages”, Theoretical Computer Science 2 (1976), 29–44.

    Article  Google Scholar 

  13. S. GREIBACH, “An infinite hierarchy of context-free languages”, J. Assoc. Comput. Mach. 16 (1969), 91–106.

    Google Scholar 

  14. S. GREIBACH, “The hardest context-free language”, SIAM J. Comput. 2 (1973), 304–310.

    Article  Google Scholar 

  15. S. GREIBACH, “One counter languages and the IRS condition”, J. of Comput. and Syst. Sciences 10 (1975), 237–247.

    Google Scholar 

  16. S. GREIBACH, “A note on the recognition of one counter languages”, RAIRO Informatique théorique R2 (1975), 5–12.

    Google Scholar 

  17. S. GREIBACH, “Remarks on blind and partially blind one-way multicounter machines”, Theoretical Computer Science 7 (1978), 311–324.

    Article  Google Scholar 

  18. S. GREIBACH, “One counter languages and the chevron operation”, RAIRO Informatique Théorique 13 (1979), 189–194.

    Google Scholar 

  19. M. JANTZEN, “On the hierarchy of Petri Net Languages”, RAIRO Informatique Théorique 13 (1979), 19–30.

    Google Scholar 

  20. M. JANTZEN, “The power of Synchronizing operations on strings”, 1980, Publication de University of California at Santa Barbara.

    Google Scholar 

  21. M. LATTEUX, “Cônes rationnels commutativement clos”, RAIRO Informatique Théorique 11 (1977), 29–51.

    Google Scholar 

  22. M. LATTEUX, “Langages à un compteur”, Publication IT-25-80, Lille 1980, soumis pour publication.

    Google Scholar 

  23. M. LATTEUX, “Langages commutatifs”, Thèse Sc. Math., Lille, 1978.

    Google Scholar 

  24. M. LATTEUX, “Cônes rationnels commutatifs”, J. of Comput. and Syst. Sciences, 18 (1979), 307–333.

    Article  Google Scholar 

  25. M. LATTEUX, “Sur les générateurs algébriques et linéaires”, Acta Informatica 13 (1980), 347–363.

    Article  Google Scholar 

  26. M. LATTEUX, “A propos du lemme de substitution”, 1980, à paraître dans Theoretical Computer Science.

    Google Scholar 

  27. M. LATTEUX et J. LEGUY, “Une propriété de la famille GRE”, Fundamental of Computation theory, Adademie-Verlag, Berlin, 1979, 255–261.

    Google Scholar 

  28. J. LEGUY, “Transductions rationnelles décroissantes”, 1979, à paraître dans RAIRO Informatique théorique.

    Google Scholar 

  29. J. LEGUY, “Transduction rationnelle décroissante et substitution”, 1980, Thèse, Lille.

    Google Scholar 

  30. M. NIVAT, “Transductions des languages de Chomsky”, Thèse Sc. Math., Grenoble, 1967.

    Google Scholar 

  31. A. SALOMAA, “On the index of a context-free grammar and language”, Information and Control 14 (1969), 474–477.

    Article  Google Scholar 

  32. P. TURAKAINEN, “On some bounded semi AFLs and AFLs”, 1980, à paraître dans Information Sciences.

    Google Scholar 

  33. M.K. YNTEMA, “Inclusion relations among families of context-free languages”, Information and Control 10 (1967), 572–597.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Université de Lille I et L.I.T.F. U.E.R. d'I.E.E.A, Informatique 59655, Villeneuve D'Ascq Cedex

    Michel Latteux

Authors
  1. Michel Latteux
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Peter Deussen

Rights and permissions

Reprints and permissions

Copyright information

© 1981 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Latteux, M. (1981). Quelques proprietes des langages a un Compteur. In: Deussen, P. (eds) Theoretical Computer Science. Lecture Notes in Computer Science, vol 104. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0017296

Download citation

  • DOI: https://doi.org/10.1007/BFb0017296

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-10576-3

  • Online ISBN: 978-3-540-38561-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation