On the Morse-Hedlund complexity gap

Details On the Morse-Hedlund complexity gap On the Morse-Hedlund complexity gap

2009-03-09

arxiv.org/abs/0903.1627v5

Computer Science

Formal Languages and Automata Theory

7 pages. Not intended to be submitted. New proof of an old result

Scientific paper

In 1938, Morse and Hedlund proved that the subword complexity function of an
infinite word is either bounded or at least linearly growing. In 1982,
Ehrenfeucht and Rozenberg proved that this gap property holds for the subword
complexity function of any language. The aim of the present paper is to present
a self-contained, compact proof of Ehrenfeucht and Rozenberg's result.

Affiliated with

Also associated with

No associations

Rating

On the Morse-Hedlund complexity gap does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Morse-Hedlund complexity gap, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Morse-Hedlund complexity gap will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-96293