On the usefulness of bifaithful rational cones | Theory of Computing Systems Skip to main content
Springer Nature Link
Log in

On the usefulness of bifaithful rational cones

  • Published:
Mathematical systems theory Aims and scope Submit manuscript

Abstract

Roughly, a faithful (resp. bifaithful) rational transduction is a non deterministic finite state mapping that does not decrease (resp. alter) the length of words by very much. We introduce the notion of stronglyf-saturated language:L is stronglyf-saturated if and only if for any languageL′, from which we can obtainL by faithful rational transduction, for any languageL″, image ofL by a faithful rational transduction, there exists a bifaithful rational transduction τ such thatL″ is the image ofL′ τ. We prove that no quasirational language and no language in the substitution closed rational cone generated by bounded languages is stronglyf-saturated. Conversely, we establish that a language such as\(\bar D_1^{\prime *} = \{ w \in \{ a,b\} ^* /|w|_a \ne |w|_b \}\), very low in the hierarchy of algebraic languages, is stronglyf-saturated thus is not a quasirational language. We also establish that any commutative quasi rational language over two letters is rational.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. J. M. Autebert, Cylindres de langages alébriques. Thèse Sc. Math. Paris, 1978.

  2. J. Beauquier, Independence of linear and one-counter generators.Fundamentals of Computation Theory, Akademie. Verlag, Berlin 1979, 45–51.

    Google Scholar 

  3. J. Beauquier and J. Berstel, More about the “Geography” of context free languages.Information and Control 49, 1981, 91–108.

    Google Scholar 

  4. J. Berstel,Transductions and Context-Free Languages, Teubner Verlag, 1979.

  5. L. Boasson, Two iteration theorems for some families of languages,J. of Comput. and Syst. Sciences 7, 1973, 583–596.

    Google Scholar 

  6. L. Boasson, The inclusion of the substitution closure of linear and one-counter languages in the Largest sub AFL of the family of CFL's is proper,Inform. Process. Let 2, 1973, 135–140.

    Google Scholar 

  7. L. Boasson, Un langage algébrique particulier,Rairo Informatique Theorique 13, 1979, 203–215.

    Google Scholar 

  8. L. Boasson and M. Nivat, Sur diverses familles de langages fermées par transduction rationnelle.Acta Informatica 2, 1973, 180–188.

    Google Scholar 

  9. S. Eilenberg, Communication au Congrès International des mathématiciens, Nice, 1970.

  10. J. Engelfriet, and G. Rozenberg, A translational theorem for the class of EOL languages.Information and Control 1981, 50, 175–183.

    Google Scholar 

  11. S. Ginsburg,Algebraic and Automata-Theoretic Properties of Formal Languages. North-Holland Publishing Company, 1975.

  12. S. Ginsburg, J. Goldstine, and S. Greibach, Uniformly erasable AFL,J. of Comput. and Syst. Sciences 10, 1975, 165–182.

    Google Scholar 

  13. S. Ginsburg and S. Greibach, Abstract families of languages. Memoirs of the American Mathematical Society 87, 1969, 1–32.

    Google Scholar 

  14. J. Goldstine, Substitution and Bounded languages.J. of Comput. and Syst. Sciences 6, 1972, 9–29.

    Google Scholar 

  15. S. Greibach, Chains of full AFL's,Math. Syst. Theory 4, 1970, 231–242.

    Google Scholar 

  16. S. Greibach, Simple syntactic operators on full semi-AFL's,J. of Comput. and Syst. Sciences 6, 1972, 30–76.

    Google Scholar 

  17. S. Greibach, One counter languages and the IRS condition,J. of Comput. and Syst. Sciences 10 (1975), 237–247.

    Google Scholar 

  18. M. Latteux, Cônes rationnels commutatifs,J. of Comput. and Syst. Sciences 18, 1979, 307–333.

    Google Scholar 

  19. M. Latteux, Sur les générateurs algébriques et linéaires,Acta Informatica 13, 1980, 347–363.

    Google Scholar 

  20. M. Latteux, A propos du lemme de substitution,Theoretical Computer Science 14, 1981, 119–123.

    Google Scholar 

  21. M. Latteux, Quelques propriété des langages à un compteur. in 5ème GI-Conference, Lecture Notes inComputer Science 104, 1981, 52–63.

    Google Scholar 

  22. J. Leguy, Langages saturés et cônes décroissants. Langages et cônes bifidèles,Acta Informatica 18, 1982, 65–78.

    Google Scholar 

  23. J. Leguy, Transductions rationnelles décroissantes,Rairo Informatique Theorique 5, 1981, 141–148.

    Google Scholar 

  24. J. Leguy, Deux nouvelles extensions du lemme de substitution. in Actes du Colloque: Mathematics for Computer Science, Paris, 16–18 Mars 1982, 199–204.

  25. M. Nivat, Transductions des langages de Chomsky,Ann. Inst. Fourier 18, 1968, 339–455.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratoire de Recherche en Informatique Fondamentale, L.A. 369, France

    Michel Latteux & Jeannine Leguy

Authors
  1. Michel Latteux
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jeannine Leguy
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Latteux, M., Leguy, J. On the usefulness of bifaithful rational cones. Math. Systems Theory 18, 19–32 (1985). https://doi.org/10.1007/BF01699459

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

Keywords

Search

Navigation