umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Term graph rewriting and parallel term rewriting
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Natural and Formal Languages)
2011 (English)In: Proceedings of the 6th International Workshop on Computing with Terms and Graphs: Saarbrücken, Germany, 2nd April / [ed] Rachid Echahed, Open Publishing Association , 2011, 3-18 p.Conference paper, Published paper (Refereed)
Abstract [en]

The relationship between Term Graph Rewriting and Term Rewriting is well understood: a single term graph reduction may correspond to several term reductions, due to sharing. It is also known that if term graphs are allowed to contain cycles, then one term graph reduction may correspond to infinitely many term reductions. We stress that this fact can be interpreted in two ways. According to the "sequential interpretation", a term graph reduction corresponds to an infinite sequence of term reductions, as formalized by Kennaway et.al. using strongly converging derivations over the complete metric space of infinite terms. Instead according to the "parallel interpretation" a term graph reduction corresponds to the parallel reduction of an infinite set of redexes in a rational term. We formalize the latter notion by exploiting the complete partial order of infinite and possibly partial terms, and we stress that this interpretation allows to explain the result of reducing circular redexes in several approaches to term graph rewriting.

Place, publisher, year, edition, pages
Open Publishing Association , 2011. 3-18 p.
Series
Electronic Proceedings in Theoretical Computer Science, ISSN 2075-2180 ; 48
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-39797DOI: 10.4204/EPTCS.48.3OAI: oai:DiVA.org:umu-39797DiVA: diva2:396254
Conference
TERMGRAPH 2011, 6th International Workshop on Computing with Terms and Graphs, Saarbrücken, Germany, 2nd April 2011
Available from: 2012-04-13 Created: 2011-02-09 Last updated: 2012-04-13Bibliographically approved

Open Access in DiVA

fulltext(208 kB)161 downloads
File information
File name FULLTEXT02.pdfFile size 208 kBChecksum SHA-512
265c2abf2e6232dfb71ecb28d3c5bf9e97dd97380af456318fe33218a92ca66f10599b5d996bee41e0bfccd2213a700496e47400b3921191e91924d2c5fcd967
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Search in DiVA

By author/editor
Drewes, Frank
By organisation
Department of Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 161 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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 105 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf