Tree (automata theory)

In automata theory, a tree is a particular way of representing a tree structure as sequences of natural numbers.

The graphic illustration of the example labeled tree
Graphic illustration of the labeled tree described in the example

For example, each node of the tree is a word over set of natural numbers (), which helps this definition to be used in automata theory.

A tree is a set T* such that if t.cT, with t* and c, then tT and t.c1T for all 0 ≤ c1 < c. The elements of T are known as nodes, and the empty word ε is the (single) root of T. For every tT, the element t.cT is a successor of t in direction c. The number of successors of t is called its degree or arity, and represented as d(t). A node is a leaf if it has no successors. If every node of a tree has finitely many successors, then it is called a finitely, otherwise an infinitely branching tree. A path π is a subset of T such that ε ∈ π and for every tT, either t is a leaf or there exists a unique c such that t.c ∈ π. A path may be a finite or infinite set. If all paths of a tree are finite then the tree is called finite, otherwise infinite. A tree is called fully infinite if all its paths are infinite. Given an alphabet Σ, a Σ-labeled tree is a pair (T,V), where T is a tree and V: T → Σ maps each node of T to a symbol in Σ. A labeled tree formally defines a commonly used term tree structure. A set of labeled trees is called a tree language.

A tree is called ordered if there is an order among the successors of each of its nodes. The above definition of tree naturally suggests an order among the successors, which can be used to make the tree ranked.

In the case of ranked alphabets, an extra function Ar: Σ → is defined. This function associates a fixed arity to each symbol of the alphabet. In this case, each tT has to satisfy Ar(V(t)) = d(t). The trees that satisfy this property are called ranked trees. The trees that do not (necessarily) satisfy that property are called unranked.

For example, the above definition is used in the definition of an infinite tree automaton.

Example

Let T = {0,1}* and Σ = {a,b}. We define a labeling function V as follows: the labeling for the root node is V(ε) = a and, for every other node t ∈ {0,1}*, the labellings for its successor nodes are V(t.0) = a and V(t.1) = b. It is clear from the picture that T forms a (fully) infinite binary tree.

References

  • Comon, Hubert; Dauchet, Max; Gilleron, Rémi; Jacquemard, Florent; Lugiez, Denis; Löding, Christof; Tison, Sophie; Tommasi, Marc (November 2008). "Preliminaries". Tree Automata Techniques and Applications (PDF). Retrieved 11 February 2014.

Read other articles:

Ini adalah sebuah nama Indonesia yang tidak menggunakan nama keluarga. Nama Jayabaya adalah sebuah patronimik, dan tokoh ini dipanggil dengan nama depannya, Mulyadi. Mulyadi JayabayaBupati Lebak ke-26Masa jabatan17 November 2003 – 17 November 2013WakilOdih Padma (2003–2006)Amir Hamzah (2008–2013)PendahuluYas'a MulyadiPenggantiIti Jayabaya Informasi pribadiLahir22 Maret 1957 (umur 66)Lebak, Jawa Barat, Indonesia(sekarang Lebak, Banten)KebangsaanIndonesiaPartai politikPD...

 

KraterSeorang penunggang kuda muda yang akan dimahkotai oleh Dewi Kemanangan Nike yang bersayap, karya Pelukis Sisyphus, sekitar 420 SM, koleksi Museum LouvreMaterialKeramikDibuatBeragam budaya yang sebagian besar berasal dari Yunani dan dieksporPeriode/budayaSebuah jambangan dari Zaman Perunggu dan Zaman BesiTempatDi sekitar Mediterania Krater (bahasa Yunani Kuno: κρατήρ, kratēr, secara harfiah berarti wadah untuk mencampur) adalah wadah besar yang umum ditemukan pada zaman Yunani...

 

Diplomatische Beziehungen ist eine Weiterleitung auf diesen Artikel. Zur Fernsehserie siehe Diplomatische Beziehungen (Fernsehserie). Dieser Artikel befasst sich mit dem Begriff in der Außenpolitik. Zu dem gleichnamigen Film siehe Diplomatie (Film). v. l. n. r.: Anwar as-Sadat, Jimmy Carter und Menachem Begin nach der Unterzeichnung des Camp-David-Abkommens Diplomatie ist die Kunst und Praxis des Verhandelns zwischen bevollmächtigten Repräsentanten verschiedener Gruppen oder Nationen (Dipl...

For the 2012 film, see 3 Kanya. 1961 Indian-Bengali anthology film directed by Satyajit Ray Teen KanyaFilm posterDirected bySatyajit RayWritten bySatyajit Ray (screenplay)Rabindranath Tagore (stories)Produced bySatyajit RayStarringSoumitra Chatterjee [Amulya]Aparna Sen [Samapti]Distributed bySony PicturesRelease date 5 May 1961 (1961-05-05) Running time173 min.CountryIndiaLanguageBengali Teen Kanya (English: Three Girls) is a 1961 Indian Bengali anthology film directed by Satya...

 

American scientist (1930–1982) Hugh Everett IIIHugh Everett in 1964Born(1930-11-11)November 11, 1930Washington, D.C., U.S.DiedJuly 19, 1982(1982-07-19) (aged 51)McLean, Virginia, U.S.CitizenshipUnited StatesAlma materCatholic University of AmericaPrinceton University (PhD)Known forMany-worlds interpretationEverett's theorem[1][2][3]ChildrenElizabeth Everett, Mark Oliver EverettScientific careerFieldsPhysicsOperations researchOptimizationGame theoryInst...

 

بساموثيسPsammuthesتمثال برونزي لبساموثيس.فرعون مصرالحقبة392 قبل الميلاد, الأسرة المصرية التاسعة والعشرينسبقههاكورتبعههاكور فترة أخرى الألقاب الملكية اسم التتويج: اوسر رع ستب إن بتاح (القوة هي رع، المختار من بتاح)اسم حورس:  الاسم النبتي:  اسم حورس الذهبي:  أسر مصر القد...

يفتقر محتوى هذه المقالة إلى الاستشهاد بمصادر. فضلاً، ساهم في تطوير هذه المقالة من خلال إضافة مصادر موثوق بها. أي معلومات غير موثقة يمكن التشكيك بها وإزالتها. (نوفمبر 2019) كأس المعارض الأوروبية 1964–65 تفاصيل الموسم كأس المعارض الأوروبية  النسخة 7  البطل نادي فيرينتسفاروشي...

 

「ハマコー」はこの項目へ転送されています。その他の用語については「ハマコウ」をご覧ください。 実業家の「濵田幸一」あるいは経済学者の「浜田宏一」とは別人です。 日本の政治家浜田 幸一はまだ こういち 生年月日 (1928-09-05) 1928年9月5日出生地 千葉県君津郡青堀町没年月日 (2012-08-05) 2012年8月5日(83歳没)死没地 千葉県富津市出身校 日本大学農獣医学部拓殖学...

 

Play turn of a character in a game Not to be confused with Health (game terminology). A generic character has a total of three lives, indicated as light-blue orbs. The character has currently lost 3.5 out of 11 health points – losing all would cost a life. In video games, a life is a play-turn that a player character has, defined as the period between start and end of play.[1] Lives refer to a finite number of tries before the game ends with a game over.[2] It is sometimes c...

1984 single by John SchneiderCountry GirlsSingle by John Schneiderfrom the album Too Good to Stop Now B-sideThe Time of My LifeReleasedDecember 1984Recorded1984GenreCountryLength3:11LabelMCASongwriter(s)Troy Seals and Eddie SetserProducer(s)Jimmy BowenJohn Schneider singles chronology I've Been Around Enough to Know (1984) Country Girls (1984) It's a Short Walk from Heaven to Hell (1985) Country Girls is a song written by Troy Seals and Eddie Setser, and recorded by American country music art...

 

You can help expand this article with text translated from the corresponding article in Spanish. (July 2020) Click [show] for important translation instructions. View a machine-translated version of the Spanish article. Machine translation, like DeepL or Google Translate, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikiped...

 

1989 supplement by R. Talsorian Games Cover art by Luis Royo, 1986 Hardwired: The Sourcebook is a supplement published by R. Talsorian Games in 1989 for the dystopian near-future science fiction role-playing game Cyberpunk. Contents This supplement is set in the year 2151 using the background of the Walter Jon Williams novel Hardwired. The Earth has become a dystopian world where most heavy industry and the social elite are in orbit, the Orbital Corporations control the world, and the United ...

Universitas Muhammadiyah JemberGedung Kampus Universitas Muhammadiyah JemberDidirikan11 Maret 1981RektorDr. Hanafi, M.PdAlamatJalan Karimata No. 49 Kelurahan Sumbersari, Kecamatan Sumbersari, Kabupaten Jember, Jember, Jawa TimurSitus webhttp://www.unmuhjember.ac.id Universitas Muhammadiyah Jember adalah sebuah perguruan tinggi swasta di Jember, Indonesia, yang berdiri pada 11 Maret tahun 1981, sebagaimana termaktub dalam Piagam Pendirian yang diterbitkan oleh Pimpinan Pusat Muhammadiyah. Dike...

 

1938 Argentine filmEl Canillita y la damaFilm posterDirected byLuis César AmadoriWritten byLuis César Amadori, Antonio BottaStarringLuis SandriniCinematographyGumer BarreirosEdited byEmilio MurúaMusic byHans DiernhammerDistributed byCorporación Cinematográfica Argentina Release date1938Running time101 minutesCountryArgentinaLanguageSpanish The Newsie and the Lady (Spanish: El Canillita y la dama) is a 1938 Argentine comedy film directed and written by Luis César Amadori.[1] Cast...

 

1993 studio album by Melvins HoudiniStudio album by MelvinsReleasedSeptember 21, 1993 (1993-09-21)Recorded1992–1993Genre Sludge metal grunge doom metal Length54:44LabelAtlanticProducer Melvins Kurt Cobain GGGarth Melvins chronology Lysol(1992) Houdini(1993) Prick(1994) Singles from Houdini HoochReleased: 1993 LizzyReleased: 1993 Honey BucketReleased: 1993 Houdini is the fifth studio album by American rock band Melvins, released on September 21, 1993, by Atlantic Records. ...

Turkish footballer Gökhan Süzen Süzen (left) playing for İstanbul BB in 2011Personal informationFull name Gökhan SüzenDate of birth (1987-07-12) July 12, 1987 (age 36)Place of birth Düzce, TurkeyHeight 1.81 m (5 ft 11+1⁄2 in)Position(s) Left backTeam informationCurrent team DenizlisporNumber 26Youth career2003–2006 Galatasaray A2Senior career*Years Team Apps (Gls)2006–2013 İstanbul BB 105 (2)2013–2015 Beşiktaş 11 (0)2014–2015 → Gaziantepspor (loan...

 

Oranje CommandoOranje Commando emblemCountry South AfricaAllegiance  Republic of South Africa  Republic of South Africa Branch  South African Army  South African Army TypeInfantryRoleLight InfantrySizeOne BattalionPart ofSouth African Infantry CorpsArmy Territorial ReserveGarrison/HQKenhardtMilitary unit Orania Commando was a light infantry regiment of the South African Army. It formed part of the South African Army Infantry Formation as well as the South African...

 

History of Latter Day Saints and Indigenous Americans Painting which hung in the Salt Lake Temple of Mormon founder Joseph Smith preaching to Native Americans in Illinois Over the past two centuries, the relationship between Native American people and Mormonism has included friendly ties, displacement, battles, slavery, education placement programs, and official and unofficial discrimination.[1] Native American people (also called American Indians) were historically considered a speci...

Roman Catholic church in Manila, Philippines This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Archdiocesan Shrine of Espiritu Santo – news · newspapers · books · scholar · JSTOR (August 2017) (Learn how and when to remove this template message) Church in Manila, PhilippinesArchdiocesan Shrine of Espiritu Sant...

 

2013 studio album by Sheryl CrowFeels like HomeStudio album by Sheryl CrowReleasedSeptember 10, 2013 (2013-09-10)Recorded2012–2013StudioBlackbird Studio, Ocean Way Nashville, Big Green Barn Studio (Nashville)GenreCountryLength44:10LabelOld Green Barn/Sea Gayle Music/Warner Bros. NashvilleProducerSheryl Crow, Justin NiebankSheryl Crow chronology 100 Miles from Memphis(2010) Feels like Home(2013) Be Myself(2017) Singles from Feels like Home EasyReleased: March 12, 2013 ...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!