Shortest repetition-free words accepted by automata

DOI10.1007/978-3-642-39310-5_18MaRDI QIDQ2843095zbMATH OpenOpenAlexFDO

Authors Hamoon Mousavi, Jeffrey Shallit

Publication date 9 August 2013

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Combinatorics on words (68R15)

Abstract: We consider the following problem: given that a finite automaton $M$ of $N$ states accepts at least one $k$-power-free (resp., overlap-free) word, what is the length of the shortest such word accepted? We give upper and lower bounds which, unfortunately, are widely separated.

Recommendations

• Overlap-free words and finite automata
• scientific article; zbMATH DE number 512830
• Finite Automata, Palindromes, Powers, and Patterns
• Automata accepting primitive words
• scientific article; zbMATH DE number 3912631

Cited in

(1)

• Finite Automata, Palindromes, Powers, and Patterns

This page was built for publication: Shortest repetition-free words accepted by automata

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