Change search
ReferencesLink to record
Permanent link

Direct link
Network Rewriting I: The Foundation
Mälardalen University, School of Education, Culture and Communication. (Mathematics/Applied Mathematics)ORCID iD: 0000-0001-6140-180X
2012 (English)Report (Other academic)
Abstract [en]

A theory is developed which uses "networks" (directed acyclic graphs with some extra structure) as a formalism for expressions in multilinear algebra. It is shown that this formalism is valid for arbitrary PROPs (short for 'PROducts and Permutations category'), and conversely that the PROP axioms are implicit in the concept of evaluating a network. Ordinary terms and operads constitute the special case that the graph underlying the network is a rooted tree. Furthermore a rewriting theory for networks is developed. Included in this is a subexpression concept for which is given both algebraic and effective graph-theoretical characterisations, a construction of reduction maps from rewriting systems, and an analysis of the obstructions to confluence that can occur. Several Diamond Lemmas for this rewriting theory are given. In addition there is much supporting material on various related subjects. In particular there is a "toolbox" for the construction of custom orders on the free PROP, so that an order can be tailored to suit a specific rewriting system. Other subjects treated are the abstract index notation in a general PROP context and the use of feedbacks (sometimes called traces) in PROPs.

Place, publisher, year, edition, pages
Keyword [en]
Mathematics - Rings and Algebras, 16S15 (Primary) 18D10, 06F25, 15A69 (Secondary), F.4.2
National Category
Algebra and Logic
Research subject
Mathematics/Applied Mathematics
URN: urn:nbn:se:mdh:diva-20964OAI: diva2:642077

Accession Number: 1204.2421; DocumentType: working paper; Archive Set: Mathematics; Last Revision Date: 20120411

Available from: 2013-08-20 Created: 2013-08-20 Last updated: 2013-12-31Bibliographically approved

Open Access in DiVA

fulltext(1434 kB)85 downloads
File information
File name FULLTEXT01.pdfFile size 1434 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links

Search in DiVA

By author/editor
Hellström, Lars
By organisation
School of Education, Culture and Communication
Algebra and Logic

Search outside of DiVA

GoogleGoogle Scholar
Total: 85 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 26 hits
ReferencesLink to record
Permanent link

Direct link