Skip to Main content Skip to Navigation
Conference papers

Generalized de Bruijn Words and the State Complexity of Conjugate Sets

Abstract : We consider a certain natural generalization of de Bruijn words, and use it to compute the exact maximum state complexity for the language consisting of the conjugates of a single word. In other words, we determine the state complexity of cyclic shift on languages consisting of a single word.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/hal-02387301
Contributor : Hal Ifip <>
Submitted on : Friday, November 29, 2019 - 4:36:17 PM
Last modification on : Friday, November 29, 2019 - 5:01:48 PM

File

 Restricted access
To satisfy the distribution rights of the publisher, the document is embargoed until : 2022-01-01

Please log in to resquest access to the document

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

Daniel Gabric, Štěpán Holub, Jeffrey Shallit. Generalized de Bruijn Words and the State Complexity of Conjugate Sets. 21th International Conference on Descriptional Complexity of Formal Systems (DCFS), Jul 2019, Košice, Slovakia. pp.137-146, ⟨10.1007/978-3-030-23247-4_10⟩. ⟨hal-02387301⟩

Share

Metrics

Record views

46