Combinatorics on words is a fairly new field of mathematics , branching from combinatorics , which focuses on the study of words and formal languages . The subject looks at letters or symbols , and the sequences they form. Combinatorics on words affects various areas of mathematical study, including algebra and computer science . There have been a wide range of contributions to the field. Some of the first work was on square-free words by Axel Thue in the early 1900s. He and colleagues observed patterns within words and tried to explain them. As time went on, combinatorics on words became useful in the study of algorithms and coding . It led to developments in abstract algebra and answering open questions.
46-464: [REDACTED] Look up Factor or factor in Wiktionary, the free dictionary. Factor (Latin, 'who/which acts') may refer to: Commerce [ edit ] Factor (agent) , a person who acts for, notably a mercantile and colonial agent Factor (Scotland) , a person or firm managing a Scottish estate Factors of production , such
92-426: A closed curve on a plane is needed. If the curve only crosses over itself a finite number of times, then one labels the intersections with a letter from the alphabet used. Traveling along the curve, the word is determined by recording each letter as an intersection is passed. Gauss noticed that the distance between when the same symbol shows up in a word is an even integer . Walther Franz Anton von Dyck began
138-408: A theorem by Chen, Fox, and Lyndon , that states any word has a unique factorization of Lyndon words, where the factorization words are non-increasing . Due to this property, Lyndon words are used to study algebra , specifically group theory . They form the basis for the idea of commutators . Cobham contributed work relating Eugène Prouhet 's work with finite automata . A mathematical graph
184-421: A certain number of letters. The words appear only once in the necklace. In 1874, Baudot developed the code that would eventually take the place of Morse code by applying the theory of binary de Bruijn necklaces. The problem continued from Sainte-Marie to Martin in 1934, who began looking at algorithms to make words of the de Bruijn structure. It was then worked on by Klaas Posthumus in 1943. Possibly
230-445: A factor is a resource used in the production of goods and services Factor, a brand of HelloFresh meal-kit company Science and technology [ edit ] Biology [ edit ] Coagulation factors , substances essential for blood coagulation Environmental factor , any abiotic or biotic factor that affects life Enzyme , proteins that catalyze chemical reactions Factor B , and factor D , peptides involved in
276-408: A factor of a word is a block of consecutive symbols. Thus, "cyclop" is a factor of "encyclopedia". In addition to examining sequences in themselves, another area to consider of combinatorics on words is how they can be represented visually. In mathematics various structures are used to encode data. A common structure used in combinatorics is the tree structure . A tree structure is a graph where
322-510: A member or component of a chord FACTOR , the Foundation to Assist Canadian Talent on Records The Factor , an April 2017 TV show on Fox News Channel See also [ edit ] [REDACTED] Search for "factor" on Misplaced Pages. All pages with titles containing factor All pages with titles beginning with Factor Co-factor (disambiguation) Factoring (disambiguation) Topics referred to by
368-451: A member or component of a chord FACTOR , the Foundation to Assist Canadian Talent on Records The Factor , an April 2017 TV show on Fox News Channel See also [ edit ] [REDACTED] Search for "factor" on Misplaced Pages. All pages with titles containing factor All pages with titles beginning with Factor Co-factor (disambiguation) Factoring (disambiguation) Topics referred to by
414-482: A multiplication Divisor , an integer which evenly divides a number without leaving a remainder Factorization , the decomposition of an object into a product of other objects Integer factorization , the process of breaking down a composite number into smaller non-trivial divisors A coefficient , a multiplicative factor in an expression, usually a number The act of forming a factor group or quotient ring in abstract algebra A von Neumann algebra , with
460-482: A multiplication Divisor , an integer which evenly divides a number without leaving a remainder Factorization , the decomposition of an object into a product of other objects Integer factorization , the process of breaking down a composite number into smaller non-trivial divisors A coefficient , a multiplicative factor in an expression, usually a number The act of forming a factor group or quotient ring in abstract algebra A von Neumann algebra , with
506-522: A person or firm managing a Scottish estate Factors of production , such a factor is a resource used in the production of goods and services Factor, a brand of HelloFresh meal-kit company Science and technology [ edit ] Biology [ edit ] Coagulation factors , substances essential for blood coagulation Environmental factor , any abiotic or biotic factor that affects life Enzyme , proteins that catalyze chemical reactions Factor B , and factor D , peptides involved in
SECTION 10
#1732776292021552-463: A set of correlated variables. People [ edit ] Factor Chandelier , Canadian hip hop artist John Factor (1892–1984), British-American Prohibition-era gangster Max Factor Sr. (1872–1938), Polish-American businessman and cosmetician Max Factor Jr. (1904–1996), son of the above, born Francis Factor Places [ edit ] Factor, Arecibo, Puerto Rico , a barrio Other uses [ edit ] Factor (chord) ,
598-463: A set of correlated variables. People [ edit ] Factor Chandelier , Canadian hip hop artist John Factor (1892–1984), British-American Prohibition-era gangster Max Factor Sr. (1872–1938), Polish-American businessman and cosmetician Max Factor Jr. (1904–1996), son of the above, born Francis Factor Places [ edit ] Factor, Arecibo, Puerto Rico , a barrio Other uses [ edit ] Factor (chord) ,
644-404: A string Authentication factor , a piece of information used to verify a person's identity for security purposes Decomposition (computer science) , also known as factoring, the organization of computer code Enumerated type : a data type consisting of a set of named values, called factor in the R programming language Other uses in science and technology [ edit ] Factor, in
690-404: A string Authentication factor , a piece of information used to verify a person's identity for security purposes Decomposition (computer science) , also known as factoring, the organization of computer code Enumerated type : a data type consisting of a set of named values, called factor in the R programming language Other uses in science and technology [ edit ] Factor, in
736-457: A trivial center Factor (graph theory) , a spanning sub graph Any finite contiguous sub-sequence of a word in combinatorics or of a word in group theory . Statistics [ edit ] An independent categorical variable . In experimental design , the factor is a category of treatments controlled by the experimenter. In factor analysis , the factors are unobserved underlying hidden variables that explain variability in
782-457: A trivial center Factor (graph theory) , a spanning sub graph Any finite contiguous sub-sequence of a word in combinatorics or of a word in group theory . Statistics [ edit ] An independent categorical variable . In experimental design , the factor is a category of treatments controlled by the experimenter. In factor analysis , the factors are unobserved underlying hidden variables that explain variability in
828-780: Is Sturmian if and only if it has n + 1 {\displaystyle n+1} distinct factors of length n {\displaystyle n} , for every non-negative integer n {\displaystyle n} . A Lyndon word is a word over a given alphabet that is written in its simplest and most ordered form out of its respective conjugacy class . Lyndon words are important because for any given Lyndon word x {\displaystyle x} , there exists Lyndon words y {\displaystyle y} and z {\displaystyle z} , with y < z {\displaystyle y<z} , x = y z {\displaystyle x=yz} . Further, there exists
874-400: Is a recent development in this field that focuses on the study of words and formal languages. A formal language is any set of symbols and combinations of symbols that people use to communicate information. Some terminology relevant to the study of words should first be explained. First and foremost, a word is basically a sequence of symbols, or letters, in a finite set . One of these sets
920-616: Is a sequence of numbers in which the difference between adjacent numbers remains constant. When examining unavoidable patterns sesquipowers are also studied. For some patterns x {\displaystyle x} , y {\displaystyle y} , z {\displaystyle z} , a sesquipower is of the form x {\displaystyle x} , x y x {\displaystyle xyx} , x y x z x y x {\displaystyle xyxzxyx} , … {\displaystyle \ldots ~} . This
966-824: Is another pattern such as square-free, or unavoidable patterns. Coudrain and Schützenberger mainly studied these sesquipowers for group theory applications. In addition, Zimin proved that sesquipowers are all unavoidable. Whether the entire pattern shows up, or only some piece of the sesquipower shows up repetitively, it is not possible to avoid it. Necklaces are constructed from words of circular sequences. They are most frequently used in music and astronomy . Flye Sainte-Marie in 1894 proved there are 2 2 n − 1 − n {\displaystyle 2^{2^{n-1}-n}} binary de Bruijn necklaces of length 2 n {\displaystyle 2^{n}} . A de Bruijn necklace contains factors made of words of length n over
SECTION 20
#17327762920211012-516: Is colored with two colors, there will always exist a solid color subgraph of each color. Other contributors to the study of unavoidable patterns include van der Waerden . His theorem states that if the positive integers are partitioned into k {\displaystyle k} classes, then there exists a class c {\displaystyle c} such that c {\displaystyle c} contains an arithmetic progression of some unknown length. An arithmetic progression
1058-445: Is different from Wikidata All article disambiguation pages All disambiguation pages Factor [REDACTED] Look up Factor or factor in Wiktionary, the free dictionary. Factor (Latin, 'who/which acts') may refer to: Commerce [ edit ] Factor (agent) , a person who acts for, notably a mercantile and colonial agent Factor (Scotland) ,
1104-539: Is different from Wikidata All article disambiguation pages All disambiguation pages Combinatorics on words Combinatorics is an area of discrete mathematics . Discrete mathematics is the study of countable structures. These objects have a definite beginning and end. The study of enumerable objects is the opposite of disciplines such as analysis , where calculus and infinite structures are studied. Combinatorics studies how to count these objects using various representations. Combinatorics on words
1150-487: Is known by the general public as the alphabet . For example, the word "encyclopedia" is a sequence of symbols in the English alphabet , a finite set of twenty-six letters. Since a word can be described as a sequence, other basic mathematical descriptions can be applied. The alphabet is a set , so as one would expect, the empty set is a subset . In other words, there exists a unique word of length zero. The length of
1196-474: Is made of edges and nodes . With finite automata, the edges are labeled with a letter in an alphabet. To use the graph, one starts at a node and travels along the edges to reach a final node. The path taken along the graph forms the word. It is a finite graph because there are a countable number of nodes and edges, and only one path connects two distinct nodes. Gauss codes , created by Carl Friedrich Gauss in 1838, are developed from graphs. Specifically,
1242-503: Is no possible algorithm that can answer the question in all cases (because any such algorithm could be encoded into a word problem which that algorithm could not solve). The Burnside question was proved using the existence of an infinite cube-free word . This question asks if a group is finite if the group has a definite number of generators and meets the criteria x n = 1 {\displaystyle x^{n}=1} , for x {\displaystyle x} in
1288-507: Is not square-free since "in" is repeated consecutively, while "servers" is square-free, its two "er" factors not being adjacent. Thue proves his conjecture on the existence of infinite square-free words by using substitutions . A substitution is a way to take a symbol and replace it with a word. He uses this technique to describe his other contribution, the Thue–Morse sequence , or Thue–Morse word. Thue wrote two papers on square-free words,
1334-569: Is to divide language into four levels, or the language hierarchy . The four levels are: regular , context-free , context-sensitive , and computably enumerable or unrestricted. Regular is the least complex while computably enumerable is the most complex. While his work grew out of combinatorics on words, it drastically affected other disciplines, especially computer science . Sturmian words , created by François Sturm, have roots in combinatorics on words. There exist several equivalent definitions of Sturmian words. For example, an infinite word
1380-405: The design of experiments , a phenomenon presumed to affect an experiment Human factors , a profession that focuses on how people interact with products, tools, or procedures Sun protection factor , a unit describing reduction in transmitted ultraviolet light Mathematics [ edit ] General mathematics [ edit ] Factor (arithmetic) , either of two numbers involved in
1426-405: The design of experiments , a phenomenon presumed to affect an experiment Human factors , a profession that focuses on how people interact with products, tools, or procedures Sun protection factor , a unit describing reduction in transmitted ultraviolet light Mathematics [ edit ] General mathematics [ edit ] Factor (arithmetic) , either of two numbers involved in
Factor - Misplaced Pages Continue
1472-450: The vertices are connected by one line, called a path or edge . Trees may not contain cycles , and may or may not be complete. It is possible to encode a word, since a word is constructed by symbols, and encode the data by using a tree. This gives a visual representation of the object. The first books on combinatorics on words that summarize the origins of the subject were written by a group of mathematicians that collectively went by
1518-434: The alternate pathway of immune system complement activation Transcription factor , a protein that binds to specific DNA sequences Computer science and information technology [ edit ] Factor (programming language) , a concatenative stack-oriented programming language Factor (Unix) , a utility for factoring an integer into its prime factors Factor, a substring , a subsequence of consecutive symbols in
1564-434: The alternate pathway of immune system complement activation Transcription factor , a protein that binds to specific DNA sequences Computer science and information technology [ edit ] Factor (programming language) , a concatenative stack-oriented programming language Factor (Unix) , a utility for factoring an integer into its prime factors Factor, a substring , a subsequence of consecutive symbols in
1610-738: The form aā or āa, for some a in the alphabet. Reduced words are formed when the factors aā, āa are used to cancel out elements until a unique word is reached. Nielsen transformations were also developed. For a set of elements of a free group , a Nielsen transformation is achieved by three transformations; replacing an element with its inverse, replacing an element with the product of itself and another element, and eliminating any element equal to 1. By applying these transformations Nielsen reduced sets are formed. A reduced set means no element can be multiplied by other elements to cancel out completely. There are also connections with Nielsen transformations with Sturmian words. One problem considered in
1656-606: The group. Many word problems are undecidable based on the Post correspondence problem . Any two homomorphisms g , h {\displaystyle g,h} with a common domain and a common codomain form an instance of the Post correspondence problem, which asks whether there exists a word w {\displaystyle w} in the domain such that g ( w ) = h ( w ) {\displaystyle g(w)=h(w)} . Post proved that this problem
1702-462: The most applied result in combinatorics on words is the Chomsky hierarchy , developed by Noam Chomsky . He studied formal language in the 1950s. His way of looking at language simplified the subject. He disregards the actual meaning of the word, does not consider certain factors such as frequency and context, and applies patterns of short terms to all length terms. The basic idea of Chomsky's work
1748-412: The name of M. Lothaire . Their first book was published in 1983, when combinatorics on words became more widespread. A main contributor to the development of combinatorics on words was Axel Thue (1863–1922); he researched repetition. Thue's main contribution was the proof of the existence of infinite square-free words . Square-free words do not have adjacent repeated factors. To clarify, "dining"
1794-463: The same term [REDACTED] This disambiguation page lists articles associated with the title Factor . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=Factor&oldid=1253769567 " Categories : Disambiguation pages Disambiguation pages with surname-holder lists Hidden categories: Short description
1840-463: The same term [REDACTED] This disambiguation page lists articles associated with the title Factor . If an internal link led you here, you may wish to change the link to point directly to the intended article. Retrieved from " https://en.wikipedia.org/w/index.php?title=Factor&oldid=1253769567 " Categories : Disambiguation pages Disambiguation pages with surname-holder lists Hidden categories: Short description
1886-528: The second of which was on the Thue–Morse word. Marston Morse is included in the name because he discovered the same result as Thue did, yet they worked independently. Thue also proved the existence of an overlap-free word. An overlap-free word is when, for two symbols x {\displaystyle x} and y {\displaystyle y} , the pattern x y x y x {\displaystyle xyxyx} does not exist within
Factor - Misplaced Pages Continue
1932-488: The study of combinatorics on words in group theory is the following: for two elements x {\displaystyle x} , y {\displaystyle y} of a semigroup , does x = y {\displaystyle x=y} modulo the defining relations of x {\displaystyle x} and y {\displaystyle y} . Post and Markov studied this problem and determined it undecidable , meaning that there
1978-442: The word w {\displaystyle w} is defined by the number of symbols that make up the sequence, and is denoted by | w | {\displaystyle |w|} . Again looking at the example "encyclopedia", | w | = 12 {\displaystyle |w|=12} , since encyclopedia has twelve letters. The idea of factoring of large numbers can be applied to words, where
2024-556: The word. He continues in his second paper to prove a relationship between infinite overlap-free words and square-free words. He takes overlap-free words that are created using two different letters, and demonstrates how they can be transformed into square-free words of three letters using substitution. As was previously described, words are studied by examining the sequences made by the symbols. Patterns are found, and they can be described mathematically. Patterns can be either avoidable patterns, or unavoidable. A significant contributor to
2070-399: The work of unavoidable patterns , or regularities, was Frank Ramsey in 1930. His important theorem states that for integers k {\displaystyle k} , m ≥ 2 {\displaystyle m\geq 2} , there exists a least positive integer R ( k , m ) {\displaystyle R(k,m)} such that despite how a complete graph
2116-424: The work of combinatorics on words in group theory by his published work in 1882 and 1883. He began by using words as group elements. Lagrange also contributed in 1771 with his work on permutation groups . One aspect of combinatorics on words studied in group theory is reduced words. A group is constructed with words on some alphabet including generators and inverse elements , excluding factors that appear of
#20979