|
Abstract Rewriting System
In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviated ARS) is a formalism that captures the quintessential notion and properties of rewriting systems. In its simplest form, an ARS is simply a set (of "objects") together with a binary relation, traditionally denoted with \rightarrow; this definition can be further refined if we index (label) subsets of the binary relation. Despite its simplicity, an ARS is sufficient to describe important properties of rewriting systems like normal forms, termination, and various notions of confluence. Historically, there have been several formalizations of rewriting in an abstract setting, each with its idiosyncrasies. This is due in part to the fact that some notions are equivalent, see below in this article. The formalization that is most commonly encountered in monographs and textbooks, and which is generally followed here, is due to Gérard ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematical Logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics. Since its inception, mathematical logic has both contributed to and been motivated by the study of foundations of mathematics. This study began in the late 19th century with the development of axiomatic frameworks for geometry, arithmetic, and Mathematical analysis, analysis. In the early 20th century it was shaped by David Hilbert's Hilbert's program, program to prove the consistency of foundational theories. Results of Kurt Gödel, Gerhard Gentzen, and others provided partial resolution to the program, and clarified the issues involved in pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Symmetric Closure
In mathematics, the symmetric closure of a binary relation R on a set X is the smallest symmetric relation on X that contains R. For example, if X is a set of airports and xRy means "there is a direct flight from airport x to airport y", then the symmetric closure of R is the relation "there is a direct flight either from x to y or from y to x". Or, if X is the set of humans and R is the relation 'parent of', then the symmetric closure of R is the relation "x is a parent or a child of y". Definition The symmetric closure S of a relation R on a set X is given by S = R \cup \. In other words, the symmetric closure of R is the union of R with its converse relation, R^. See also * * {{annotated link, Reflexive closure References * Franz Baader and Tobias Nipkow Tobias Nipkow (born 1958) is a German computer scientist. Career Nipkow received his Diplom (MSc) in computer science from the Department of Computer Science of the Technische Hochschule Darmstadt in 1982, and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Jean-Pierre Jouannaud
Jean-Pierre Jouannaud is a French computer scientist, known for his work in the area of term rewriting. He was born on 21 May 1947 in Aix-les-Bains (France). From 1967 to 1969 he visited the Ecole Polytechnique (Paris). In 1970, 1972, and 1977, he wrote his Master thesis (DEA), PhD thesis (Thèse de 3ème cycle), and Habilitation thesis ( Thèse d'état), respectively, at the Université de Paris VI. In 1979, he became an associate professor at the Nancy University; 1985 he changed to the Université de Paris-Sud, where he became a full professor in 1986. He was member of the steering committee of several international computer science conferences: International Conference on Rewriting Techniques and Applications (RTA) 1989-1994, IEEE Symposium on Logic in Computer Science (LICS) 1993-1997, Conference for Computer Science Logic (CSL) 1993-1997, International Conference on Principles and Practice of Constraint Programming (CP) since 1994, and Federated Logic Conference (FLoC) 1 ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Nachum Dershowitz
Nachum Dershowitz is an Israeli computer scientist, known e.g. for the Dershowitz–Manna ordering and the multiset path ordering used to prove termination of term rewrite systems. He obtained his B.Sc. summa cum laude in 1974 in Computer Science–Applied Mathematics from Bar-Ilan University, and his Ph.D. in 1979 in Applied Mathematics from the Weizmann Institute of Science. From 1978, he worked at the Department of Computer Science of the University of Illinois at Urbana-Champaign, until he became a full professor of the Tel Aviv University (School of Computer Science) in 1998. He was a guest researcher at Weizmann Institute, INRIA, ENS Cachan, Microsoft Research, and the universities of Stanford, Paris, Jerusalem, Chicago, and Beijing. He received the Herbrand Award for Distinguished Contributions to Automatic Reasoning in 2011. He has co-authored the standard text on calendar algorithms, ''Calendrical Calculations'', with Edward Reingold.Review of ''Calendrical Calculat ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Word Problem (mathematics)
In computational mathematics, a word problem is the problem of deciding whether two given expressions are equivalent with respect to a set of rewriting identities. A prototypical example is the word problem for groups, but there are many other instances as well. A deep result of computational theory is that answering this question is in many important cases undecidable. Background and motivation In computer algebra one often wishes to encode mathematical expressions using an expression tree. But there are often multiple equivalent expression trees. The question naturally arises of whether there is an algorithm which, given as input two expressions, decides whether they represent the same element. Such an algorithm is called a ''solution to the word problem''. For example, imagine that x,y,z are symbols representing real numbers - then a relevant solution to the word problem would, given the input (x \cdot y)/z \mathrel (x/z)\cdot y, produce the output EQUAL, and similarly pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Well-founded Induction
In mathematics, a binary relation ''R'' is called well-founded (or wellfounded) on a class ''X'' if every non-empty subset ''S'' ⊆ ''X'' has a minimal element with respect to ''R'', that is, an element ''m'' not related by ''s R m'' (for instance, "''s'' is not smaller than ''m''") for any ''s'' ∈ ''S''. In other words, a relation is well founded if :(\forall S \subseteq X)\; \neq \emptyset \implies (\exists m \in S) (\forall s \in S) \lnot(s \mathrel m) Some authors include an extra condition that ''R'' is set-like, i.e., that the elements less than any given element form a set. Equivalently, assuming the axiom of dependent choice, a relation is well-founded when it contains no infinite descending chains, which can be proved when there is no infinite sequence ''x''0, ''x''1, ''x''2, ... of elements of ''X'' such that ''x''''n''+1 ''R'' ''x''n for every natural number ''n''. In order theory, a partial order is called well-founded ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Newman's Lemma
In mathematics, in the theory of rewriting systems, Newman's lemma, also commonly called the diamond lemma, states that a terminating (or strongly normalizing) abstract rewriting system (ARS), that is, one in which there are no infinite reduction sequences, is confluent if it is locally confluent. In fact a terminating ARS is confluent precisely when it is locally confluent. Equivalently, for every binary relation with no decreasing infinite chains and satisfying a weak version of the diamond property, there is a unique minimal element in every connected component of the relation considered as a graph. Today, this is seen as a purely combinatorial result based on well-foundedness due to a proof of Gérard Huet in 1980. Newman's original proof was considerably more complicated. Diamond lemma In general, Newman's lemma can be seen as a combinatorial result about binary relations → on a set ''A'' (written backwards, so that ''a'' → ''b'' means that ''b'' is below ''a'') wit ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Noetherian Relation
In mathematics, the adjective Noetherian is used to describe objects that satisfy an ascending or descending chain condition on certain kinds of subobjects, meaning that certain ascending or descending sequences of subobjects must have finite length. Noetherian objects are named after Emmy Noether, who was the first to study the ascending and descending chain conditions for rings. Specifically: * Noetherian group, a group that satisfies the ascending chain condition on subgroups. * Noetherian ring, a ring that satisfies the ascending chain condition on ideals. * Noetherian module, a module that satisfies the ascending chain condition on submodules. * More generally, an object in a category is said to be Noetherian if there is no infinitely increasing filtration of it by subobjects. A category is Noetherian if every object in it is Noetherian. * Noetherian relation, a binary relation that satisfies the ascending chain condition on its elements. * Noetherian topological space, a topolo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Cyclic Locally, But Not Globally Confluent Rewrite System
Cycle, cycles, or cyclic may refer to: Anthropology and social sciences * Cyclic history, a theory of history * Cyclical theory, a theory of American political history associated with Arthur Schlesinger, Sr. * Social cycle, various cycles in social sciences ** Business cycle, the downward and upward movement of gross domestic product (GDP) around its ostensible, long-term growth trend Arts, entertainment, and media Films * ''Cycle'' (2008 film), a Malayalam film * ''Cycle'' (2017 film), a Marathi film Literature * ''Cycle'' (magazine), an American motorcycling enthusiast magazine * Literary cycle, a group of stories focused on common figures Music Musical terminology * Cycle (music), a set of musical pieces that belong together **Cyclic form, a technique of construction involving multiple sections or movements **Interval cycle, a collection of pitch classes generated from a sequence of the same interval class **Song cycle, individually complete songs designed to be performe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lambda Calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation that can be used to simulate any Turing machine. It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. Lambda calculus consists of constructing § lambda terms and performing § reduction operations on them. In the simplest form of lambda calculus, terms are built using only the following rules: * x – variable, a character or string representing a parameter or mathematical/logical value. * (\lambda x.M) – abstraction, function definition (M is a lambda term). The variable x becomes bound in the expression. * (M\ N) – application, applying a function M to an argument N. M and N are lambda terms. The reduction operations include: * (\lambda x.M \rightarrow(\l ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Alonzo Church
Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician, computer scientist, logician, philosopher, professor and editor who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, the Church–Turing thesis, proving the unsolvability of the Entscheidungsproblem, the Frege–Church ontology, and the Church–Rosser theorem. He also worked on philosophy of language (see e.g. Church 1970). Alongside his student Alan Turing, Church is considered one of the founders of computer science. Life Alonzo Church was born on June 14, 1903, in Washington, D.C., where his father, Samuel Robbins Church, was a Justice of the Peace and the judge of the Municipal Court for the District of Columbia. He was the grandson of Alonzo Webster Church (1829-1909), United States Senate Librarian from 1881-1901, and great grandson of Alonzo Church, a Professor of Mathematics and Astronomy and 6th Pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Composition Of Relations
In the mathematics of binary relations, the composition of relations is the forming of a new binary relation from two given binary relations ''R'' and ''S''. In the calculus of relations, the composition of relations is called relative multiplication, and its result is called a relative product. Function composition is the special case of composition of relations where all relations involved are functions. The word uncle indicates a compound relation: for a person to be an uncle, he must be the brother of a parent. In algebraic logic it is said that the relation of Uncle (x U z) is the composition of relations "is a brother of" (x B y) and "is a parent of" (y P z). U = BP \quad \text \quad xByPz \text xUz. Beginning with Augustus De Morgan, the traditional form of reasoning by syllogism has been subsumed by relational logical expressions and their composition. Definition If R \subseteq X \times Y and S \subseteq Y \times Z are two binary relations, then their composition R; ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
