Shortest repetition-free words accepted by automata

DOI10.1007/978-3-642-39310-5_18zbMATH Open1388.68176arXiv1304.2959OpenAlexW2962860594MaRDI QIDQ2843095FDOQ2843095

Authors: Hamoon Mousavi, Jeffrey Shallit 

Publication date: 9 August 2013

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

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.

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

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

Mathematics Subject Classification ID

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

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)