Automatic sequence

Automatic sequence

An automatic sequence is an infinite word characterized by a finite automaton. There are two equivalent definitions.

Automaton point of view

Let "q" be an integer, and "A"=("E",φ,"e") be a deterministic automaton where
*"E" is the finite set of states
*φ : "E"× [0,"q"-1] →"E" is the transition function
*ein E is the initial statealso let "A" be a finite set, and π:"E"→"A" a projection towards "A".

For each "n", take "m"("n") = π(φ("e",n')) where n' is "n" written in base "q". Then the sequence "m" = "m"(1)"m"(2)"m"(3)... is called a "q"-automatic sequence.

ubstitution point of view

Let σ be a morphism of the free monoid "E"* with sigma(E)subseteq E^q, and ein E such that σ("e") begins by "e". Let also be "A" and π as before. Then if m' is a fixpoint of σ, that is to say m' = σ(m'), then "m" = π(m') is a "q"-automatic sequence over "A".

Examples

The Thue-Morse sequence is automatic: take "E"="A"={0,1}, "e"=0, π=id, and σ such that σ(0)=01, σ(1)=10; we get the fixpoint 01101001100101101001011001101001... , which is in fact the Thue-Morse word.


Wikimedia Foundation. 2010.

Поможем написать курсовую

Look at other dictionaries:

  • automatic sequence — noun : the arrangement of a recording on successive sides of two or more phonograph discs so that the continuity of the recording is preserved when the discs are played on a record changer …   Useful english dictionary

  • Automatic Sequence Controlled Calculator — Mark I linke Seite Der Mark I, früher Automatic Sequence Controlled Calculator (ASCC) genannt, ist ein in den USA zwischen 1943 und 1944 vollständig aus elektromechanischen Bauteilen gebauter Computer. Der Rechner wurde von Howard H. Aiken von… …   Deutsch Wikipedia

  • automatic sequence control — programinis valdymas statusas T sritis automatika atitikmenys: angl. automatic sequence control; memory stored control; program control; programmed control; time schedule control vok. Ablaufsteuerung, f; programmierbare Steuerung, f;… …   Automatikos terminų žodynas

  • automatic sequence manipulator — automatinis nuoseklusis manipuliatorius statusas T sritis automatika atitikmenys: angl. automatic sequence manipulator vok. automatischer ablaufgesteuerter Manipulator, m rus. автоматический манипулятор последовательного действия, m pranc.… …   Automatikos terminų žodynas

  • Automatic sequence cut — Программированная (с последовательной перестановкой размера) разрезка стопы (бумаги) …   Краткий толковый словарь по полиграфии

  • Aiken IBM Automatic Sequence Controlled Calculator Mark I — Harvard Mark I Pour les articles homonymes, voir Harvard et Mark I. Côté droit. L’IBM …   Wikipédia en Français

  • Automatic full barriers — are a set of four half barriers closing a road at a railway level crossing. Typically the barriers on the approach side to the crossing are lowered first with those on the exit side following shortly after. The sequence timing is set to allow… …   Wikipedia

  • Automatic differentiation — In mathematics and computer algebra, automatic differentiation, or AD, sometimes alternatively called algorithmic differentiation, is a method to numerically evaluate the derivative of a function specified by a computer program. Two classical… …   Wikipedia

  • Automatic test pattern generation — ATPG (acronym for both Automatic Test Pattern Generation and Automatic Test Pattern Generator) is an electronic design automation method/technology used to find an input (or test) sequence that, when applied to a digital circuit, enables testers… …   Wikipedia

  • Automatic transmission — An automatic transmission (commonly AT or Auto ) is an automobile gearbox that can change gear ratios automatically as the vehicle moves, freeing the driver from having to shift gears manually. Similar but larger devices are also used for heavy… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”