umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Term graph rewriting and parallel term rewriting
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap. (Natural and Formal Languages)
2011 (Engelska)Ingår i: Proceedings of the 6th International Workshop on Computing with Terms and Graphs: Saarbrücken, Germany, 2nd April / [ed] Rachid Echahed, Open Publishing Association , 2011, s. 3-18Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
Open Publishing Association , 2011. s. 3-18
Serie
Electronic Proceedings in Theoretical Computer Science, ISSN 2075-2180 ; 48
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
datalogi
Identifikatorer
URN: urn:nbn:se:umu:diva-39797DOI: 10.4204/EPTCS.48.3OAI: oai:DiVA.org:umu-39797DiVA, id: diva2:396254
Konferens
TERMGRAPH 2011, 6th International Workshop on Computing with Terms and Graphs, Saarbrücken, Germany, 2nd April 2011
Tillgänglig från: 2012-04-13 Skapad: 2011-02-09 Senast uppdaterad: 2018-06-08Bibliografiskt granskad

Open Access i DiVA

fulltext(208 kB)229 nedladdningar
Filinformation
Filnamn FULLTEXT02.pdfFilstorlek 208 kBChecksumma SHA-512
265c2abf2e6232dfb71ecb28d3c5bf9e97dd97380af456318fe33218a92ca66f10599b5d996bee41e0bfccd2213a700496e47400b3921191e91924d2c5fcd967
Typ fulltextMimetyp application/pdf

Övriga länkar

Förlagets fulltext

Personposter BETA

Drewes, Frank

Sök vidare i DiVA

Av författaren/redaktören
Drewes, Frank
Av organisationen
Institutionen för datavetenskap
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 229 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 705 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf