|
Abstract Rewriting
In mathematical logic and theoretical computer science, an abstract rewriting system (also (abstract) reduction system or abstract rewrite system; abbreviated ARS) is a Formalism (mathematics), formalism that captures the quintessential notion and properties of rewriting systems. In its simplest form, an ARS is simply a set (mathematics), 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 form (abstract rewriting), normal forms, Termination (term rewriting), termination, and various notions of Confluence (abstract rewriting), 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 articl ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematical Logic
Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability 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 th ... [...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 A symmetric relation is a type of binary relation. Formally, a binary relation ''R'' over a set ''X'' is symmetric if: : \forall a, b \in X(a R b \Leftrightarrow b R a) , where the notation ''aRb'' means that . An example is the relation "is equ ... 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 * * References * Franz Baader and Tobias ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Jan Van Leeuwen
Jan van Leeuwen (born 17 December 1946 in Waddinxveen) is a Dutch computer scientist and emeritus professor of computer science at the Department of Information and Computing Sciences at Utrecht University.Curriculum vitae , retrieved 2011-03-27. Education and career Van Leeuwen completed his undergraduate studies in mathematics at in 1967 and received a PhD in mathematics in 1972 from the same institution under the supervision of Dirk van Dalen.. After postdoctoral studies at the |
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 Conferenc ... [...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 Path_ordering_(term_rewriting), multiset path ordering used to prove Rewriting#Termination, termination of term rewrite systems. Education and career He obtained his B.Sc., ''summa cum laude'', in 1974 in computer science and 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, and was hired as 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 University, Stanford, Université de Paris Orsay, Paris, Hebrew University, Jerusalem, University of Chicago, Chicago, and Tsinghua University, Beijing. He received the Herbrand Award for Distingu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Word Problem (mathematics)
In computational mathematics, a word problem is the decision problem, 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. Some deep results of computational theory concern the undecidable problem, undecidability of this question in many important cases. 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, produ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Well-founded Induction
In mathematics, a binary relation is called well-founded (or wellfounded or foundational) on a set or, more generally, a class if every non-empty subset has a minimal element with respect to ; that is, there exists an such that, for every , one does not have . In other words, a relation is well-founded if: (\forall S \subseteq X)\; \neq \varnothing \implies (\exists m \in S) (\forall s \in S) \lnot(s \mathrel m) Some authors include an extra condition that 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, meaning there is no infinite sequence of elements of such that for every natural number . In order theory, a partial order is called well-founded if the corresponding strict order is a well-founded relation. If the order is a total order then it is called a well-order. In set theory, a set is called a well-fou ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Newman's Lemma
In theoretical computer science, specifically in term rewriting, Newman's lemma, also commonly called the diamond lemma, is a criterion to prove that an abstract rewriting system is Confluence (abstract rewriting), confluent. It states that Confluence (abstract rewriting)#Local confluence, local confluence is a sufficient condition for confluence, provided that the system is also Abstract rewriting system#Termination and convergence, terminating. This is useful since local confluence is usually easier to verify than confluence. The lemma was originally proved by Max Newman in 1942. A considerably simpler proof (given below) was proposed by Gérard Huet. A number of other proofs exist. Statement and proof The lemma is purely combinatorial and applies to any relation. Owing to the context where it is commonly applied, it is stated below in the terminology of abstract rewriting systems (this is simply a set whose elements are called terms, equipped with a relation \to called reducti ... [...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 t ... [...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 desig ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lambda Calculus
In mathematical logic, the lambda calculus (also written as ''λ''-calculus) is a formal system for expressing computability, computation based on function Abstraction (computer science), abstraction and function application, application using variable Name binding, binding and Substitution (algebra), substitution. Untyped lambda calculus, the topic of this article, is a universal machine, a model of computation that can be used to simulate any Turing machine (and vice versa). It was introduced by the mathematician Alonzo Church in the 1930s as part of his research into the foundations of mathematics. In 1936, Church found a formulation which was #History, logically consistent, and documented it in 1940. Lambda calculus consists of constructing #Lambda terms, lambda terms and performing #Reduction, reduction operations on them. A term is defined as any valid lambda calculus expression. In the simplest form of lambda calculus, terms are built using only the following rules: # x: A ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Alonzo Church
Alonzo Church (June 14, 1903 – August 11, 1995) was an American computer scientist, mathematician, logician, and philosopher 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'' ("decision problem"), the Frege–Church ontology, and the Church–Rosser theorem. Alongside his doctoral 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 to 1901, and great-grandson of Alonzo Church, a professor of Mathematics and Astronomy and 6th President of the University of Ge ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
