|
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 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 analysis. In the early 20th century it was shaped by David Hilbert's 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 proving consistency. Work in set theory s ... [...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, ... [...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) ... [...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 Calculati ... [...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 |
