text:
ZPP (complexity)

In complexity theory, ZPP (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties:

 * It always returns the correct YES or NO answer.
 * The running time is polynomial in expectation for every input.

In other words, if the algorithm is allowed to flip a truly-random coin while it is running, it will always return the correct answer and, for a problem of size n, there is some polynomial p(n) such that the average running time will be less than p(n), even though it might occasionally be much longer. Such an algorithm is called a Las Vegas algorithm.

Alternatively, ZPP can be defined as the class of problems for which a probabilistic Turing machine exists with these properties: The two definitions are equivalent.
 * It always runs in polynomial time.
 * It returns an answer YES, NO or DO NOT KNOW.
 * The answer is always either DO NOT KNOW or the correct answer.
 * It returns DO NOT KNOW with probability at most 1/2 for every input (and the correct answer otherwise).

The definition of ZPP is based on probabilistic Turing machines, but, for clarity, note that other complexity classes based on them include BPP and RP. The class BQP is based on another machine with randomness: the quantum computer.

Intersection definition
The class ZPP is exactly equal to the intersection of the classes RP and co-RP. This is often taken to be the definition of ZPP. To show this, first note that every problem which is in both RP and co-RP has a Las Vegas algorithm as follows:

 * Suppose we have a language L recognized by both the RP algorithm A and the (possibly completely different) co-RP algorithm B.
 * Given an input, run A on the input for one step. If it returns YES, the answer must be YES. Otherwise, run B on the input for one step. If it returns NO, the answer must be NO. If neither occurs, repeat this step.

Note that only one machine can ever give a wrong answer, and the chance of that machine giving the wrong answer during each repetition is at most 50%. This means that the chance of reaching the kth round shrinks exponentially in k, showing that the expected running time is polynomial. This shows that RP intersect co-RP is contained in ZPP.

To show that ZPP is contained in RP intersect co-RP, suppose we have a Las Vegas algorithm C to solve a problem. We can then construct the following RP algorithm: By Markov's Inequality, the chance that it will yield an answer before we stop it is at least 1/2. This means the chance we'll give the wrong answer on a YES instance, by stopping and yielding NO, is at most 1/2, fitting the definition of an RP algorithm. The co-RP algorithm is identical, except that it gives YES if C "times out".
 * Run C for at least double its expected running time. If it gives an answer, give that answer. If it doesn't give any answer before we stop it, give NO.

Witness and proof
The classes NP, RP and ZPP can be thought of in terms of proof of membership in a set.

Definition: A verifier V for a set X is a Turing machine such that:
 * if x is in X then there exists a string w such that V(x,w) accepts;
 * if x is not in X, then for all strings w, V(x,w) rejects.

The string w can be thought of as the proof of membership. In the case of short proofs (of length bounded by a polynomial in the size of the input) which can be efficiently verified (V is a polynomial-time deterministic Turing machine), the string w is called a witness.

Notes:
 * The definition is very asymmetric. The proof of x being in X is a single string. The proof of x not being in X is the collection of all strings, none of which is a proof of membership.
 * For all x in X there must be a witness to its membership in X.
 * The witness need not be a traditionally construed proof. If V is a probabilistic Turing machine which could possibly accept x if x is in X, then the proof is the string of coin flips which leads the machine to accept x (provided all members in X have some witness and the machine never accepts a non-member).
 * The co-concept is a proof of non-membership, or membership in the complement set.

The classes NP, RP and ZPP are sets which have witnesses for membership. The class NP requires only that witnesses exist. They may be very rare. Of the 2f( possible strings, with f a polynomial, only one need cause the verifier to accept (if x is in X. If x is not in X, no string will cause the verifier to accept).

For the classes RP and ZPP any string chosen at random will likely be a witness.

The corresponding co-classes have witness for non-membership. In particular, co-RP is the class of sets for which, if x is not in X, any randomly chosen string is likely to be a witness for non-membership. ZPP is the class of sets for which any random string is likely to be a witness of x in X, or x not in X, which ever the case may be.

Connecting this definition with other definitions of RP, co-RP and ZPP is easy. The probabilistic polynomial-time Turing Machine V*w(x) corresponds to the deterministic polynomial-time Turing Machine V(x, w) by replacing the random tape of V* with a second input tape for V on which is written the sequence of coin flips. By selecting the witness as a random string, the verifier is a probabilistic polynomial-time Turing Machine whose probability of accepting x when x is in X is large (greater than 1/2, say), but zero if x ∉ X (for RP); of rejecting x when x is not in X is large but zero if x ∈ X (for co-RP); and of correctly accepting or rejecting x as a member of X is large, but zero of incorrectly accepting or rejecting x (for ZPP).

By repeated random selection of a possible witness, the large probability that a random string is a witness gives an expected polynomial time algorithm for accepting or rejecting an input. Conversely, if the Turing Machine is expected polynomial-time (for any given x), then a considerable fraction of the runs must be polynomial-time bounded, and the coin sequence used in such a run will be a witness.

ZPP should be contrasted with BPP. The class BPP does not require witnesses, although witnesses are sufficient (hence BPP contains RP, co-RP and ZPP). A BPP language has V(x,w) accept on a (clear) majority of strings w if x is in X, and conversely reject on a (clear) majority of strings w if x is not in X. No single string w need be definitive, and therefore they cannot in general be considered proofs or witnesses.

Complexity-theoretic properties
It is known that ZPP is closed under complement; that is, ZPP = co-ZPP.

ZPP is low for itself, meaning that a ZPP machine with the power to solve ZPP problems instantly (a ZPP oracle machine) is not any more powerful than the machine without this extra power. In symbols, ZPPZPP = ZPP.

ZPPNP BPP = ZPPNP.

NPBPP is contained in ZPPNP.

Connection to other classes
Since ZPP = RP ∩ coRP, ZPP is obviously contained in both RP and coRP.

The class P is contained in ZPP, and some computer scientists have conjectured that P = ZPP, i.e., every Las Vegas algorithm has a deterministic polynomial-time equivalent.

There exists an oracle relative to which ZPP = EXPTIME. A proof for ZPP = EXPTIME would imply that P ≠ ZPP, as P ≠ EXPTIME (see time hierarchy theorem).

title: ZPP (complexity)


text:
Cherry

A cherry is the fruit of many plants of the genus Prunus, and is a fleshy drupe (stone fruit).

Commercial cherries are obtained from cultivars of several species, such as the sweet Prunus avium and the sour Prunus cerasus. The name 'cherry' also refers to the cherry tree and its wood, and is sometimes applied to almonds and visually similar flowering trees in the genus Prunus, as in "ornamental cherry" or "cherry blossom." Wild cherry may refer to any of the cherry species growing outside cultivation, although Prunus avium is often referred to specifically by the name "wild cherry" in the British Isles.

True cherries
Prunus subg. Cerasus contains species that are typically called cherries. They are known as true cherries and distinguished by having a single winter bud per axil, by having the flowers in small corymbs or umbels of several together (occasionally solitary, e.g. P. serrula; some species with short racemes, e.g. P. maacki), and by having smooth fruit with no obvious groove. Examples of true cherries are:
 * Prunus apetala (Siebold & Zucc.) Franch. & Sav. – clove cherry
 * Prunus avium (L.) L. – sweet cherry, wild cherry, mazzard or gean
 * Prunus campanulata Maxim. – Taiwan cherry, Formosan cherry or bell-flowered cherry
 * Prunus canescens Bois. – grey-leaf cherry
 * Prunus cerasus L. – sour cherry
 * Prunus emarginata (Douglas ex Hook.) Walp. – Oregon cherry or bitter cherry
 * Prunus fruticosa Pall. – European dwarf cherry, dwarf cherry, Mongolian cherry or steppe cherry
 * Prunus incisa Thunb. – Fuji cherry
 * Prunus jamasakura Siebold ex Koidz. – Japanese mountain cherry or Japanese hill cherry
 * Prunus leveilleana (Koidz.) Koehne – Korean mountain cherry
 * Prunus maackii Rupr. – Manchurian cherry or Amur chokecherry
 * Prunus mahaleb L. – Saint Lucie cherry, rock cherry, perfumed cherry or mahaleb cherry
 * Prunus maximowiczii Rupr. – Miyama cherry or Korean cherry
 * Prunus nipponica Matsum. – Takane cherry, peak cherry or Japanese alpine cherry
 * Prunus pensylvanica L.f. – pin cherry, fire cherry, or wild red cherry
 * Prunus pseudocerasus Lindl. – Chinese sour cherry or Chinese cherry
 * Prunus rufa Wall ex Hook.f. – Himalayan cherry
 * Prunus rufoides C.K.Schneid. – tailed-leaf cherry
 * Prunus sargentii Rehder – northern Japanese hill cherry, northern Japanese mountain cherry or Sargent's cherry
 * Prunus serrula Franch. – paperbark cherry, birch bark cherry or Tibetan cherry
 * Prunus serrulata Lindl. – Japanese cherry, hill cherry, Oriental cherry or East Asian cherry
 * Prunus speciosa (Koidz.) Ingram – Oshima cherry
 * Prunus takesimensis Nakai – Ulleungdo cherry
 * Prunus yedoensis Matsum. – Yoshino cherry or Tokyo cherry

Bush cherries
Bush cherries are characterized by having three winter buds per axil. They used to be included in Prunus subg. Cerasus, but phylogenetic research indicates they should be a section of Prunus subg. Prunus. Examples of bush cherries are:
 * Prunus cistena Koehne – purple-leaf sand cherry
 * Prunus humilis Bunge – Chinese plum-cherry or humble bush cherry
 * Prunus japonica Thunb. – Korean cherry
 * Prunus prostrata Labill. – mountain cherry, rock cherry, spreading cherry or prostrate cherry
 * Prunus pumila L. – sand cherry
 * Prunus tomentosa Thunb. – Nanking cherry, Manchu cherry, downy cherry, Shanghai cherry, Ando cherry, mountain cherry, Chinese dwarf cherry, Chinese bush cherry

Bird cherries, cherry laurels, and other racemose cherries
Prunus subg. Padus contains most racemose species that are called cherries which used to be included in the genera Padus (bird cherries), Laurocerasus (cherry laurels), Pygeum (tropical species such as African cherry) and Maddenia. Examples of the racemose cherries are:
 * Prunus africana (Hook.f.) Kalkman – African cherry
 * Prunus caroliniana Aiton – Carolina laurel cherry or laurel cherry
 * Prunus cornuta (Wall. ex Royle) Steud. – Himalayan bird cherry
 * Prunus grayana Maxim. – Japanese bird cherry or Gray's bird cherry
 * Prunus ilicifolia (Nutt. ex Hook. & Arn.) Walp. – hollyleaf cherry, evergreen cherry, holly-leaved cherry or islay
 * Prunus laurocerasus L. – cherry laurel
 * Prunus lyonii (Eastw.) Sarg. – Catalina Island cherry
 * Prunus myrtifolia (L.) Urb. – West Indian cherry
 * Prunus napaulensis (Ser.) Steud. – Nepal bird cherry
 * Prunus occidentalis Sw. – western cherry laurel
 * Prunus padus L. – bird cherry or European bird cherry
 * Prunus pleuradenia Griseb. – Antilles cherry
 * Prunus serotina Ehrh. – black cherry, wild cherry
 * Prunus ssiori F.Schmidt – Hokkaido bird cherry
 * Prunus virginiana L. – chokecherry

Etymology
The English word cherry derives from Old Northern French or Norman cherise from the Latin cerasum, referring to an ancient Greek region, Kerasous (Κερασοῦς) near Giresun, Turkey, from which cherries were first thought to be exported to Europe.

The word "cherry" is also used for some species that bear fruits with similar size and shape even though they are not in the same Prunus genus; some of these species include the "Jamaican cherry" (Muntingia calabura) and the "Spanish cherry" (Mimusops elengi).

Antiquity
The indigenous range of the sweet cherry extends through most of Europe, western Asia, and parts of northern Africa, and the fruit has been consumed throughout its range since prehistoric times. A cultivated cherry is recorded as having been brought to Rome by Lucius Licinius Lucullus from northeastern Anatolia, also known as the Pontus region, in 72 BC.

Cherries were introduced into England at Teynham, near Sittingbourne in Kent, by order of Henry VIII, who had tasted them in Flanders.

Cherries, along with many other fruiting trees and plants, probably first arrived in North America around 1606 in the New France colony of Port Royal, which is modern-day Annapolis Royal, Nova Scotia. Richard Guthrie described in 1629, the "fruitful valley adorned with...great variety of fruit trees, chestnuts, pears, apples, cherries, plums and all other fruits."

Cultivation
The cultivated forms are of the species sweet cherry (P. avium) to which most cherry cultivars belong, and the sour cherry (P. cerasus), which is used mainly for cooking. Both species originate in Europe and western Asia; they usually do not cross-pollinate. Some other species, although having edible fruit, are not grown extensively for consumption, except in northern regions where the two main species will not grow. Irrigation, spraying, labor, and their propensity to damage from rain and hail make cherries relatively expensive. Nonetheless, demand is high for the fruit. In commercial production, sour cherries, as well as sweet cherries sometimes, are harvested by using a mechanized "shaker." Hand picking is also widely used for sweet as well as sour cherries to harvest the fruit to avoid damage to both fruit and trees.

Common rootstocks include Mazzard, Mahaleb, Colt, and Gisela Series, a dwarfing rootstock that produces trees significantly smaller than others, only 8 to 10 feet (2.5 to 3 meters) tall. Sour cherries require no pollenizer, while few sweet varieties are self-fertile.

A cherry tree will take three to four years once it is planted in the orchard to produce its first crop of fruit, and seven years to attain full maturity.

Growing season
Like most temperate-latitude trees, cherry trees require a certain number of chilling hours each year to break dormancy and bloom and produce fruit. The number of chilling hours required depends on the variety. Because of this cold-weather requirement, no members of the genus Prunus can grow in tropical climates. (See "production" section for more information on chilling requirements)

Cherries have a short growing season and can grow in most temperate latitudes. Cherries blossom in April (in the Northern Hemisphere) and the peak season for the cherry harvest is in the summer. In southern Europe in June, in North America in June, in England in mid-July, and in southern British Columbia (Canada) in June to mid-August. In many parts of North America, they are among the first tree fruits to flower and ripen in mid-Spring.

In the Southern Hemisphere, cherries are usually at their peak in late December and are widely associated with Christmas. 'Burlat' is an early variety which ripens during the beginning of December, 'Lapins' ripens near the end of December, and 'Sweetheart' finish slightly later.

Pests and diseases
Generally, the cherry can be a difficult fruit tree to grow and keep alive. In Europe, the first visible pest in the growing season soon after blossom (in April in western Europe) usually is the black cherry aphid ("cherry blackfly," Myzus cerasi), which causes leaves at the tips of branches to curl, with the blackfly colonies exuding a sticky secretion which promotes fungal growth on the leaves and fruit. At the fruiting stage in June/July (Europe), the cherry fruit fly (Rhagoletis cingulata and Rhagoletis cerasi) lays its eggs in the immature fruit, whereafter its larvae feed on the cherry flesh and exit through a small hole (about 1 mm diameter), which in turn is the entry point for fungal infection of the cherry fruit after rainfall. In addition, cherry trees are susceptible to bacterial canker, cytospora canker, brown rot of the fruit, root rot from overly wet soil, crown rot, and several viruses.

Cultivars
The following cultivars have gained the Royal Horticultural Society's Award of Garden Merit:

See cherry blossom and Prunus for ornamental trees.

Production
In 2020, world production of sweet cherries was 2.61 million tonnes, with Turkey producing 28% of this total. Other major producers of sweet cherries were the United States and Chile. World production of sour cherries in 2020 was 1.48 million tonnes, led by Russia, Turkey, Ukraine and Serbia.

Middle East
Major commercial cherry orchards in West Asia are in Turkey, Syria, Lebanon, and Azerbaijan.

Europe
Major commercial cherry orchards in Europe are in Turkey, Italy, Spain and other Mediterranean regions, and to a smaller extent in the Baltic States and southern Scandinavia.

In France since the 1920s, the first cherries of the season come in April/May from the region of Céret (Pyrénées-Orientales), where the local producers send, as a tradition since 1932, the first crate of cherries to the president of the Republic.

North America
In the United States, most sweet cherries are grown in Washington, California, Oregon, Wisconsin, and Michigan. Important sweet cherry cultivars include Bing, Ulster, Rainier, Brooks, Tulare, King, and Sweetheart. Both Oregon and Michigan provide light-colored 'Royal Ann' ('Napoleon'; alternately 'Queen Anne') cherries for the maraschino cherry process. Most sour (also called tart) cherries are grown in Michigan, followed by Utah, New York, and Washington. Sour cherries include 'Nanking' and 'Evans.' Traverse City, Michigan is called the "Cherry Capital of the World", hosting a National Cherry Festival and making the world's largest cherry pie. The specific region of northern Michigan known for tart cherry production is referred to as the "Traverse Bay" region.

Most cherry varieties have a chilling requirement of 800 or more hours, meaning that in order to break dormancy, blossom, and set fruit, the winter season needs to have at least 800 hours where the temperature is below 7 C. "Low chill" varieties requiring 300 hours or less are Minnie Royal and Royal Lee, requiring cross-pollinization, whereas the cultivar, Royal Crimson, is self-fertile. These varieties extend the range of cultivation of cherries to the mild winter areas of southern US. This is a boon to California producers of sweet cherries, as California is the second largest producer of sweet cherries in the US.

Native and non-native sweet cherries grow well in Canada's provinces of Ontario and British Columbia where an annual cherry festival has been celebrated for seven consecutive decades in the Okanagan Valley town of Osoyoos. In addition to the Okanagan, other British Columbia cherry growing regions are the Similkameen Valley and Kootenay Valley, all three regions together producing 5.5 million kg annually or 60% of total Canadian output. Sweet cherry varieties in British Columbia include 'Rainier', 'Van', 'Chelan', 'Lapins', 'Sweetheart', 'Skeena', 'Staccato', 'Christalina' and 'Bing.'

Australia
In Australia, cherries are grown in all the states except for the Northern Territory. The major producing regions are located in the temperate areas within New South Wales, Victoria, South Australia and Tasmania. Western Australia has limited production in the elevated parts in the southwest of the state. Key production areas include Young, Orange and Bathurst in New South Wales, Wandin, the Goulburn and Murray valley areas in Victoria, the Adelaide Hills region in South Australia, and the Huon and Derwent Valleys in Tasmania.

Key commercial varieties in order of seasonality include 'Empress', 'Merchant', 'Supreme', 'Ron's seedling', 'Chelan', 'Ulster', 'Van', 'Bing', 'Stella', 'Nordwunder', 'Lapins', 'Simone', 'Regina', 'Kordia' and 'Sweetheart'. New varieties are being introduced, including the late season 'Staccato' and early season 'Sequoia'. The Australian Cherry Breeding program is developing a series of new varieties which are under testing evaluation.

The New South Wales town of Young is called the "Cherry Capital of Australia" and hosts the National Cherry Festival.

Nutritional value
Raw sweet cherries are 82% water, 16% carbohydrates, 1% protein, and negligible in fat (table). As raw fruit, sweet cherries provide little nutrient content per 100 g serving, as only dietary fiber and vitamin C are present in moderate content, while other vitamins and dietary minerals each supply less than 10% of the Daily Value (DV) per serving, respectively (table).

Compared to sweet cherries, raw sour cherries contain 50% more vitamin C per 100 g (12% DV) and about 20 times more vitamin A (8% DV), beta-Carotene in particular (table).

Health risks
The cherry kernels, accessible by chewing or breaking the hard-shelled cherry pits, contain amygdalin, a chemical that releases the toxic compound hydrogen cyanide when ingested. The amount of amygdalin in each cherry varies widely, and symptoms would show only after eating several crushed pits (3–4 of the Morello variety or 7–9 of the red or black varieties). Swallowing the pits whole normally causes no complications.

Other uses
Cherry wood is valued for its rich color and straight grain in manufacturing fine furniture, particularly desks, tables and chairs.

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/

title: Cherry


text:
93 BC

Year 93 BC was a year of the pre-Julian Roman calendar. At the time it was known as the Year of the Consulship of Flaccus and Herennius (or, less frequently, year 661 Ab urbe condita). The denomination 93 BC for this year has been used since the early medieval period, when the Anno Domini calendar era became the prevalent method in Europe for naming years.

Roman republic

 * Roman consuls: Gaius Valerius Flaccus and Marcus Herennius.

Asia Minor

 * Ariobarzanes I Philoromaios becomes king of Cappadocia with Roman backing.
 * Arshak I becomes king of Caucasian Iberia after overthrowing Farnadjom.

Asia

 * End of era Taishi of Emperor Wu of Han China.

Births

 * Publius Clodius Pulcher, Roman politician (d. 52 BC)

Deaths

 * Antiochus XI, king of the Seleucid Empire
 * Farnadjom, king of Caucasian Iberia

title: 93 BC


text:
94 BC

Year 94 BC was a year of the pre-Julian Roman calendar. At the time it was known as the Year of the Consulship of Caldus and Ahenobarbus (or, less frequently, year 660 Ab urbe condita) and the Third Year of Taishi.

Anatolia

 * Approximate date – Nicomedes IV succeeds his father Nicomedes III as king of Bithynia.

India

 * The Shakas start to control northwest India.

Roman Republic

 * Consuls: Gaius Coelius Caldus and Lucius Domitius Ahenobarbus.
 * The first (failed) attempt to open a Latin rhetorical school.
 * Lucius Cornelius Sulla is elected praetor urbanus.

Births

 * Zhao of Han, Chinese emperor (d. 74 BC)

title: 94 BC


text:
90 BC

Year 90 BC was a year of the pre-Julian Roman calendar. At the time it was known as the Year of the Consulship of Caesar and Lupus (or, less frequently, year 664 Ab urbe condita) and the Third Year of Zhenghe. The denomination 90 BC for this year has been used since the early medieval period, when the Anno Domini calendar era became the prevalent method in Europe for naming years.

Roman Republic

 * Consuls: Lucius Julius Caesar and Publius Rutilius Lupus.
 * Social War continues: Pompeius Strabo and Gaius Marius distinguish themselves.
 * The Etruscans are granted Roman citizenship.
 * Corfinium in south-central Italy is the center of a rebellion against Rome.
 * The Lex Iulia grants citizenship to all Italians who did not oppose Rome during the Social War.
 * Cicero starts to serve in the Roman army.

Asia Minor

 * Nicomedes IV of Bithynia is defeated in battle by a coalition of Nicomedes' brother Socrates, and Mithridates VI of Pontus. Nicomedes flees to Rome.

China

 * The Xiongnu invade the Prefectures of Wuyuan and Jiuquan and kill the commandants of both Prefectures.
 * Emperor Wu of Han sends three armies against the Xiongnu under General-in-Chief Li Guangli, Ma Tong and Shang Qiucheng, marching from Wuyuan, Jiuqian and Xihe respectively. An army of Central Asian vassals of Han, under Cheng Mian, captures the king of the vassal state of Jushi, who is suspected of treachery. The Xiongnu General-in-Chief and the former Han general Li Ling fight indecisively against Shang's army.
 * Li Guangli and his in-law Prime Minister Liu Qumao seek to recommend Liu Bo, Li Guangli's nephew, as the new Crown Prince, and while Li Guangli is on campaign, Liu Qumao and his wife are executed and Li Guangli's wife imprisoned, having been charged with cursing the emperor and seeking to replace him with Liu Bo.
 * Wishing to please the emperor, Li Guangli and his 70,000 men penetrate as far as the Selenga River. A detachment crosses the river and defeats an army of 20,000 under the Xiongnu Left General-in-Chief, who is killed. However, Li Guangli is then defeated by Hulugu Chanyu's army of 50,000 in the Khangai Mountains and surrenders. Li Guangli marries Hulugu's daughter, and Emperor Wu exterminates Li's clan.

Births

 * Aulus Hirtius, Roman politician and historian (d. 43 BC)
 * Diodorus Siculus, Greek historian (approximate date)
 * Pasherienptah III, Egyptian high priest (d. 41 BC)

Deaths

 * Antiochus X Eusebes, Seleucid king (approximate date)
 * Dionysios Trax, Greek grammarian (b. 170 BC)
 * Li Yannian, Chinese musician (executed by Wu of Han)
 * Pharnajom, king of Iberia (modern Georgia)

title: 90 BC


text:
92 BC

Year 92 BC was a year of the pre-Julian Roman calendar. At the time it was known as the Year of the Consulship of Pulcher and Perperna (or, less frequently, year 662 Ab urbe condita) and the First Year of Zhenghe. The denomination 92 BC for this year has been used since the early medieval period, when the Anno Domini calendar era became the prevalent method in Europe for naming years.

Roman Republic

 * Consuls: Gaius Claudius Pulcher and Marcus Perperna.
 * In the first diplomatic contact between Rome and Parthia, Sulla meets with a Parthian envoy, resulting in the parties recognizing the Euphrates as a common frontier.
 * Sulla repulses Tigranes of Armenia from Cappadocia.
 * Gaius Sentius becomes Roman governor of Macedonia. He serves until 88 BC.

Levant

 * 92 BC Levant earthquake, earthquake mentioned in catalogues of historical earthquakes. An earthquake and a tsunami reportedly affected areas of the Levant, including the modern states of Cyprus, Egypt, Israel, and Syria.

Deaths

 * Antiochus XI Epiphanes, king of the Greek Seleucid Empire, drowned

title: 92 BC


text:
91 BC

Year 91 BC was a year of the pre-Julian Roman calendar. At the time it was known as the Year of the Consulship of Philippus and Caesar (or, less frequently, year 663 Ab urbe condita) and the Second Year of Zhenghe. The denomination 91 BC for this year has been used since the early medieval period, when the Anno Domini calendar era became the prevalent method in Europe for naming years.

Roman Republic

 * Consuls: Sextus Julius Caesar and Lucius Marcius Philippus.
 * The tribune Marcus Livius Drusus proposes extending Roman citizenship to allied Italian cities, but is assassinated, leading to the Social War.

China

 * Witchcraft Trials
 * Emperor Wu of Han executes Prime Minister Gongsun He (the brother-in-law of Empress Wei Zifu) and his clan because Gongsun's son is accused of adultery with the emperor's daughter Princess Yangshi and witchcraft.
 * Following further accusations of witchcraft, the emperor executes hundreds of imperial officials and concubines.
 * After convincing the emperor that his ill health is caused by witchcraft, the prosecutor Jiang Chong is given charge of investigating the matter. People accuse each other of witchcraft, and tens of thousands are executed across China, including former generals Zhao Ponu and Gongsun Ao.

 * 'Rebellion' of Liu Ju
 * July - After Jiang Chong frames Crown Prince Liu Ju of witchcraft and prevents communication between the prince and his father, Liu Ju kills Jiang, former general Han Yue and their followers. Due to miscommunication, the emperor misinterprets this as a rebellion against himself, and he orders Prime Minister Liu Qumao to march against Liu Ju.
 * After being defeated in Chang'an, Liu Ju and his mother, Empress Wei Zifu, commit suicide. Emperor Wu exterminates the followers of Liu Ju and their families.
 * Learning that the charges against Liu Ju were fabricated, Emperor Wu orders further executions.

 * September - The Xiongnu invade the prefectures of Shanggu and Wuyuan.

Births

 * Xuan of Han, emperor of the Han dynasty (d. 49 BC)

Deaths

 * Liu Ju, crown prince of the Han dynasty (b. 128 BC)
 * Lucius Licinius Crassus, Roman consul (b. 140 BC)
 * Marcus Livius Drusus, Roman politician
 * Quintus Caecilius Metellus Numidicus, Roman politician
 * Wei Zifu, empress of the Han dynasty

title: 91 BC


text:
87 BC

Year 87 BC was a year of the pre-Julian Roman calendar. At the time it was known as the Year of the Consulship of Octavius and Cinna/Merula (or, less frequently, year 667 Ab urbe condita) and the Second Year of Houyuan. The denomination 87 BC for this year has been used since the early medieval period, when the Anno Domini calendar era became the prevalent method in Europe for naming years.

Roman Republic

 * Lucius Cornelius Cinna is elected consul of Rome, thus returning the rule of Rome back to the populares faction.
 * Sulla arrives in Greece and besieges Athens. He orders Lucius Licinius Lucullus to raise a fleet from Rome's allies around the eastern Mediterranean.
 * Ostia is razed by Gaius Marius as he comes back from Africa with an army to take Rome by force.

China

 * March 29 – Emperor Wu of Han dies after a 54-year reign in which he leads the Han dynasty (China) through its greatest expansion. The Empire's borders span from modern Kyrgyzstan in the west, to Mongolia in the north, to Korea in the east, and to northern Vietnam in the south.
 * March 30 – The eight-year-old Liu Fuling becomes emperor, with Huo Guang General-in-Chief and regent.

Technology

 * Antikythera mechanism manufactured.

Births

 * Lucius Munatius Plancus, Roman consul (approximate date)

Deaths

 * March 29 – Han Wudi, emperor of the Han dynasty (b. 157 BC)
 * Apollodorus of Artemita, Greek writer
 * Gaius Atilius Serranus, Roman consul and senator
 * Gaius Julius Caesar Strabo, Roman politician
 * Gnaeus Pompeius Strabo, Roman general and politician
 * Gotarzes I, ruler (shah) of the Parthian Empire
 * Lucius Cornelius Merula, Roman politician and priest
 * Lucius Julius Caesar, Roman consul (killed by partisans of Gaius Marius)
 * Marcus Antonius, Roman consul (executed by order of Marius and Cinna)
 * Publius Licinius Crassus, Roman consul and censor (killed by Marians invading Rome)
 * Quintus Ancharius, Roman politician (executed by order of Marius and Cinna)

title: 87 BC


text:
89 BC

Year 89 BC was a year of the pre-Julian Roman calendar. At the time it was known as the Year of the Consulship of Strabo and Cato (or, less frequently, year 665 Ab urbe condita) and the Fourth Year of Zhenghe. The denomination 89 BC for this year has been used since the early medieval period, when the Anno Domini calendar era became the prevalent method in Europe for naming years.

Roman Republic

 * Consuls: Gnaeus Pompeius Strabo and Lucius Porcius Cato.
 * Social War:
 * Roman forces under Lucius Porcius Cato are defeated by the Italian rebels in the Battle of Fucine Lake, Cato is killed.
 * The Roman army of Gnaeus Pompeius Strabo decisively defeats the rebels in the Battle of Asculum.
 * Lex Plautia Papiria extends citizenship to all Italians who applied for it within 60 days. The new citizens are enrolled in eight designated tribes, to prevent domination of the assemblies.
 * Lex Pompeia grants Latin rights to cities in Cisalpine Gaul.
 * Pompeii is annexed by the Roman Republic.
 * Cicero ends his service in the Roman army.

Asia Minor

 * Mithridates VI of Pontus invades Bithynia and Cappadocia, thus beginning the First Mithridatic War.

Xiongnu

 * The former Han General-in-Chief Li Guangli, now the son-in-law of Hulugu Chanyu, is arrested and sacrificed to the gods to restore the health of Hulugu's mother.

Births

 * Empress Shangguan, wife to Emperor Zhao of Han (d. 37 BC)

Deaths

 * Aulus Sempronius Asellio, Roman praetor (murdered by creditors)
 * Lucius Porcius Cato, Roman politician and general
 * Marcus Aemilius Scaurus, Roman politician (b. c. 163 BC)
 * Titus Didius, killed in battle during the Social War
 * Li Guangli, Chinese General-in-Chief (Han dynasty)

title: 89 BC


text:
88 BC

Year 88 BC was a year of the pre-Julian Roman calendar. At the time it was known as the Year of the Consulship of Sulla and Rufus (or, less frequently, year 666 Ab urbe condita) and the First Year of Houyuan. The denomination 88 BC for this year has been used since the early medieval period, when the Anno Domini calendar era became the prevalent method in Europe for naming years.

Roman Republic

 * The Social War ends with the defeat of the Italian allies by the Romans.
 * August: The consul Lucius Cornelius Sulla becomes the first Roman commander to march on Rome with his army and to capture the city by force. This extraordinary act is prompted by his desire to maintain his proconsular command for the First Mithridatic War in Asia Minor. Sulla then murdered his enemy P. Sulpicius Rufus and forced Gaius Marius to flee to Africa.
 * The Dardani, Scordisci, and the Maedi attack the Roman province of Macedonia.

Greece

 * May – King Mithridates VI of Pontus invades Greece. Defeating the Roman forces four times in succession, he conquers Bithynia, Phrygia, Mysia, Lycia, Pamphylia, Ionia and Cappadocia. The Roman province of Asia is dismantled. On the king's orders, the local authorities in every city of the province round up and put to death all resident Italians in a single day (App.Mith.§§85–91). Plutarch (Sulla 24.4) says that 150,000 are killed, other sources calculate a figure of 80,000 people.

China

 * Emperor Wu of Han makes preparations for the six-year-old Liu Fuling to be made Crown Prince and establishes Huo Guang as the future regent. The emperor executes Fuling's mother Lady Gouyi so that she cannot dominate the state while Fuling is a child emperor.

Deaths

 * Demetrius III Eucaerus, king of the Seleucid Empire
 * Gnaeus Domitius Ahenobarbus, Roman consul
 * Lady Gouyi, mother of Zhao of Han (b. 113)
 * Manius Aquillius, Roman consul and general
 * Ptolemy X Alexander I, king (pharaoh) of Egypt
 * Publius Sulpicius Rufus, Roman tribune of the plebs, murdered by Sulla
 * Quintus Mucius Scaevola Augur, Roman consul
 * Quintus Poppaedius Silo, Italian tribe leader

title: 88 BC


text:
Music theory

Music theory is the study of the practices and possibilities of music. The Oxford Companion to Music describes three interrelated uses of the term "music theory": The first is the "rudiments", that are needed to understand music notation (key signatures, time signatures, and rhythmic notation); the second is learning scholars' views on music from antiquity to the present; the third is a sub-topic of musicology that "seeks to define processes and general principles in music". The musicological approach to theory differs from music analysis "in that it takes as its starting-point not the individual work or performance but the fundamental materials from which it is built."

Music theory is frequently concerned with describing how musicians and composers make music, including tuning systems and composition methods among other topics. Because of the ever-expanding conception of what constitutes music, a more inclusive definition could be the consideration of any sonic phenomena, including silence. This is not an absolute guideline, however; for example, the study of "music" in the Quadrivium liberal arts university curriculum, that was common in medieval Europe, was an abstract system of proportions that was carefully studied at a distance from actual musical practice. But this medieval discipline became the basis for tuning systems in later centuries and is generally included in modern scholarship on the history of music theory.

Music theory as a practical discipline encompasses the methods and concepts that composers and other musicians use in creating and performing music. The development, preservation, and transmission of music theory in this sense may be found in oral and written music-making traditions, musical instruments, and other artifacts. For example, ancient instruments from prehistoric sites around the world reveal details about the music they produced and potentially something of the musical theory that might have been used by their makers. In ancient and living cultures around the world, the deep and long roots of music theory are visible in instruments, oral traditions, and current music-making. Many cultures have also considered music theory in more formal ways such as written treatises and music notation. Practical and scholarly traditions overlap, as many practical treatises about music place themselves within a tradition of other treatises, which are cited regularly just as scholarly writing cites earlier research.

In modern academia, music theory is a subfield of musicology, the wider study of musical cultures and history. Music theory is often concerned with abstract musical aspects such as tuning and tonal systems, scales, consonance and dissonance, and rhythmic relationships. In addition, there is also a body of theory concerning practical aspects, such as the creation or the performance of music, orchestration, ornamentation, improvisation, and electronic sound production. A person who researches or teaches music theory is a music theorist. University study, typically to the MA or PhD level, is required to teach as a tenure-track music theorist in a US or Canadian university. Methods of analysis include mathematics, graphic analysis, and especially analysis enabled by western music notation. Comparative, descriptive, statistical, and other methods are also used. Music theory textbooks, especially in the United States of America, often include elements of musical acoustics, considerations of musical notation, and techniques of tonal composition (harmony and counterpoint), among other topics.

Mesopotamia
Several surviving Sumerian and Akkadian clay tablets include musical information of a theoretical nature, mainly lists of intervals and tunings. The scholar Sam Mirelman reports that the earliest of these texts dates from before 1500 BCE, a millennium earlier than surviving evidence from any other culture of comparable musical thought. Further, "All the Mesopotamian texts [about music] are united by the use of a terminology for music that, according to the approximate dating of the texts, was in use for over 1,000 years."

China
Much of Chinese music history and theory remains unclear.

Chinese theory starts from numbers, the main musical numbers being twelve, five and eight. Twelve refers to the number of pitches on which the scales can be constructed. The Lüshi chunqiu from about 238 BCE recalls the legend of Ling Lun. On order of the Yellow Emperor, Ling Lun collected twelve bamboo lengths with thick and even nodes. Blowing on one of these like a pipe, he found its sound agreeable and named it huangzhong, the "Yellow Bell." He then heard phoenixes singing. The male and female phoenix each sang six tones. Ling Lun cut his bamboo pipes to match the pitches of the phoenixes, producing twelve pitch pipes in two sets: six from the male phoenix and six from the female: these were called the lülü or later the shierlü.

"Apart from technical and structural aspects, ancient Chinese music theory also discusses topics such as the nature and functions of music. The Yueji ('Record of music', c1st and 2nd centuries BCE), for example, manifests Confucian moral theories of understanding music in its social context. Studied and implemented by Confucian scholar-officials [...], these theories helped form a musical Confucianism that overshadowed but did not erase rival approaches. These include the assertion of Mozi (c. 468 – c. 376 BCE) that music wasted human and material resources, and Laozi's claim that the greatest music had no sounds. [...] Even the music of the qin zither, a genre closely affiliated with Confucian scholar-officials, includes many works with Daoist references, such as Tianfeng huanpei ('Heavenly Breeze and Sounds of Jade Pendants')."

India
The Samaveda and Yajurveda (c. 1200 – 1000 BCE) are among the earliest testimonies of Indian music, but properly speaking, they contain no theory. The Natya Shastra, written between 200 BCE to 200 CE, discusses intervals (Śrutis), scales (Grāmas), consonances and dissonances, classes of melodic structure (Mūrchanās, modes?), melodic types (Jātis), instruments, etc.

Greece
Early preserved Greek writings on music theory include two types of works: Several names of theorists are known before these works, including Pythagoras (c. 570 ~ c. 495), Philolaus (c. 470 ~ (c. 385), Archytas (428–347), and others.
 * technical manuals describing the Greek musical system including notation, scales, consonance and dissonance, rhythm, and types of musical compositions;
 * treatises on the way in which music reveals universal patterns of order leading to the highest levels of knowledge and understanding.

Works of the first type (technical manuals) include

More philosophical treatises of the second type include

China
The pipa instrument carried with it a theory of musical modes that subsequently led to the Sui and Tang theory of 84 musical modes.

Arabic countries / Persian countries
Medieval Arabic music theorists include:

 * Abū Yūsuf Ya'qūb al-Kindi (Bagdad, 873 CE), who uses the first twelve letters of the alphabet to describe the twelve frets on five strings of the oud, producing a chromatic scale of 25 degrees.

 * [Yaḥyā ibn] al-Munajjim (Baghdad, 856–912), author of Risāla fī al-mūsīqī ("Treatise on music", MS GB-Lbl Oriental 2361) which describes a Pythagorean tuning of the oud and a system of eight modes perhaps inspired by Ishaq al-Mawsili (767–850).

 * Abū n-Nașr Muḥammad al-Fārābi (Persia, 872? – Damas, 950 or 951 CE), author of Kitab al-Musiqa al-Kabir ("The Great Book of Music").

 * 'Ali ibn al-Husayn ul-Isfahānī (897–967), known as Abu al-Faraj al-Isfahani, author of Kitāb al-Aghānī ("The Book of Songs").

 * Abū 'Alī al-Ḥusayn ibn ʿAbd-Allāh ibn Sīnā, known as Avicenna (c. 980 – 1037), whose contribution to music theory consists mainly in Chapter 12 of the section on mathematics of his Kitab Al-Shifa ("The Book of Healing").

 * al-Ḥasan ibn Aḥmad ibn 'Ali al-Kātib, author of Kamāl adab al Ghinā' ("The Perfection of Musical Knowledge"), copied in 1225 (Istanbul, Topkapi Museum, Ms 1727).

 * Safi al-Din al-Urmawi (1216–1294 CE), author of the Kitabu al-Adwār ("Treatise of musical cycles") and ar-Risālah aš-Šarafiyyah ("Epistle to Šaraf").

 * Mubārak Šāh, commentator of Safi al-Din's Kitāb al-Adwār (British Museum, Ms 823).

 * Anon. LXI, Anonymous commentary on Safi al-Din's Kitāb al-Adwār.

 * Shams al-dῑn al-Saydᾱwῑ Al-Dhahabῑ (14th century CE (?)), music theorist. Author of Urjῡza fi'l-mῡsῑqᾱ ("A Didactic Poem on Music").

Europe
The Latin treatise De institutione musica by the Roman philosopher Boethius (written c. 500, translated as Fundamentals of Music) was a touchstone for other writings on music in medieval Europe. Boethius represented Classical authority on music during the Middle Ages, as the Greek writings on which he based his work were not read or translated by later Europeans until the 15th century. This treatise carefully maintains distance from the actual practice of music, focusing mostly on the mathematical proportions involved in tuning systems and on the moral character of particular modes. Several centuries later, treatises began to appear which dealt with the actual composition of pieces of music in the plainchant tradition. At the end of the ninth century, Hucbald worked towards more precise pitch notation for the neumes used to record plainchant.

Guido d'Arezzo wrote a letter to Michael of Pomposa in 1028, entitled Epistola de ignoto cantu, in which he introduced the practice of using syllables to describe notes and intervals. This was the source of the hexachordal solmization that was to be used until the end of the Middle Ages. Guido also wrote about emotional qualities of the modes, the phrase structure of plainchant, the temporal meaning of the neumes, etc.; his chapters on polyphony "come closer to describing and illustrating real music than any previous account" in the Western tradition.

During the thirteenth century, a new rhythm system called mensural notation grew out of an earlier, more limited method of notating rhythms in terms of fixed repetitive patterns, the so-called rhythmic modes, which were developed in France around 1200. An early form of mensural notation was first described and codified in the treatise Ars cantus mensurabilis ("The art of measured chant") by Franco of Cologne (c. 1280). Mensural notation used different note shapes to specify different durations, allowing scribes to capture rhythms which varied instead of repeating the same fixed pattern; it is a proportional notation, in the sense that each note value is equal to two or three times the shorter value, or half or a third of the longer value. This same notation, transformed through various extensions and improvements during the Renaissance, forms the basis for rhythmic notation in European classical music today.

Middle Eastern and Central Asian countries

 * Bāqiyā Nāyinῑ (Uzbekistan, 17th century CE), Uzbek author and music theorist. Author of Zamzama e wahdat-i-mῡsῑqῑ ["The Chanting of Unity in Music"].

 * Baron Francois Rodolphe d'Erlanger (Tunis, Tunisia, 1910–1932 CE), French musicologist. Author of La musique arabe and Ta'rῑkh al-mῡsῑqᾱ al-arabiyya wa-usῡluha wa-tatawwurᾱtuha ["A History of Arabian Music, its principles and its Development"]

D'Erlanger divulges that the Arabic music scale is derived from the Greek music scale, and that Arabic music is connected to certain features of Arabic culture, such as astrology.

Europe

 * Renaissance

 * Baroque

 * 1750–1900
 * As Western musical influence spread throughout the world in the 1800s, musicians adopted Western theory as an international standard—but other theoretical traditions in both textual and oral traditions remain in use. For example, the long and rich musical traditions unique to ancient and current cultures of Africa are primarily oral, but describe specific forms, genres, performance practices, tunings, and other aspects of music theory.
 * Sacred harp music uses a different kind of scale and theory in practice. The music focuses on the solfege "fa, sol, la" on the music scale. Sacred Harp also employs a different notation involving "shape notes", or notes that are shaped to correspond to a certain solfege syllable on the music scale. Sacred Harp music and its music theory originated with Reverend Thomas Symmes in 1720, where he developed a system for "singing by note" to help his church members with note accuracy.

Fundamentals of music
Music is composed of aural phenomena; "music theory" considers how those phenomena apply in music. Music theory considers melody, rhythm, counterpoint, harmony, form, tonal systems, scales, tuning, intervals, consonance, dissonance, durational proportions, the acoustics of pitch systems, composition, performance, orchestration, ornamentation, improvisation, electronic sound production, etc.

Pitch
Pitch is the lowness or highness of a tone, for example the difference between middle C and a higher C. The frequency of the sound waves producing a pitch can be measured precisely, but the perception of pitch is more complex because single notes from natural sources are usually a complex mix of many frequencies. Accordingly, theorists often describe pitch as a subjective sensation rather than an objective measurement of sound.

Specific frequencies are often assigned letter names. Today most orchestras assign concert A (the A above middle C on the piano) to the frequency of 440 Hz. This assignment is somewhat arbitrary; for example, in 1859 France, the same A was tuned to 435 Hz. Such differences can have a noticeable effect on the timbre of instruments and other phenomena. Thus, in historically informed performance of older music, tuning is often set to match the tuning used in the period when it was written. Additionally, many cultures do not attempt to standardize pitch, often considering that it should be allowed to vary depending on genre, style, mood, etc.

The difference in pitch between two notes is called an interval. The most basic interval is the unison, which is simply two notes of the same pitch. The octave interval is two pitches that are either double or half the frequency of one another. The unique characteristics of octaves gave rise to the concept of pitch class: pitches of the same letter name that occur in different octaves may be grouped into a single "class" by ignoring the difference in octave. For example, a high C and a low C are members of the same pitch class—the class that contains all C's.

Musical tuning systems, or temperaments, determine the precise size of intervals. Tuning systems vary widely within and between world cultures. In Western culture, there have long been several competing tuning systems, all with different qualities. Internationally, the system known as equal temperament is most commonly used today because it is considered the most satisfactory compromise that allows instruments of fixed tuning (e.g. the piano) to sound acceptably in tune in all keys.

Scales and modes
Notes can be arranged in a variety of scales and modes. Western music theory generally divides the octave into a series of twelve pitches, called a chromatic scale, within which the interval between adjacent tones is called a semitone, or half step. Selecting tones from this set of 12 and arranging them in patterns of semitones and whole tones creates other scales.

The most commonly encountered scales are the seven-toned major, the harmonic minor, the melodic minor, and the natural minor. Other examples of scales are the octatonic scale and the pentatonic or five-tone scale, which is common in folk music and blues. Non-Western cultures often use scales that do not correspond with an equally divided twelve-tone division of the octave. For example, classical Ottoman, Persian, Indian and Arabic musical systems often make use of multiples of quarter tones (half the size of a semitone, as the name indicates), for instance in 'neutral' seconds (three quarter tones) or 'neutral' thirds (seven quarter tones)—they do not normally use the quarter tone itself as a direct interval.

In traditional Western notation, the scale used for a composition is usually indicated by a key signature at the beginning to designate the pitches that make up that scale. As the music progresses, the pitches used may change and introduce a different scale. Music can be transposed from one scale to another for various purposes, often to accommodate the range of a vocalist. Such transposition raises or lowers the overall pitch range, but preserves the intervallic relationships of the original scale. For example, transposition from the key of C major to D major raises all pitches of the scale of C major equally by a whole tone. Since the interval relationships remain unchanged, transposition may be unnoticed by a listener, however other qualities may change noticeably because transposition changes the relationship of the overall pitch range compared to the range of the instruments or voices that perform the music. This often affects the music's overall sound, as well as having technical implications for the performers.

The interrelationship of the keys most commonly used in Western tonal music is conveniently shown by the circle of fifths. Unique key signatures are also sometimes devised for a particular composition. During the Baroque period, emotional associations with specific keys, known as the doctrine of the affections, were an important topic in music theory, but the unique tonal colorings of keys that gave rise to that doctrine were largely erased with the adoption of equal temperament. However, many musicians continue to feel that certain keys are more appropriate to certain emotions than others. Indian classical music theory continues to strongly associate keys with emotional states, times of day, and other extra-musical concepts and notably, does not employ equal temperament.

Consonance and dissonance
Consonance and dissonance are subjective qualities of the sonority of intervals that vary widely in different cultures and over the ages. Consonance (or concord) is the quality of an interval or chord that seems stable and complete in itself. Dissonance (or discord) is the opposite in that it feels incomplete and "wants to" resolve to a consonant interval. Dissonant intervals seem to clash. Consonant intervals seem to sound comfortable together. Commonly, perfect fourths, fifths, and octaves and all major and minor thirds and sixths are considered consonant. All others are dissonant to a greater or lesser degree.

Context and many other aspects can affect apparent dissonance and consonance. For example, in a Debussy prelude, a major second may sound stable and consonant, while the same interval may sound dissonant in a Bach fugue. In the Common practice era, the perfect fourth is considered dissonant when not supported by a lower third or fifth. Since the early 20th century, Arnold Schoenberg's concept of "emancipated" dissonance, in which traditionally dissonant intervals can be treated as "higher," more remote consonances, has become more widely accepted.

Rhythm
Rhythm is produced by the sequential arrangement of sounds and silences in time. Meter measures music in regular pulse groupings, called measures or bars. The time signature or meter signature specifies how many beats are in a measure, and which value of written note is counted or felt as a single beat.

Through increased stress, or variations in duration or articulation, particular tones may be accented. There are conventions in most musical traditions for regular and hierarchical accentuation of beats to reinforce a given meter. Syncopated rhythms contradict those conventions by accenting unexpected parts of the beat. Playing simultaneous rhythms in more than one time signature is called polyrhythm.

In recent years, rhythm and meter have become an important area of research among music scholars. The most highly cited of these recent scholars are Maury Yeston, Fred Lerdahl and Ray Jackendoff, Jonathan Kramer, and Justin London.

Melody
A melody is a group of musical sounds in agreeable succession or arrangement. Because melody is such a prominent aspect in so much music, its construction and other qualities are a primary interest of music theory.

The basic elements of melody are pitch, duration, rhythm, and tempo. The tones of a melody are usually drawn from pitch systems such as scales or modes. Melody may consist, to increasing degree, of the figure, motive, semi-phrase, antecedent and consequent phrase, and period or sentence. The period may be considered the complete melody, however some examples combine two periods, or use other combinations of constituents to create larger form melodies.

Chord
A chord, in music, is any harmonic set of three or more notes that is heard as if sounding simultaneously. These need not actually be played together: arpeggios and broken chords may, for many practical and theoretical purposes, constitute chords. Chords and sequences of chords are frequently used in modern Western, West African, and Oceanian music, whereas they are absent from the music of many other parts of the world.

The most frequently encountered chords are triads, so called because they consist of three distinct notes: further notes may be added to give seventh chords, extended chords, or added tone chords. The most common chords are the major and minor triads and then the augmented and diminished triads. The descriptions major, minor, augmented, and diminished are sometimes referred to collectively as chordal quality. Chords are also commonly classed by their root note—so, for instance, the chord C major may be described as a triad of major quality built on the note C. Chords may also be classified by inversion, the order in which the notes are stacked.

A series of chords is called a chord progression. Although any chord may in principle be followed by any other chord, certain patterns of chords have been accepted as establishing key in common-practice harmony. To describe this, chords are numbered, using Roman numerals (upward from the key-note), per their diatonic function. Common ways of notating or representing chords in western music other than conventional staff notation include Roman numerals, figured bass (much used in the Baroque era), chord letters (sometimes used in modern musicology), and various systems of chord charts typically found in the lead sheets used in popular music to lay out the sequence of chords so that the musician may play accompaniment chords or improvise a solo.

Harmony
In music, harmony is the use of simultaneous pitches (tones, notes), or chords. The study of harmony involves chords and their construction and chord progressions and the principles of connection that govern them. Harmony is often said to refer to the "vertical" aspect of music, as distinguished from melodic line, or the "horizontal" aspect. Counterpoint, which refers to the interweaving of melodic lines, and polyphony, which refers to the relationship of separate independent voices, is thus sometimes distinguished from harmony.

In popular and jazz harmony, chords are named by their root plus various terms and characters indicating their qualities. For example, a lead sheet may indicate chords such as C major, D minor, and G dominant seventh. In many types of music, notably Baroque, Romantic, modern, and jazz, chords are often augmented with "tensions". A tension is an additional chord member that creates a relatively dissonant interval in relation to the bass. It is part of a chord, but is not one of the chord tones (1 3 5 7). Typically, in the classical common practice period a dissonant chord (chord with tension) "resolves" to a consonant chord. Harmonization usually sounds pleasant to the ear when there is a balance between the consonant and dissonant sounds. In simple words, that occurs when there is a balance between "tense" and "relaxed" moments.

Timbre
Timbre, sometimes called "color", or "tone color," is the principal phenomenon that allows us to distinguish one instrument from another when both play at the same pitch and volume, a quality of a voice or instrument often described in terms like bright, dull, shrill, etc. It is of considerable interest in music theory, especially because it is one component of music that has as yet, no standardized nomenclature. It has been called "... the psychoacoustician's multidimensional waste-basket category for everything that cannot be labeled pitch or loudness," but can be accurately described and analyzed by Fourier analysis and other methods because it results from the combination of all sound frequencies, attack and release envelopes, and other qualities that a tone comprises.

Timbre is principally determined by two things: (1) the relative balance of overtones produced by a given instrument due its construction (e.g. shape, material), and (2) the envelope of the sound (including changes in the overtone structure over time). Timbre varies widely between different instruments, voices, and to lesser degree, between instruments of the same type due to variations in their construction, and significantly, the performer's technique. The timbre of most instruments can be changed by employing different techniques while playing. For example, the timbre of a trumpet changes when a mute is inserted into the bell, the player changes their embouchure, or volume.

A voice can change its timbre by the way the performer manipulates their vocal apparatus, (e.g. the shape of the vocal cavity or mouth). Musical notation frequently specifies alteration in timbre by changes in sounding technique, volume, accent, and other means. These are indicated variously by symbolic and verbal instruction. For example, the word dolce (sweetly) indicates a non-specific, but commonly understood soft and "sweet" timbre. Sul tasto instructs a string player to bow near or over the fingerboard to produce a less brilliant sound. Cuivre instructs a brass player to produce a forced and stridently brassy sound. Accent symbols like marcato (^) and dynamic indications (pp) can also indicate changes in timbre.

Dynamics
In music, "dynamics" normally refers to variations of intensity or volume, as may be measured by physicists and audio engineers in decibels or phons. In music notation, however, dynamics are not treated as absolute values, but as relative ones. Because they are usually measured subjectively, there are factors besides amplitude that affect the performance or perception of intensity, such as timbre, vibrato, and articulation.

The conventional indications of dynamics are abbreviations for Italian words like forte (f) for loud and piano (p) for soft. These two basic notations are modified by indications including mezzo piano (mp) for moderately soft (literally "half soft") and mezzo forte (mf) for moderately loud, sforzando or sforzato (sfz) for a surging or "pushed" attack, or fortepiano (fp) for a loud attack with a sudden decrease to a soft level. The full span of these markings usually range from a nearly inaudible pianissississimo (pppp) to a loud-as-possible fortissississimo (ffff).

Greater extremes of pppppp and fffff and nuances such as p+ or più piano are sometimes found. Other systems of indicating volume are also used in both notation and analysis: dB (decibels), numerical scales, colored or different sized notes, words in languages other than Italian, and symbols such as those for progressively increasing volume (crescendo) or decreasing volume (diminuendo or decrescendo), often called "hairpins" when indicated with diverging or converging lines as shown in the graphic above.

Articulation
Articulation is the way the performer sounds notes. For example, staccato is the shortening of duration compared to the written note value, legato performs the notes in a smoothly joined sequence with no separation. Articulation is often described rather than quantified, therefore there is room to interpret how to execute precisely each articulation.

For example, staccato is often referred to as "separated" or "detached" rather than having a defined or numbered amount by which to reduce the notated duration. Violin players use a variety of techniques to perform different qualities of staccato. The manner in which a performer decides to execute a given articulation is usually based on the context of the piece or phrase, but many articulation symbols and verbal instructions depend on the instrument and musical period (e.g. viol, wind; classical, baroque; etc.).

There is a set of articulations that most instruments and voices perform in common. They are—from long to short: legato (smooth, connected); tenuto (pressed or played to full notated duration); marcato (accented and detached); staccato ("separated", "detached"); martelé (heavily accented or "hammered"). Many of these can be combined to create certain "in-between" articulations. For example, portato is the combination of tenuto and staccato. Some instruments have unique methods by which to produce sounds, such as spiccato for bowed strings, where the bow bounces off the string.

Texture
In music, texture is how the melodic, rhythmic, and harmonic materials are combined in a composition, thus determining the overall quality of the sound in a piece. Texture is often described in regard to the density, or thickness, and range, or width, between lowest and highest pitches, in relative terms as well as more specifically distinguished according to the number of voices, or parts, and the relationship between these voices. For example, a thick texture contains many "layers" of instruments. One of these layers could be a string section, or another brass.

The thickness also is affected by the number and the richness of the instruments playing the piece. The thickness varies from light to thick. A lightly textured piece will have light, sparse scoring. A thickly or heavily textured piece will be scored for many instruments. A piece's texture may be affected by the number and character of parts playing at once, the timbre of the instruments or voices playing these parts and the harmony, tempo, and rhythms used. The types categorized by number and relationship of parts are analyzed and determined through the labeling of primary textural elements: primary melody, secondary melody, parallel supporting melody, static support, harmonic support, rhythmic support, and harmonic and rhythmic support.

Common types included monophonic texture (a single melodic voice, such as a piece for solo soprano or solo flute), biphonic texture (two melodic voices, such as a duo for bassoon and flute in which the bassoon plays a drone note and the flute plays the melody), polyphonic texture and homophonic texture (chords accompanying a melody).

Form or structure

The term musical form (or musical architecture) refers to the overall structure or plan of a piece of music, and it describes the layout of a composition as divided into sections. In the tenth edition of The Oxford Companion to Music, Percy Scholes defines musical form as "a series of strategies designed to find a successful mean between the opposite extremes of unrelieved repetition and unrelieved alteration." According to Richard Middleton, musical form is "the shape or structure of the work." He describes it through difference: the distance moved from a repeat; the latter being the smallest difference. Difference is quantitative and qualitative: how far, and of what type, different. In many cases, form depends on statement and restatement, unity and variety, and contrast and connection.

Expression
Musical expression is the art of playing or singing music with emotional communication. The elements of music that comprise expression include dynamic indications, such as forte or piano, phrasing, differing qualities of timbre and articulation, color, intensity, energy and excitement. All of these devices can be incorporated by the performer. A performer aims to elicit responses of sympathetic feeling in the audience, and to excite, calm or otherwise sway the audience's physical and emotional responses. Musical expression is sometimes thought to be produced by a combination of other parameters, and sometimes described as a transcendent quality that is more than the sum of measurable quantities such as pitch or duration.

Expression on instruments can be closely related to the role of the breath in singing, and the voice's natural ability to express feelings, sentiment and deep emotions. Whether these can somehow be categorized is perhaps the realm of academics, who view expression as an element of musical performance that embodies a consistently recognizable emotion, ideally causing a sympathetic emotional response in its listeners. The emotional content of musical expression is distinct from the emotional content of specific sounds (e.g., a startlingly-loud 'bang') and of learned associations (e.g., a national anthem), but can rarely be completely separated from its context.

The components of musical expression continue to be the subject of extensive and unresolved dispute.

Notation
Musical notation is the written or symbolized representation of music. This is most often achieved by the use of commonly understood graphic symbols and written verbal instructions and their abbreviations. There are many systems of music notation from different cultures and different ages. Traditional Western notation evolved during the Middle Ages and remains an area of experimentation and innovation. In the 2000s, computer file formats have become important as well. Spoken language and hand signs are also used to symbolically represent music, primarily in teaching.

In standard Western music notation, tones are represented graphically by symbols (notes) placed on a staff or staves, the vertical axis corresponding to pitch and the horizontal axis corresponding to time. Note head shapes, stems, flags, ties and dots are used to indicate duration. Additional symbols indicate keys, dynamics, accents, rests, etc. Verbal instructions from the conductor are often used to indicate tempo, technique, and other aspects.

In Western music, a range of different music notation systems are used. In Western Classical music, conductors use printed scores that show all of the instruments' parts and orchestra members read parts with their musical lines written out. In popular styles of music, much less of the music may be notated. A rock band may go into a recording session with just a handwritten chord chart indicating the song's chord progression using chord names (e.g., C major, D minor, G7, etc.). All of the chord voicings, rhythms and accompaniment figures are improvised by the band members.

As academic discipline
The scholarly study of music theory in the twentieth century has a number of different subfields, each of which takes a different perspective on what are the primary phenomenon of interest and the most useful methods for investigation.

Analysis
Musical analysis is the attempt to answer the question how does this music work? The method employed to answer this question, and indeed exactly what is meant by the question, differs from analyst to analyst, and according to the purpose of the analysis. According to Ian Bent, "analysis, as a pursuit in its own right, came to be established only in the late 19th century; its emergence as an approach and method can be traced back to the 1750s. However, it existed as a scholarly tool, albeit an auxiliary one, from the Middle Ages onwards." Adolf Bernhard Marx was influential in formalising concepts about composition and music understanding towards the second half of the 19th century. The principle of analysis has been variously criticized, especially by composers, such as Edgard Varèse's claim that, "to explain by means of [analysis] is to decompose, to mutilate the spirit of a work".

Schenkerian analysis is a method of musical analysis of tonal music based on the theories of Heinrich Schenker (1868–1935). The goal of a Schenkerian analysis is to interpret the underlying structure of a tonal work and to help reading the score according to that structure. The theory's basic tenets can be viewed as a way of defining tonality in music. A Schenkerian analysis of a passage of music shows hierarchical relationships among its pitches, and draws conclusions about the structure of the passage from this hierarchy. The analysis makes use of a specialized symbolic form of musical notation that Schenker devised to demonstrate various techniques of elaboration. The most fundamental concept of Schenker's theory of tonality may be that of tonal space. The intervals between the notes of the tonic triad form a tonal space that is filled with passing and neighbour notes, producing new triads and new tonal spaces, open for further elaborations until the surface of the work (the score) is reached.

Although Schenker himself usually presents his analyses in the generative direction, starting from the fundamental structure (Ursatz) to reach the score, the practice of Schenkerian analysis more often is reductive, starting from the score and showing how it can be reduced to its fundamental structure. The graph of the Ursatz is arrhythmic, as is a strict-counterpoint cantus firmus exercise. Even at intermediate levels of the reduction, rhythmic notation (open and closed noteheads, beams and flags) shows not rhythm but the hierarchical relationships between the pitch-events. Schenkerian analysis is subjective. There is no mechanical procedure involved and the analysis reflects the musical intuitions of the analyst. The analysis represents a way of hearing (and reading) a piece of music.

Transformational theory is a branch of music theory developed by David Lewin in the 1980s, and formally introduced in his 1987 work, Generalized Musical Intervals and Transformations. The theory, which models musical transformations as elements of a mathematical group, can be used to analyze both tonal and atonal music. The goal of transformational theory is to change the focus from musical objects—such as the "C major chord" or "G major chord"—to relations between objects. Thus, instead of saying that a C major chord is followed by G major, a transformational theorist might say that the first chord has been "transformed" into the second by the "Dominant operation." (Symbolically, one might write "Dominant(C major) = G major.") While traditional musical set theory focuses on the makeup of musical objects, transformational theory focuses on the intervals or types of musical motion that can occur. According to Lewin's description of this change in emphasis, "[The transformational] attitude does not ask for some observed measure of extension between reified 'points'; rather it asks: 'If I am at s and wish to get to t, what characteristic gesture should I perform in order to arrive there?'"

Music perception and cognition
Music psychology or the psychology of music may be regarded as a branch of both psychology and musicology. It aims to explain and understand musical behavior and experience, including the processes through which music is perceived, created, responded to, and incorporated into everyday life. Modern music psychology is primarily empirical; its knowledge tends to advance on the basis of interpretations of data collected by systematic observation of and interaction with human participants. Music psychology is a field of research with practical relevance for many areas, including music performance, composition, education, criticism, and therapy, as well as investigations of human aptitude, skill, intelligence, creativity, and social behavior.

Music psychology can shed light on non-psychological aspects of musicology and musical practice. For example, it contributes to music theory through investigations of the perception and computational modelling of musical structures such as melody, harmony, tonality, rhythm, meter, and form. Research in music history can benefit from systematic study of the history of musical syntax, or from psychological analyses of composers and compositions in relation to perceptual, affective, and social responses to their music.

Genre and technique
A music genre is a conventional category that identifies some pieces of music as belonging to a shared tradition or set of conventions. It is to be distinguished from musical form and musical style, although in practice these terms are sometimes used interchangeably.

Music can be divided into different genres in many different ways. The artistic nature of music means that these classifications are often subjective and controversial, and some genres may overlap. There are even varying academic definitions of the term genre itself. In his book Form in Tonal Music, Douglass M. Green distinguishes between genre and form. He lists madrigal, motet, canzona, ricercar, and dance as examples of genres from the Renaissance period. To further clarify the meaning of genre, Green writes, "Beethoven's Op. 61 and Mendelssohn's Op. 64 are identical in genre—both are violin concertos—but different in form. However, Mozart's Rondo for Piano, K. 511, and the Agnus Dei from his Mass, K. 317 are quite different in genre but happen to be similar in form." Some, like Peter van der Merwe, treat the terms genre and style as the same, saying that genre should be defined as pieces of music that came from the same style or "basic musical language."

Others, such as Allan F. Moore, state that genre and style are two separate terms, and that secondary characteristics such as subject matter can also differentiate between genres. A music genre or subgenre may also be defined by the musical techniques, the style, the cultural context, and the content and spirit of the themes. Geographical origin is sometimes used to identify a music genre, though a single geographical category will often include a wide variety of subgenres. Timothy Laurie argues that "since the early 1980s, genre has graduated from being a subset of popular music studies to being an almost ubiquitous framework for constituting and evaluating musical research objects".

Musical technique is the ability of instrumental and vocal musicians to exert optimal control of their instruments or vocal cords to produce precise musical effects. Improving technique generally entails practicing exercises that improve muscular sensitivity and agility. To improve technique, musicians often practice fundamental patterns of notes such as the natural, minor, major, and chromatic scales, minor and major triads, dominant and diminished sevenths, formula patterns and arpeggios. For example, triads and sevenths teach how to play chords with accuracy and speed. Scales teach how to move quickly and gracefully from one note to another (usually by step). Arpeggios teach how to play broken chords over larger intervals. Many of these components of music are found in compositions, for example, a scale is a very common element of classical and romantic era compositions.

Heinrich Schenker argued that musical technique's "most striking and distinctive characteristic" is repetition. Works known as études (meaning "study") are also frequently used for the improvement of technique.

Mathematics
Music theorists sometimes use mathematics to understand music, and although music has no axiomatic foundation in modern mathematics, mathematics is "the basis of sound" and sound itself "in its musical aspects... exhibits a remarkable array of number properties", simply because nature itself "is amazingly mathematical". The attempt to structure and communicate new ways of composing and hearing music has led to musical applications of set theory, abstract algebra and number theory. Some composers have incorporated the golden ratio and Fibonacci numbers into their work. There is a long history of examining the relationships between music and mathematics. Though ancient Chinese, Egyptians and Mesopotamians are known to have studied the mathematical principles of sound, the Pythagoreans (in particular Philolaus and Archytas) of ancient Greece were the first researchers known to have investigated the expression of musical scales in terms of numerical ratios. In the modern era, musical set theory uses the language of mathematical set theory in an elementary way to organize musical objects and describe their relationships. To analyze the structure of a piece of (typically atonal) music using musical set theory, one usually starts with a set of tones, which could form motives or chords. By applying simple operations such as transposition and inversion, one can discover deep structures in the music. Operations such as transposition and inversion are called isometries because they preserve the intervals between tones in a set. Expanding on the methods of musical set theory, some theorists have used abstract algebra to analyze music. For example, the pitch classes in an equally tempered octave form an abelian group with 12 elements. It is possible to describe just intonation in terms of a free abelian group.

Serial composition and set theory

In music theory, serialism is a method or technique of composition that uses a series of values to manipulate different musical elements. Serialism began primarily with Arnold Schoenberg's twelve-tone technique, though his contemporaries were also working to establish serialism as one example of post-tonal thinking. Twelve-tone technique orders the twelve notes of the chromatic scale, forming a row or series and providing a unifying basis for a composition's melody, harmony, structural progressions, and variations. Other types of serialism also work with sets, collections of objects, but not necessarily with fixed-order series, and extend the technique to other musical dimensions (often called "parameters"), such as duration, dynamics, and timbre. The idea of serialism is also applied in various ways in the visual arts, design, and architecture

"Integral serialism" or "total serialism" is the use of series for aspects such as duration, dynamics, and register as well as pitch. Other terms, used especially in Europe to distinguish post-World War II serial music from twelve-tone music and its American extensions, are "general serialism" and "multiple serialism".

Musical set theory provides concepts for categorizing musical objects and describing their relationships. Many of the notions were first elaborated by Howard Hanson (1960) in connection with tonal music, and then mostly developed in connection with atonal music by theorists such as Allen Forte (1973), drawing on the work in twelve-tone theory of Milton Babbitt. The concepts of set theory are very general and can be applied to tonal and atonal styles in any equally tempered tuning system, and to some extent more generally than that.

One branch of musical set theory deals with collections (sets and permutations) of pitches and pitch classes (pitch-class set theory), which may be ordered or unordered, and can be related by musical operations such as transposition, inversion, and complementation. The methods of musical set theory are sometimes applied to the analysis of rhythm as well.

Musical semiotics
Music semiology (semiotics) is the study of signs as they pertain to music on a variety of levels. Following Roman Jakobson, Kofi Agawu adopts the idea of musical semiosis being introversive or extroversive—that is, musical signs within a text and without. "Topics", or various musical conventions (such as horn calls, dance forms, and styles), have been treated suggestively by Agawu, among others. The notion of gesture is beginning to play a large role in musico-semiotic enquiry.

 * "There are strong arguments that music inhabits a semiological realm which, on both ontogenetic and phylogenetic levels, has developmental priority over verbal language."

Writers on music semiology include Kofi Agawu (on topical theory, Heinrich Schenker, Robert Hatten (on topic, gesture), Raymond Monelle (on topic, musical meaning), Jean-Jacques Nattiez (on introversive taxonomic analysis and ethnomusicological applications), Anthony Newcomb (on narrativity), and Eero Tarasti.

Roland Barthes, himself a semiotician and skilled amateur pianist, wrote about music in Image-Music-Text, The Responsibilities of Form, and Eiffel Tower, though he did not consider music to be a semiotic system.

Signs, meanings in music, happen essentially through the connotations of sounds, and through the social construction, appropriation and amplification of certain meanings associated with these connotations. The work of Philip Tagg (Ten Little Tunes, Fernando the Flute, Music's Meanings) provides one of the most complete and systematic analysis of the relation between musical structures and connotations in western and especially popular, television and film music. The work of Leonard B. Meyer in Style and Music theorizes the relationship between ideologies and musical structures and the phenomena of style change, and focuses on romanticism as a case study.

Education and careers
Music theory in the practical sense has been a part of education at conservatories and music schools for centuries, but the status music theory currently has within academic institutions is relatively recent. In the 1970s, few universities had dedicated music theory programs, many music theorists had been trained as composers or historians, and there was a belief among theorists that the teaching of music theory was inadequate and that the subject was not properly recognised as a scholarly discipline in its own right. A growing number of scholars began promoting the idea that music theory should be taught by theorists, rather than composers, performers or music historians. This led to the founding of the Society for Music Theory in the United States in 1977. In Europe, the French Société d'Analyse musicale was founded in 1985. It called the First European Conference of Music Analysis for 1989, which resulted in the foundation of the Société belge d'Analyse musicale in Belgium and the Gruppo analisi e teoria musicale in Italy the same year, the Society for Music Analysis in the UK in 1991, the Vereniging voor Muziektheorie in the Netherlands in 1999 and the Gesellschaft für Musiktheorie in Germany in 2000. They were later followed by the Russian Society for Music Theory in 2013, the Polish Society for Music Analysis in 2015 and the Sociedad de Análisis y Teoría Musical in Spain in 2020, and others are in construction. These societies coordinate the publication of music theory scholarship and support the professional development of music theory researchers. They formed in 2018 a network of European societies for Theory and/or Analysis of Music, the EuroT&AM

As part of their initial training, music theorists will typically complete a B.Mus or a B.A. in music (or a related field) and in many cases an M.A. in music theory. Some individuals apply directly from a bachelor's degree to a PhD, and in these cases, they may not receive an M.A. In the 2010s, given the increasingly interdisciplinary nature of university graduate programs, some applicants for music theory PhD programs may have academic training both in music and outside of music (e.g., a student may apply with a B.Mus. and a Masters in Music Composition or Philosophy of Music).

Most music theorists work as instructors, lecturers or professors in colleges, universities or conservatories. The job market for tenure-track professor positions is very competitive: with an average of around 25 tenure-track positions advertised per year in the past decade, 80–100 PhD graduates are produced each year (according to the Survey of Earned Doctorates) who compete not only with each other for those positions but with job seekers that received PhD's in previous years who are still searching for a tenure-track job. Applicants must hold a completed PhD or the equivalent degree (or expect to receive one within a year of being hired—called an "ABD", for "All But Dissertation" stage) and (for more senior positions) have a strong record of publishing in peer-reviewed journals. Some PhD-holding music theorists are only able to find insecure positions as sessional lecturers. The job tasks of a music theorist are the same as those of a professor in any other humanities discipline: teaching undergraduate and/or graduate classes in this area of specialization and, in many cases some general courses (such as Music appreciation or Introduction to Music Theory), conducting research in this area of expertise, publishing research articles in peer-reviewed journals, authoring book chapters, books or textbooks, traveling to conferences to present papers and learn about research in the field, and, if the program includes a graduate school, supervising M.A. and PhD students and giving them guidance on the preparation of their theses and dissertations. Some music theory professors may take on senior administrative positions in their institution, such as Dean or Chair of the School of Music.

title: Music theory


text:
Recursively enumerable language

In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.

Recursively enumerable languages are known as type-0 languages in the Chomsky hierarchy of formal languages. All regular, context-free, context-sensitive and recursive languages are recursively enumerable.

The class of all recursively enumerable languages is called RE.

Definitions
There are three equivalent definitions of a recursively enumerable language:

 * 1) A recursively enumerable language is a recursively enumerable subset in the set of all possible words over the alphabet of the language.
 * 2) A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) which will enumerate all valid strings of the language. Note that if the language is infinite, the enumerating algorithm provided can be chosen so that it avoids repetitions, since we can test whether the string produced for number n is "already" produced for a number which is less than n. If it already is produced, use the output for input n+1 instead (recursively), but again, test whether it is "new".
 * 3) A recursively enumerable language is a formal language for which there exists a Turing machine (or other computable function) that will halt and accept when presented with any string in the language as input but may either halt and reject or loop forever when presented with a string not in the language. Contrast this to recursive languages, which require that the Turing machine halts in all cases.

All regular, context-free, context-sensitive and recursive languages are recursively enumerable.

Post's theorem shows that RE, together with its complement co-RE, correspond to the first level of the arithmetical hierarchy.

Example
The set of halting Turing machines is recursively enumerable but not recursive. Indeed, one can run the Turing machine and accept if the machine halts, hence it is recursively enumerable. On the other hand, the problem is undecidable.

Some other recursively enumerable languages that are not recursive include:

 * Post correspondence problem
 * Mortality (computability theory)
 * Entscheidungsproblem

Closure properties
Recursively enumerable languages (REL) are closed under the following operations. That is, if L and P are two recursively enumerable languages, then the following languages are recursively enumerable as well:

 * the Kleene star $$L^*$$ of L
 * the concatenation $$L \circ P$$ of L and P
 * the union $$L \cup P$$
 * the intersection $$L \cap P$$.

Recursively enumerable languages are not closed under set difference or complementation. The set difference $$L - P$$ is recursively enumerable if $$P$$ is recursive. If $$L$$ is recursively enumerable, then the complement of $$L$$ is recursively enumerable if and only if $$L$$ is also recursive.

title: Recursively enumerable language