Shortlex order

In mathematics, and particularly in the theory of formal languages, shortlex is a total ordering for finite sequences of objects that can themselves be totally ordered. In the shortlex ordering, sequences are primarily sorted by cardinality (length) with the shortest sequences first, and sequences of the same length are sorted into lexicographical order.[1] Shortlex ordering is also called radix, length-lexicographic, military, or genealogical ordering.[2]

In the context of strings on a totally ordered alphabet, the shortlex order is identical to the lexicographical order, except that shorter strings precede longer strings. For example, the shortlex order of the set of strings on the English alphabet (in its usual order) is [ε, a, b, c, ..., z, aa, ab, ac, ..., zz, aaa, aab, aac, ..., zzz, ...], where ε denotes the empty string.

The strings in this ordering over a fixed finite alphabet can be placed into one-to-one order-preserving correspondence with the natural numbers, giving the bijective numeration system for representing numbers.[3] The shortlex ordering is also important in the theory of automatic groups.[4]

See also

References

  1. ^ Sipser, Michael (2012). Introduction to the Theory of Computation (3 ed.). Boston, MA: Cengage Learning. p. 14. ISBN 978-1133187790.
  2. ^ Bárány, Vince (2008), "A hierarchy of automatic ω-words having a decidable MSO theory", RAIRO Theoretical Informatics and Applications, 42 (3): 417–450, doi:10.1051/ita:2008008, MR 2434027.
  3. ^ Smullyan, R. (1961), "9. Lexicographical ordering; n-adic representation of integers", Theory of Formal Systems, Annals of Mathematics Studies, vol. 47, Princeton University Press, pp. 34–36.
  4. ^ Epstein, David B. A.; Cannon, James W.; Holt, Derek F.; Levy, Silvio V. F.; Paterson, Michael S.; Thurston, William P. (1992), Word processing in groups, Boston, MA: Jones and Bartlett Publishers, p. 56, ISBN 0-86720-244-0, MR 1161694.


Stub icon

This algebra-related article is a stub. You can help Wikipedia by expanding it.

Read other articles:

Jessica Jackley

Jessica JackleyJessica Jackley berbicara di Universitas Tennessee pada 24 Maret 2010Lahir1977 (umur 46–47)Tempat tinggalLos Angeles, California, A.S.Kebangsaan Amerika SerikatAlmamaterUniversitas Bucknell (B.A.) Sekolah Bisnis Stanford (M.B.A.)PekerjaanPendiri & CMO, Kiva.org Pendiri & CEO, ProFounderSuami/istriMatt Flannery (-2008)Reza AslanAnak3 Jessica Jackley adalah seorang pengusaha dan wirausahawan Amerika. Ia paling dikenal karena mendirikan Kiva dan kemudian P...

 

Selibat klerikal (Gereja Katolik)

Bagian dari seri tentangHukum KanonikGereja Katolik Hukum Mutakhir Kitab Hukum Kanonik 1983 Omnium in mentem Kitab Hukum Kanon Gereja-Gereja Timur Ad tuendam fidem Ex Corde Ecclesiae Indulgentiarum Doctrina Pastor Bonus Pontificalis Domus Universi Dominici Gregis Consuetudo Sejarah Hukum Kitab Hukum Kanonik 1917 Corpus Iuris Canonici Dekretis Regulæ Iuris Decretales Gregorii IX Dekretalis Decretum Gratiani Extravagantes Liber Septimus Tata Tertib Gereja Purba Didakhe Konstitusi Apostolik Kan...

 

Serie C2 1978-1979

Questa voce o sezione sull'argomento edizioni di competizioni calcistiche non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Serie C2 1978-1979 Competizione Serie C2 Sport Calcio Edizione 1ª Organizzatore Lega Nazionale Semiprofessionisti Date dal 1º ottobre 1978all'11 luglio 1979 Luogo Italia Partecip...

Al Capone

American gangster and businessman (1899–1947) This article is about the gangster. For other uses, see Al Capone (disambiguation). Capone redirects here. For other uses, see Capone (disambiguation). Al CaponeCapone in 1930BornAlphonse Gabriel Capone(1899-01-17)January 17, 1899New York City, U.S.DiedJanuary 25, 1947(1947-01-25) (aged 48)Palm Island, Florida, U.S.Resting placeMount Carmel Cemetery, Hillside, Illinois, U.S.Other namesScarfaceBig AlBig BoyPublic Enemy No. 1SnorkyOccupa...

 

Peppered moth evolution

Significance of the peppered moth in evolutionary biology This article is about the peppered moth's significance in evolutionary biology. For its evolutionary ancestry, see Insect evolution. Biston betularia f. typica, the white-bodied peppered moth. Biston betularia f. carbonaria, the black-bodied peppered moth. The evolution of the peppered moth is an evolutionary instance of directional colour change in the moth population as a consequence of air pollution during the Industrial Revolution...

 

Two Mothers (TV series)

South Korean TV series or program Two MothersPromotional posterGenreMelodrama Romance Family RevengeDeveloped byKBS DramaWritten byHwang Soon-YoungDirected byKwak Ki-WonStarringJang Seo-Hee Lee Chae-YoungMusic byLee Chang-heeCountry of originSouth KoreaOriginal languageKoreanNo. of episodes102ProductionExecutive producerLee Jae-YoungProducersBaek Sang-Hoon, Lee Un-JungRunning timeMondays to Fridays at 19:50 (KST)Production companiesJidam Incformerly Yein E&MOriginal releaseNetworkKBS2Rel...

Army of the Cumberland

Principal Union army unit in the Western Theater of the American Civil War Army of the CumberlandBattle of Missionary RidgeActiveOctober 24, 1862 – August 1, 1865Country United StatesBranch United States ArmyTypeField armyEngagementsAmerican Civil War Battle of Stones River Tullahoma Campaign Battle of Chickamauga Chattanooga Campaign Atlanta Campaign Franklin–Nashville Campaign CommandersNotablecommandersWilliam S. RosecransGeorge H. ThomasRobert AndersonMilitary unit The Army o...

 

Max Castillo (baseball)

Venezuelan baseball player (born 1999) Baseball player Max CastilloCastillo with the Omaha Storm Chasers in 2022Philadelphia Phillies – No. 68PitcherBorn: (1999-05-04) May 4, 1999 (age 25)Caracas, VenezuelaBats: RightThrows: RightMLB debutJune 19, 2022, for the Toronto Blue JaysMLB statistics (through 2023 season)Win–loss record0–3Earned run average5.43Strikeouts47 Teams Toronto Blue Jays (2022) Kansas City Royals (2022–2023) Maximo Alberto Castillo (born May 4, 19...

 

2016年美國總統選舉

2016年美國總統選舉 ← 2012 2016年11月8日 2020 → 538個選舉人團席位獲勝需270票民意調查投票率55.7%[1][2] ▲ 0.8 %   获提名人 唐納·川普 希拉莉·克林頓 政党 共和黨 民主党 家鄉州 紐約州 紐約州 竞选搭档 迈克·彭斯 蒂姆·凱恩 选举人票 304[3][4][註 1] 227[5] 胜出州/省 30 + 緬-2 20 + DC 民選得票 62,984,828[6] 65,853,514[6]...

Naniwasuji Line

Planned underground heavy rail line in central Osaka, Japan 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: Naniwasuji Line – news · newspapers · books · scholar · JSTOR (February 2021) (Learn how and when to remove this message) Naniwasuji LineSpace at JR Namba Station reserved for the Naniwasuji LineOvervi...

 

Sustainability measurement

Quantitative basis for the informed management of sustainability Trees being felled in Kalimantan, the Indonesian part of Borneo, in 2013, to make way for a new coal mining project Sustainability measurement is a set of frameworks or indicators used to measure how sustainable something is. This includes processes, products, services and businesses. Sustainability is difficult to quantify.[1] It may even be impossible to measure as there is no fixed definition.[2] To measure su...

 

Roland TR-606

TR-606PembuatRoland CorporationTanggal perilisan1981–1984SpesifikasiMemori penyimpanan32 pola, 8 laguInput/outputRoland TR-606 Drumatix adalah mesin drum sintesis analog yang dapat diprogram buatan Roland Corporation dari tahun 1981 hingga 1984. Awalnya 606 dirancang untuk digunakan bersama Roland TB-303 (penyintesis bass analog monofonik) untuk memberikan iringan drum dan bass yang sederhana untuk gitaris tanpa pemain drum/bass. TR-606 umumnya digunakan pada genre musik elektronik, seperti...

Ivory

Material derived from the tusks and teeth of animals For other uses, see Ivory (disambiguation). 11th-century Italian carved elephant tusk, Louvre. Cylindrical ivory casket, Siculo-Arabic, Hunt Museum. Ivory is a hard, white material from the tusks (traditionally from elephants) and teeth of animals, that consists mainly of dentine, one of the physical structures of teeth and tusks. The chemical structure of the teeth and tusks of mammals is the same, regardless of the species of origin, but ...

 

Area code 229

Telephone area code for southwest Georgia, United States Area code 229 is a telephone area code in the North American Numbering Plan for the southwest corner of the U.S. state of Georgia. The numbering plan area includes the cities of Albany, Valdosta, Adel, Leesburg, Bainbridge, Americus, Vienna, Fitzgerald, Ocilla, Cairo, Moultrie, Thomasville, McRae-Helena, and Tifton. The area code was created on August 1, 2000 in a three-way split of area code 912,[1] which had served the souther...

 

Eccellenza Lazio 2011-2012

Voce principale: Eccellenza 2011-2012. Eccellenza Lazio 2011-2012 Competizione Eccellenza Lazio Sport Calcio Edizione 21ª Organizzatore FIGC - LNDComitato Regionale Lazio Date dal 4 settembre 2011al 20 maggio 2012 Luogo  Italia Partecipanti 36 Formula 2 gironi all'italiana Risultati Vincitore Ostia Mare (Girone A)San Cesareo (Girone B) Altre promozioni LVPA Frascati Retrocessioni (le squadre scritte in corsivo sono poi state ripescate)Corneto Tarquinia Giada MaccareseFiumicinoL...

Liechtenstein at the 1956 Winter Olympics

Sporting event delegationLiechtenstein at the1956 Winter OlympicsIOC codeLIENOCLiechtenstein Olympic CommitteeWebsitewww.olympic.li (in German and English)in Cortina d'AmpezzoCompetitors8 (men) in 2 sportsFlag bearerEduard Theodor von Falz-Fein[1]Medals Gold 0 Silver 0 Bronze 0 Total 0 Winter Olympics appearances (overview)193619481952195619601964196819721976198019841988199219941998200220062010201420182022 Liechtenstein competed at the 1956 Winter Olympics in Cortina d'...

 

ATP synthase

ATP synthase (EC 7.1.2.2) là một cấu trúc enzyme được tìm thấy trong vi khuẩn và ti thể hay lục lạp của các sinh vật nhân thực. Cấu trúc này có khả năng tổng hợp adenosine triphosphate (ATP) từ adenosine diphosphate (ADP) và phosphate vô cơ (Pi) đồng thời tích trữ năng lượng cho tế bào. Năng lượng này thường ở dạng proton di chuyển được nhờ chênh lệch hoá thẩm, như từ lumen của thylakoid vào chất n...

 

HD 33579

Star in the constellation Dorado HD 33579 A light curve for HD 33579, plotted from Hipparcos data[1] Observation dataEpoch J2000.0      Equinox J2000.0 Constellation Dorado Right ascension 5h 5m 55.51147s[2] Declination −67° 53′ 10.9330″[2] Apparent magnitude (V) 8.99 - 9.22[3] Characteristics Spectral type A3Ia+[4] U−B color index −0.29[5] B−V color index +0.14[...

Feedback

Process where information about current status is used to influence future status For other uses, see Feedback (disambiguation). Complex systems Topics Self-organizationEmergence Collective behaviorSocial dynamics Collective intelligence Collective action Self-organized criticality Herd mentality Phase transition Agent-based modelling Synchronization Ant colony optimization Particle swarm optimization Swarm behaviour Collective consciousness NetworksScale-free networks Social network analysis...

 

USS Tecumseh (1863)

Canonicus-class monitor For other ships with the same name, see USS Tecumseh. Tecumseh strikes a mine and sinks History United States NameUSS Tecumseh NamesakeTecumseh Ordered15 September 1862 BuilderCharles Secor & Co., Jersey City, New Jersey Laid down1862 Launched12 September 1863 Commissioned19 April 1864 FateSunk during the Battle of Mobile Bay, 5 August 1864 General characteristics TypeCanonicus-class monitor Displacement2,100 long tons (2,134 t) Tons burthen1,034 tons (bm) Len...