- Information algebra
information theorygoes back to Claude Shannon. It is a theory of information transmission, looking at communication and storage. However, it has not been considered so far that information comes from different sources and that it is therefore usually combined. It has furthermore been neglected in classical information theory that one wants to extract those parts out of a piece of information that are relevant to specific questions.
A mathematical phrasing of these operations leads to an algebra of information, describing basic modes of information processing. Such an algebra grasps a lot of formalisms of
computer science, which seem to be different on the surface: relational databases, multiple systems of formal logic or numerical problems of linear algebra. It allows the development of generic procedures of information processing and thus a unification of basic methods of computer science, in particular of distributed information processing.
Information relates to precise questions, comes from different sources, must be aggregated and can be focused on questions of interest. Starting from these considerations, information algebras Harv|Kohlas|2003 are two
sorted algebras , where is a semigroup, representing combination or aggregation of information, is a latticeof domains (related to questions) whose partial orderreflects the granularity of the domain or the question, and a mixed operationrepresenting focusing or extraction of information.
Information and its operations
More precisely, in the two-sorted algebra , the following operations are defined
Models of information algebras
Here follows an incomplete list of instances of information algebras:
Relational algebra: The reduct of a relational algebra with natural join as combination and the usual projection is a labeled information algebra, see .
Constraint systems: Constraints form an information algebra Harv|Jaffar|Maher|1994.
Semiring valued algebras: C-Semirings induce information algebras Harv|Bistarelli|Montanari|Rossi1997;Harv|Bistarelli|Fargier|Montanari|Rossi|Schiex|Verfaillie|1999;Harv|Kohlas|Wilson|2006.
Logic: Many logic systems induce information algebras Harv|Wilson|Mengin|1999. Reducts of cylindrical algebras Harv|Henkin|Monk|Tarski|1971 or polyadic algebras are information algebras related to predicate logic Harv|Halmos|2000.
Module algebras: Harv|Bergstra|Heering|Klint|1990;Harv|de Lavalette|1992.
Linear systems: Systems of linear equations or linear inequalities induce information algebras Harv|Kohlas|2003.
Worked-out Example: Relational Algebra
Let be a set of symbols, called attributes (or columnnames). For each let be a non-empty set, theset of all possible values of the attribute . For example, if , then couldbe the set of strings, whereas and are boththe set of non-negative integers.
Let . An -tuple is a function so that and for each The setof all -tuples is denoted by . For an -tuple and a subset the restriction is defined to be the-tuple so that for all .
A relation over is a set of -tuples, i.e. a subset of .The set of attributes is called the domain of and denoted by. For the projection of onto is definedas follows::The join of a relation over and a relation over isdefined as follows::As an example, let and be the following relations::Then the join of and is::A relational database with natural join as combination and the usual projection is an information algebra.The operations are well defined since
- If , then .
; Valuation Algebras : Dropping the idempotency axiom leads to Valuation Algebras. These axioms have been introduced by Harv|Shenoy|Shafer|1990 to generalize "local computation schemes" Harv|Lauritzen|Spiegelhalter|1988 from Bayesian networks to more general formalisms (including belief function, possibility potentials, etc.) Harv|Kohlas |Shenoy|2000.; Domains and Information Systems: "Compact Information Algebras" Harv|Kohlas|2003 are related to Scott domains and Scott information systems Harv|Scott|1970;Harv|Scott|1982;Harv|Larsen|Winskel|1984.; Uncertain Information : Random variables with values in information algebras represent "probabilistic argumentation systems" Harv|Haenni|Kohlas|Lehmann|2000.; Semantic Information : Information algebras introduce semantics by relating information to questions through focusing and combination Harv|Groenendijk|Stokhof|1984;Harv|Floridi|2004.; Information Flow : Information algebras are related to information flow, in particular classifications Harv|Barwise|Seligman|1997.; Tree decomposition : ...; Semigroup theory : ...
The axioms for information algebras are derived from the axiom system proposed in (Shenoy and Shafer, 1990), see also (Shafer, 1991).
Harvard reference | Given=Gerard R. Renardel | Surname=de Lavalette | Chapter= Logical semantics of modularisation | Editor=Egon Börger, Gerhard Jäger, Hans Kleine Büning, and Michael M. Richter | Title=CSL: 5th Workshop on Computer Science Logic | Pages=306–315 | Publisher=Volume 626 of Lecture Notes in Computer Science, Springer | Year=1992 | ISBN=3-540-55789-X
Harvard reference | Given1=K. G. | Surname1=Larsen | Given2=G. |Surname2=Winskel | Chapter=Using information systems to solve recursive domain equations effectively | Editor=Gilles Kahn, David B. MacQueen, and Gordon D. Plotkin | Title=Semantics of Data Types, International Symposium, Sophia-Antipolis, France, June 27-29, 1984, Proceedings | Volume=173 of Lec- ture Notes in Computer Science | Pages=109–129 | Location=Berlin | Year= 1984 | Publisher=Springer
Harvard reference | Given1=S. L. | Surname1= Lauritzen |Given2=D. J.|Surname2=Spiegelhalter | Title=Local computations with probabilities on graphical structures and their application to expert systems | Journal= J. Royal Statis. Soc. B |Volume= 50 | Pages=157–224 | Year= 1988
Harvard reference | Given=Dana S. | Surname= Scott | Title= Outline of a mathematical theory of computation | Publisher=Technical Monograph PRG–2, Oxford University Computing Laboratory, Programming Research Group | Year=1970
Harvard reference | Given1=P. P. | Surname1=Shenoy | Given2=G. | Surname2=Shafer | Chapter=Axioms for probability and belief-function proagation | Editor=Ross D. Shachter, Tod S. Levitt, Laveen N. Kanal, and John F. Lemmer | Title= Uncertainty in Artificial Intelligence 4 | Volume= 9 | Journal= Machine intelligence and pattern recognition |Pages = 169–198 | Place=Amsterdam | Year= 1990 | Publisher=Elsevier | ISBN= 0-444-88650-8
Harvard reference | Given1=Nic | Surname1=Wilson |Given2= Jérôme | Surname2= Mengin | Chapter=Logical deduction using the local computation framework | Editor=Anthony Hunter and Simon Parsons, | Title=Symbolic and Quantitative Approaches to Reasoning and Uncertainty, European Confer- ence, ECSQARU’99, London, UK, July 5-9, 1999, Proceedings, volume 1638 of Lecture Notes in Computer Science | Pages= 386–396 | Publisher= Springer | Year= 1999 | ISBN = 3-540-66131-X | URL = http://springerlink.metapress.com/openurl.asp?genre=article&issn=0302-9743&volume=1638&spage=0386
Wikimedia Foundation. 2010.
Look at other dictionaries:
Information theory — Not to be confused with Information science. Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental… … Wikipedia
Information Integration Theory — was proposed by Norman H. Anderson to describe and model how a person integrates information from a number of sources in to make an overall judgment. The theory proposes three functions.  The valuation function V(S) is an empirically derived… … Wikipedia
algebra — /al jeuh breuh/, n. 1. the branch of mathematics that deals with general statements of relations, utilizing letters and other symbols to represent specific sets of numbers, values, vectors, etc., in the description of such relations. 2. any of… … Universalium
Algebra — This article is about the branch of mathematics. For other uses, see Algebra (disambiguation). Algebra is the branch of mathematics concerning the study of the rules of operations and relations, and the constructions and concepts arising from… … Wikipedia
Information theory and measure theory — Measures in information theory = Many of the formulas in information theory have separate versions for continuous and discrete cases, i.e. integrals for the continuous case and sums for the discrete case. These versions can often be generalized… … Wikipedia
Information science — Not to be confused with Information theory. Contents 1 Introduction 2 A multitude of information sciences? 3 Definitions of information science 4 History … Wikipedia
information theory — the mathematical theory concerned with the content, transmission, storage, and retrieval of information, usually in the form of messages or data, and esp. by means of computers. [1945 50] * * * ▪ mathematics Introduction a mathematical… … Universalium
information processing — Acquisition, recording, organization, retrieval, display, and dissemination of information. Today the term usually refers to computer based operations. Information processing consists of locating and capturing information, using software to… … Universalium
Homological algebra — is the branch of mathematics which studies homology in a general algebraic setting. It is a relatively young discipline, whose origins can be traced to investigations in combinatorial topology (a precursor to algebraic topology) and abstract… … Wikipedia
History of algebra — Elementary algebra is the branch of mathematics that deals with solving for the operands of arithmetic equations. Modern or abstract algebra has its origins as an abstraction of elementary algebra. Historians know that the earliest mathematical… … Wikipedia