[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

How Many Holes Can an Unbordered Partial Word Contain?

  • Conference paper
Language and Automata Theory and Applications (LATA 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5457))

  • 896 Accesses

Abstract

Partial words are sequences over a finite alphabet that may have some undefined positions, or “holes,” that are denoted by \(\ensuremath{\diamond}\)’s. A nonempty partial word is called bordered if one of its proper prefixes is compatible with one of its suffixes (here \(\ensuremath{\diamond}\) is compatible with every letter in the alphabet); it is called unbordered otherwise. In this paper, we investigate the problem of computing the maximum number of holes a partial word of a fixed length can have and still fail to be bordered.

This material is based upon work supported by the National Science Foundation under Grant No. DMS–0754154. We thank the referees of a preliminary version of this paper for their very valuable comments and suggestions. A World Wide Web server interface has been established at www.uncg.edu/cmp/research/countingpwords for automated use of the program. This work was done during the fourth author’s stay at the University of North Carolina at Greensboro.

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.

Similar content being viewed by others

References

  1. Berstel, J., Boasson, L.: Partial words and a theorem of Fine and Wilf. Theoretical Computer Science 218, 135–141 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  2. Blanchet-Sadri, F.: Algorithmic Combinatorics on Partial Words. Chapman & Hall/CRC Press (2007)

    Google Scholar 

  3. Blanchet-Sadri, F.: Primitive partial words. Discrete Applied Mathematics 148, 195–213 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  4. Blanchet-Sadri, F., Davis, C., Dodge, J., Mercaş, R., Moorefield, M.: Unbordered partial words. Discrete Applied Mathematics (2008), doi:10.1016/j.dam.2008.04.004

    Google Scholar 

  5. Blanchet-Sadri, F.: Open problems on partial words. In: Bel-Enguix, G., Jiménez-López, M., Martín-Vide, C. (eds.) New Developments in Formal Languages and Applications, pp. 11–58. Springer, Berlin (2007)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of North Carolina, P.O. Box 26170, Greensboro, NC 27402–6170, USA

    Francine Blanchet-Sadri

  2. Department of Mathematical Sciences, Carnegie Mellon University, 5032 Forbes Ave., Pittsburgh, PA 15289, USA

    Emily Allen

  3. Department of Mathematics, University of Mississippi, P.O. Box 1848, University, MS 38677, USA

    Cameron Byrum

  4. GRLMC, Universitat Rovira i Virgili, Plaça Imperial Tárraco, 1, Tarragona, 43005, Spain

    Robert Mercaş

Authors
  1. Francine Blanchet-Sadri
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Emily Allen
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Cameron Byrum
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Robert Mercaş
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Research Group on Mathematical Linguistics, Rovira i Virgili University, Av. Catalunya, 35, 43002, Tarragona, Spain

    Adrian Horia Dediu

  2. Research Group on Mathematical Linguistics, Universitat Rovira i Virgili, Tarragona, Spain

    Armand Mihai Ionescu

  3. European Research Council Executive Agency, 16 Place Rogier, 1210, Brussels, Belgium

    Carlos Martín-Vide

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Blanchet-Sadri, F., Allen, E., Byrum, C., Mercaş, R. (2009). How Many Holes Can an Unbordered Partial Word Contain?. In: Dediu, A.H., Ionescu, A.M., Martín-Vide, C. (eds) Language and Automata Theory and Applications. LATA 2009. Lecture Notes in Computer Science, vol 5457. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-00982-2_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-00982-2_15

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-00981-5

  • Online ISBN: 978-3-642-00982-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation