Navigation: Home > Publications > Short paper in a conference proceedings: On subword Complexity of Morphic Sequences

 Short paper in a conference proceedings: R. Deviatov, On subword Complexity of Morphic Sequences

Abstract
We sketch the proof of the following result: the subword complexity of arbitrary morphic sequence is either Θ(n2), or O(n3/2).
Final proceedings version: download pdf
Copyright notice: This article is copyright Springer-Verlag Berlin Heidelberg 2008
This version is also available at the paper page at the journal website (your university or you need a subscription to download the paper from the journal website).
Last version submitted to the conference: download pdf; download zip archive with all sources
Bibliographic reference:
R. A. Devyatov, On subword complexity of morphic sequences, in: Edward A. Hirsch, Alexander A. Razborov, Alexei Semenov, and Anatol Slissenko (Eds.), Proceedings of the 3rd international Conference on Computer Science: Theory and Applications (Moscow, Russia, June 07–12, 2008), Lecture Notes In Computer Science 5010, Springer-Verlag, Berlin, Heidelberg, 2008, 146–157.
Article page at the journal website

DOI: 10.1007/978-3-540-79709-8_17 (link)