Maximal state complexity and generalized de Bruijn words

DOI10.1016/j.ic.2021.104689OpenAlexW3120801721MaRDI QIDQ2113383

Daniel Gabric, Štěpán Holub, Jeffrey O. Shallit

Publication date: 14 March 2022

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1903.05442

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An algorithm for generating shift-register cycles
• Asymptotically-tight bounds on the number of cycles in generalized de Bruijn-Good graphs
• Strings with maximally many distinct subsequences and substrings
• Generalized de Bruijn words and the state complexity of conjugate sets
• On the maximum number of distinct factors of a binary string
• m-ary closed sequences
• Binary Ring Sequences
• State complexity of cyclic shift
• A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
• De Bruijn Sequences-A Model Example of the Interaction of Discrete Mathematics and Computer Science
• An algebraic construction for q-ary shift register sequences
• Cyclic Shift on Prefix-Free Languages
• Normal Recurring Decimals

This page was built for publication: Maximal state complexity and generalized de Bruijn words