Automatic sequence (original) (raw)
In mathematics and theoretical computer science, an automatic sequence (also called a k-automatic sequence or a k-recognizable sequence when one wants to indicate that the base of the numerals used is k) is an infinite sequence of terms characterized by a finite automaton. The n-th term of an automatic sequence a(n) is a mapping of the final state reached in a finite automaton accepting the digits of the number n in some fixed base k.
| Property | Value |
|---|---|
| dbo:abstract | In mathematics and theoretical computer science, an automatic sequence (also called a k-automatic sequence or a k-recognizable sequence when one wants to indicate that the base of the numerals used is k) is an infinite sequence of terms characterized by a finite automaton. The n-th term of an automatic sequence a(n) is a mapping of the final state reached in a finite automaton accepting the digits of the number n in some fixed base k. An automatic set is a set of non-negative integers S for which the sequence of values of its characteristic function χS is an automatic sequence; that is, S is k-automatic if χS(n) is k-automatic, where χS(n) = 1 if n S and 0 otherwise. (en) En mathématique, en combinatoire des mots et en théorie des automates, une suite automatique (ou suite -automatique où est un entier) est une suite infinie de symboles qui peut être caractérisée de plusieurs manières équivalentes : par automate fini déterministe, par morphisme uniforme, par noyau ou par série formelle. Par exemple, la caractérisation par automates est la suivante : une suite est -automatique s'il existe un automate tel que le -ième terme de la suite est fonction de l'état atteint par cet automate après lecture de en base . L'exemple par excellence d'une suite 2-automatique est la suite de Prouhet-Thue-Morse. Un ensemble -reconnaissable de nombres est un ensemble S d'entiers naturels dont la suite caractéristique est k-automatique ; en d'autres termes, S est k-reconnaissable si la suite , définie par si et sinon, est k-automatique. Un nombre réel automatique (plus précisément un nombre réel -automatique) est un nombre réel dont le développement en base est une suite -automatique. Tout nombre réel automatique est soit rationnel, soit transcendant. Ce théorème fournit une large classe de nombres transcendants. Par exemple, la constante de Prouhet-Thue-Morse, dont le développement binaire est donné par la suite du même nom, est un nombre transcendant. (fr) Uma sequência automática (ou k-sequência automática) é uma sequência infinita de termos caracterizado por um autômato finito. O enésimo termo da sequência é um mapeamento do estado final do autômato quando a sua entrada de n dígitos tem como base um valor fixo k. Um conjunto k-automático é um conjunto não negativo de inteiros no qual cada sequência de valores é uma sequência automática de uma função característica, ou seja, um conjunto n da sequência pode ser determinado por um autômato finito de dígitos n na base k. Um autômato lendo dígitos de base k a partir da mais significante é chamado de leitura direta, e uma leitura a partir do menos significante é chamada de leitura reversa. No entanto as duas direções conduzem a mais classes de sequências. Cada sequência automática é uma . (pt) |
| dbo:thumbnail | wiki-commons:Special:FilePath/ThueMorseAutomaton.png?width=300 |
| dbo:wikiPageExternalLink | https://www.ams.org/bookpages/crmm-27 https://archive.org/details/appliedcombinato0000loth https://archive.org/details/newadvancestrans1986bake https://archive.org/details/newadvancestrans1986bake/page/n113 |
| dbo:wikiPageID | 7740302 (xsd:integer) |
| dbo:wikiPageLength | 23250 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1122555983 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Cambridge_University_Press dbr:Morphic_word dbr:Deterministic_finite_automaton dbr:Algebraic_function dbc:Combinatorics_on_words dbr:Julius_Richard_Büchi dbr:Regular_paperfolding_sequence dbr:Decidability_(logic) dbr:Mathematical_Systems_Theory dbr:Mathematics dbr:Pumping_lemma_for_regular_languages dbr:Modulo_operation dbr:Baum–Sweet_sequence dbr:Tag_system dbr:Theoretical_computer_science dbr:K-regular_sequence dbr:Alan_Cobham_(mathematician) dbr:American_Mathematical_Society dbc:Integer_sequences dbr:Finite_field dbr:Fixed_point_(mathematics) dbr:Formal_power_series dbr:Unary_numeral_system dbr:Radix dbc:Automata_(computation) dbr:Cobham's_theorem dbr:Büchi_arithmetic dbr:Free_monoid dbr:Injective_function dbr:Integer dbr:Sequence dbr:Set_(mathematics) dbr:Wojciech_Szpankowski dbr:File:ThueMorseAutomaton.png dbr:Rudin–Shapiro_sequence dbr:Gesine_Reinert dbr:Multiplicative_independence dbr:Sophie_Schbath dbr:Thue–Morse_sequence dbr:Valérie_Berthé dbr:Springer-Verlag dbr:Finite_automaton dbr:Uniform_morphism |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Reflist dbt:OEIS2C |
| dct:subject | dbc:Combinatorics_on_words dbc:Integer_sequences dbc:Automata_(computation) |
| gold:hypernym | dbr:K |
| rdf:type | dbo:School yago:Abstraction100002137 yago:Arrangement107938773 yago:Group100031264 yago:Ordering108456993 yago:WikicatIntegerSequences yago:Sequence108459252 yago:Series108457976 |
| rdfs:comment | In mathematics and theoretical computer science, an automatic sequence (also called a k-automatic sequence or a k-recognizable sequence when one wants to indicate that the base of the numerals used is k) is an infinite sequence of terms characterized by a finite automaton. The n-th term of an automatic sequence a(n) is a mapping of the final state reached in a finite automaton accepting the digits of the number n in some fixed base k. (en) En mathématique, en combinatoire des mots et en théorie des automates, une suite automatique (ou suite -automatique où est un entier) est une suite infinie de symboles qui peut être caractérisée de plusieurs manières équivalentes : par automate fini déterministe, par morphisme uniforme, par noyau ou par série formelle. Par exemple, la caractérisation par automates est la suivante : une suite est -automatique s'il existe un automate tel que le -ième terme de la suite est fonction de l'état atteint par cet automate après lecture de en base . L'exemple par excellence d'une suite 2-automatique est la suite de Prouhet-Thue-Morse. (fr) Uma sequência automática (ou k-sequência automática) é uma sequência infinita de termos caracterizado por um autômato finito. O enésimo termo da sequência é um mapeamento do estado final do autômato quando a sua entrada de n dígitos tem como base um valor fixo k. Um conjunto k-automático é um conjunto não negativo de inteiros no qual cada sequência de valores é uma sequência automática de uma função característica, ou seja, um conjunto n da sequência pode ser determinado por um autômato finito de dígitos n na base k. Cada sequência automática é uma . (pt) |
| rdfs:label | Automatic sequence (en) Suite automatique (fr) Sequência automática (pt) |
| owl:sameAs | freebase:Automatic sequence yago-res:Automatic sequence wikidata:Automatic sequence dbpedia-fr:Automatic sequence dbpedia-pt:Automatic sequence https://global.dbpedia.org/id/3E3uM |
| prov:wasDerivedFrom | wikipedia-en:Automatic_sequence?oldid=1122555983&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/ThueMorseAutomaton.png |
| foaf:isPrimaryTopicOf | wikipedia-en:Automatic_sequence |
| is dbo:wikiPageRedirects of | dbr:Cobham-Semenov_theorem dbr:Automatic_real_number dbr:Automatic_sequences dbr:Automatic_set dbr:Period-doubling_sequence dbr:Cobham–Semenov_theorem dbr:K-automatic_sequence |
| is dbo:wikiPageWikiLink of | dbr:Morphic_word dbr:Regular_paperfolding_sequence dbr:Index_of_philosophy_articles_(A–C) dbr:Presburger_arithmetic dbr:Cobham-Semenov_theorem dbr:Baum–Sweet_sequence dbr:K-regular_sequence dbr:K-synchronized_sequence dbr:Alan_Cobham_(mathematician) dbr:Cobham's_theorem dbr:Büchi_arithmetic dbr:Fibbinary_number dbr:Sequence dbr:Rudin–Shapiro_sequence dbr:Thue–Morse_sequence dbr:Automatic_real_number dbr:Automatic_sequences dbr:Automatic_set dbr:Period-doubling_sequence dbr:Cobham–Semenov_theorem dbr:K-automatic_sequence |
| is foaf:primaryTopic of | wikipedia-en:Automatic_sequence |
