|
Partial Cyclic Order
In mathematics, a partial cyclic order is a ternary relation that generalizes a cyclic order in the same way that a partial order generalizes a linear order. Definition Over a given set, a partial cyclic order is a ternary relation R that is: * ''cyclic'', i.e. it is invariant under a cyclic permutation: R(x, y, z) \Rightarrow R(y, z, x) * ''asymmetric'': R(x, y, z) \Rightarrow \not R(z, y, x) * ''transitive'': R(x, y, z) and R(x, z, u) \Rightarrow R(x, y, u) Constructions Direct sum Direct product Power Dedekind–MacNeille completion Extensions linear extension, Szpilrajn extension theorem standard example The relationship between partial and total cyclic orders is more complex than the relationship between partial and total linear orders. To begin with, not every partial cyclic order can be extended to a total cyclic order. An example is the following relation on the first thirteen letters of the alphabet: ∪ . This relation is a partial cyclic order, but it cannot be e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ternary Relation
In mathematics, a ternary relation or triadic relation is a finitary relation in which the number of places in the relation is three. Ternary relations may also be referred to as 3-adic, 3-ary, 3-dimensional, or 3-place. Just as a binary relation is formally defined as a set of ''pairs'', i.e. a subset of the Cartesian product of some sets ''A'' and ''B'', so a ternary relation is a set of triples, forming a subset of the Cartesian product of three sets ''A'', ''B'' and ''C''. An example of a ternary relation in elementary geometry can be given on triples of points, where a triple is in the relation if the three points are collinear. Another geometric example can be obtained by considering triples consisting of two points and a line, where a triple is in the ternary relation if the two points determine (are incident with) the line. Examples Binary functions A function in two variables, mapping two values from sets ''A'' and ''B'', respectively, to a value in ''C'' associate ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Szpilrajn Extension Theorem
In order theory, the Szpilrajn extension theorem (also called the order-extension principle), proved by Edward Szpilrajn in 1930,. states that every strict partial order is contained in a total order. Intuitively, the theorem says that any method of comparing elements that leaves some pairs incomparable can be extended in such a way that every pair becomes comparable. The theorem is one of many examples of the use of the axiom of choice in the form of Zorn's lemma to find a maximal set with certain properties. Definitions and statement A binary relation R on a set X is formally defined as a set of ordered pairs (x, y) of elements of X, and (x, y) \in R is often abbreviated as xRy. A relation is reflexive if xRx holds for every element x \in X; it is transitive if xRy \text yRz imply xRz for all x, y, z \in X; it is antisymmetric if xRy \text yRx imply x = y for all x, y \in X; and it is a connex relation if xRy \text yRx holds for all x, y \in X. A partial order is, by def ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Electronic Notes In Theoretical Computer Science
''Electronic Notes in Theoretical Computer Science'' is an electronic computer science journal published by Elsevier, started in 1995. Its issues include many post-proceedings for workshops, etc. The journal is abstracted and indexed in Scopus and Science Citation Index The Science Citation Index Expanded – previously entitled Science Citation Index – is a citation index originally produced by the Institute for Scientific Information (ISI) and created by Eugene Garfield. It was officially launched in 1964 and .... Electronic Notes in Theoretical Computer Science has been discontinued as of 2021. References Computer science journals Elsevier academic journals Publications established in 1995 {{comp-sci-theory-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
SIAM Journal On Discrete Mathematics
'' SIAM Journal on Discrete Mathematics'' is a peer-reviewed mathematics journal published quarterly by the Society for Industrial and Applied Mathematics (SIAM). The journal includes articles on pure and applied discrete mathematics. It was established in 1988, along with the ''SIAM Journal on Matrix Analysis and Applications'', to replace the ''SIAM Journal on Algebraic and Discrete Methods''. The journal is indexed by ''Mathematical Reviews'' and Zentralblatt MATH. Its 2009 MCQ was 0.57. According to the ''Journal Citation Reports'', the journal has a 2016 impact factor of 0.755. Although its official ISO abbreviation is ''SIAM J. Discrete Math.'', its publisher and contributors frequently use the shorter abbreviation ''SIDMA''. References External links * Combinatorics journals Publications established in 1988 English-language journals Discrete Mathematics Discrete mathematics is the study of mathematical structures that can be considered "discrete" (in a way ana ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bulletin Of The American Mathematical Society
The ''Bulletin of the American Mathematical Society'' is a quarterly mathematical journal published by the American Mathematical Society. Scope It publishes surveys on contemporary research topics, written at a level accessible to non-experts. It also publishes, by invitation only, book reviews and short ''Mathematical Perspectives'' articles. History It began as the ''Bulletin of the New York Mathematical Society'' and underwent a name change when the society became national. The Bulletin's function has changed over the years; its original function was to serve as a research journal for its members. Indexing The Bulletin is indexed in Mathematical Reviews, Science Citation Index, ISI Alerting Services, CompuMath Citation Index, and Current Contents/Physical, Chemical & Earth Sciences. See also *'' Journal of the American Mathematical Society'' *''Memoirs of the American Mathematical Society'' *''Notices of the American Mathematical Society'' *'' Proceedings of the American M ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theoretical Computer Science (journal)
''Theoretical Computer Science'' (TCS) is a computer science journal published by Elsevier, started in 1975 and covering theoretical computer science. The journal publishes 52 issues a year. It is abstracted and indexed by Scopus and the Science Citation Index. According to the Journal Citation Reports, its 2020 impact factor The impact factor (IF) or journal impact factor (JIF) of an academic journal is a scientometric index calculated by Clarivate that reflects the yearly mean number of citations of articles published in the last two years in a given journal, as i ... is 0.827. References Computer science journals Elsevier academic journals Publications established in 1975 {{comp-sci-theory-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor. Since an algorithm's running time may vary among different inputs of the same size, one commonly considers the worst-case time complexity, which is the maximum amount of time required for inputs of a given size. Less common, and usually specified explicitly, is the average-case complexity, which is the average of the time taken on inputs of a given size (this makes sense because there are only a finite number of possible inputs of a given size). In both cases, the time complexity is generally expresse ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
3SAT
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. In other words, it asks whether the variables of a given Boolean formula can be consistently replaced by the values TRUE or FALSE in such a way that the formula evaluates to TRUE. If this is the case, the formula is called ''satisfiable''. On the other hand, if no such assignment exists, the function expressed by the formula is FALSE for all possible variable assignments and the formula is ''unsatisfiable''. For example, the formula "''a'' AND NOT ''b''" is satisfiable because one can find the values ''a'' = TRUE and ''b'' = FALSE, which make (''a'' AND NOT ''b'') = TRUE. In contrast, "''a'' AND NOT ''a''" is unsatisfiable. SAT is the first problem that was proved to be NP-complete ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
NP-complete
In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions. # the problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, NP-complete problems are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some NP-complete problem quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified. The name "NP-complete" is short for "nondeterministic polynomial-time complete". In this name, "nondeterministic" refers to nondeterministic Turing machines, a way of mathematically formalizing the idea of a brute-force search algorithm. Polynomial time refers to an amount of time that is considered "quick" for a de ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Linear Extension
In order theory, a branch of mathematics, a linear extension of a partial order is a total order (or linear order) that is compatible with the partial order. As a classic example, the lexicographic order of totally ordered sets is a linear extension of their product order. Definitions Given any partial orders \,\leq\, and \,\leq^*\, on a set X, \,\leq^*\, is a linear extension of \,\leq\, exactly when (1) \,\leq^*\, is a total order and (2) for every x, y \in X, if x \leq y, then x \leq^* y. It is that second property that leads mathematicians to describe \,\leq^*\, as extending \,\leq. Alternatively, a linear extension may be viewed as an order-preserving bijection from a partially ordered set P to a chain C on the same ground set. Order-extension principle The statement that every partial order can be extended to a total order is known as the order-extension principle. A proof using the axiom of choice was first published by Edward Marczewski in 1930. Marczewski ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cyclic Order
In mathematics, a cyclic order is a way to arrange a set of objects in a circle. Unlike most structures in order theory, a cyclic order is not modeled as a binary relation, such as "". One does not say that east is "more clockwise" than west. Instead, a cyclic order is defined as a ternary relation , meaning "after , one reaches before ". For example, une, October, February but not une, February, October cf. picture. A ternary relation is called a cyclic order if it is cyclic, asymmetric, transitive, and connected. Dropping the "connected" requirement results in a partial cyclic order. A set with a cyclic order is called a cyclically ordered set or simply a cycle. Some familiar cycles are discrete, having only a finite number of elements: there are seven days of the week, four cardinal directions, twelve notes in the chromatic scale, and three plays in rock-paper-scissors. In a finite cycle, each element has a "next element" and a "previous element". There are also continu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Dedekind–MacNeille Completion
In mathematics, specifically order theory, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it. It is named after Holbrook Mann MacNeille whose 1937 paper first defined and constructed it, and after Richard Dedekind because its construction generalizes the Dedekind cuts used by Dedekind to construct the real numbers from the rational numbers. It is also called the completion by cuts or normal completion. Order embeddings and lattice completions A partially ordered set (poset) consists of a set of elements together with a binary relation on pairs of elements that is reflexive ( for every ''x''), transitive (if and then ), and antisymmetric (if both and hold, then ). The usual numeric orderings on the integers or real numbers satisfy these properties; however, unlike the orderings on the numbers, a partial order may have two elements that are ''incomparable'': neither nor holds. Another familiar example of a par ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
