On the subword complexity and square-freeness of formal languages | SpringerLink
Skip to main content
Springer Nature Link
Log in

On the subword complexity and square-freeness of formal languages

  • Conference paper
  • First Online:
Theoretical Computer Science

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

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. Autebert, J.M., Beauquier, J., Boasson, L. and Nivat, M., Quelques problemes ouverts en théorie des languages algébraiques, RAIRO Informatique Theorique, v. 13, 363–379, 1979.

    Google Scholar 

  2. Berstel, J., Sur les mots sans carré définis par un morphisme, Lecture Notes in Computer Science, Springer-Verlag, v. 71, 16–25, 1979.

    Google Scholar 

  3. Ehrenfeucht, A., Lee, K.P. and Rozenberg, G., Subword complexities of various classes of deterministic developmental languages without interactions, Theoretical Computer Science, v. 1, 59–76, 1975.

    Article  Google Scholar 

  4. Harrison, M., Introduction to formal language theory, Addison-Wesley, 1979.

    Google Scholar 

  5. Rozenberg, G. and Salomaa, A., The mathematical theory of L-systems, Academic Press, 1979.

    Google Scholar 

  6. Salomaa, A., Jewels of formal language theory, Computer Science Press, to appear.

    Google Scholar 

  7. Thue, A., Ueber unendliche Zeichenreihen, Norsk. Vid. Solsk. Skr. I Mat. Nat. Kl., nr. 7, 1–22, 1906.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, University of Colorado at Boulder, Boulder, Colorado, USA

    A. Ehrenfeucht

  2. Institute of Applied Mathematics and Computer Science, University of Leiden, Leiden, The Netherlands

    G. Rozenberg

Authors
  1. A. Ehrenfeucht
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. G. Rozenberg
    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

Ehrenfeucht, A., Rozenberg, G. (1981). On the subword complexity and square-freeness of formal languages. In: Deussen, P. (eds) Theoretical Computer Science. Lecture Notes in Computer Science, vol 104. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0017289

Download citation

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

  • 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