Maximal state complexity and generalized de Bruijn words

DOI10.1016/J.IC.2021.104689MaRDI QIDQ2113383OpenAlexFDO

Authors Daniel Gabric, Štěpán Holub, Jeffrey 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)

Recommendations

• Generalized de Bruijn words and the state complexity of conjugate sets
• scientific article; zbMATH DE number 1992419
• scientific article; zbMATH DE number 2201359
• The number of languages with maximum state complexity
• The number of languages with maximum state complexity

Cites work

• scientific article; zbMATH DE number 4085051 (Why is no real title available?)
• scientific article; zbMATH DE number 3505007 (Why is no real title available?)
• scientific article; zbMATH DE number 1992419 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 3353192 (Why is no real title available?)
• scientific article; zbMATH DE number 3068971 (Why is no real title available?)
• scientific article; zbMATH DE number 3095523 (Why is no real title available?)
• A Survey of Full Length Nonlinear Shift Register Cycle Algorithms
• An algebraic construction for q-ary shift register sequences
• An algorithm for generating shift-register cycles
• Asymptotically-tight bounds on the number of cycles in generalized de Bruijn-Good graphs
• Binary Ring Sequences
• Cyclic shift on prefix-free languages
• De Bruijn Sequences-A Model Example of the Interaction of Discrete Mathematics and Computer Science
• Generalized de Bruijn words and the state complexity of conjugate sets
• Normal Recurring Decimals
• On the maximum number of distinct factors of a binary string
• Quotient complexity of regular languages
• State complexity of cyclic shift
• Strings with maximally many distinct subsequences and substrings
• m-ary closed sequences

Cited in

(2)

• Maximal State Complexity and Generalized de Bruijn Words
• Cut-down de Bruijn sequences

Describes a project that uses

Uses Software

• OEIS

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2113383)