<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>

COPY SCRIPT

For further information contact us at helpdesk@openaire.eu

The number of binary rotation words

descriptionPublicationkeyboard_double_arrow_right Article , Preprint , Other literature type 11 Aug 2014Embargo end date: 01 Jan 2013 France Publisher:EDP SciencesJournal:RAIRO - Theoretical Informatics and Applications, volume 48, pages 453-465 (issn: 0988-3754, eissn: 1290-385X,

Authors: Frid, Anna E.; Jamet, Damien;

doi: 10.1051/ita/2014019 , 10.48550/arxiv.1302.3722

arXiv: http://arxiv.org/abs/1302.3722

The number of binary rotation words

- Summary
- Subjects
- Related research
  (1)
- Metrics

Abstract

We consider binary rotation words generated by partitions of the unit circle to two intervals and give a precise formula for the number of such words of length n. We also give the precise asymptotics for it, which happens to be O(n^4). The result continues the line initiated by the formula for the number of all Sturmian words obtained by Lipatov in 1982, then independently by Berenstein, Kanal, Lavine and Olson in 1987, Mignosi in 1991, and then with another technique by Berstel and Pocchiola in 1993.

Submitted to RAIRO ITA

Country

France

Related Organizations

French National Centre for Scientific Research
France
University of Lorraine
France
Aix-Marseille University
France
French Institute for Research in Computer Science and Automation
France
University of Lorraine
France

View all View all

Keywords

FOS: Computer and information sciences, rotation words, Discrete Mathematics (cs.DM), subword complexity, [MATH.MATH-DS] Mathematics [math]/Dynamical Systems [math.DS], Sturmian words, Dynamical Systems (math.DS), rotation, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], FOS: Mathematics, Mathematics - Combinatorics, 68R15, 37B10, Combinatorics (math.CO), Mathematics - Dynamical Systems, total complexity, Computer Science - Discrete Mathematics

1 Research products, page 1 of 1

On the arithmetical complexity of Sturmian words
2007IsAmongTopNSimilarDocuments

Impact byBIP!

	citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	1
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average