{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/19683"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/19683","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Specification of concurrent systems using graph grammars","abstract":"Existing textual programming languages support sequential programming well because there is a correlation between the one-dimensional nature of text and the one-dimensional nature of sequential programs, i.e. the single flow of control in a program. Textual notation does not support concurrent programming as well, however, because concurrent programs have many threads of control, have a two-dimensional relationship between the flow of control in a process and the flow of information between processes, and are often dynamic. Most existing models for the specification of concurrent systems support one or two of these traits, but fall short of supporting all three.","abstract_html":"Existing textual programming languages support sequential programming well because there is a correlation between the one-dimensional nature of text and the one-dimensional nature of sequential programs, i.e. the single flow of control in a program. Textual notation does not support concurrent programming as well, however, because concurrent programs have many threads of control, have a two-dimensional relationship between the flow of control in a process and the flow of information between processes, and are often dynamic. Most existing models for the specification of concurrent systems support one or two of these traits, but fall short of supporting all three.","abstract_has_math":false,"creators":["Loyall, Joseph Patrick"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Kaplan, Simon M."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2011,"date_issued":"2011-05-07T12:15:11Z","date_published":"2011-05-07T12:15:11Z","updated_at":"2026-07-22T22:25:14Z","subjects":["Computer Science"],"languages":["eng"],"rights":["Copyright 1991 Loyall, Joseph Patrick"],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9210902","(UMI)AAI9210902"],"render_values":[{"text":"AAI9210902","href":null,"code":true},{"text":"(UMI)AAI9210902","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/19683","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Kaplan, Simon M."]},{"key":"dc:creator","label":"Author","values":["Loyall, Joseph Patrick"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2011-05-07T12:15:11Z","10000-01-01","1991"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 1991 Loyall, Joseph Patrick"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["AAI9210902","(UMI)AAI9210902","http://hdl.handle.net/2142/19683"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Existing textual programming languages support sequential programming well because there is a correlation between the one-dimensional nature of text and the one-dimensional nature of sequential programs, i.e. the single flow of control in a program. Textual notation does not support concurrent programming as well, however, because concurrent programs have many threads of control, have a two-dimensional relationship between the flow of control in a process and the flow of information between processes, and are often dynamic. Most existing models for the specification of concurrent systems support one or two of these traits, but fall short of supporting all three.","Graph grammars are well suited for the specification of concurrent systems because they are also inherently concurrent, two-dimensional, and dynamic. We have developed a general graph rewriting model, $\\Delta$-grammars, based on the theory of graph grammars. Concurrent systems are specified in A by representing the state of the system as a graph and state transitions as graph transformations. Previously, we have developed a formal semantics for $\\Delta$-grammars and demonstrated its usefulness for giving a graphical semantics of existing concurrent languages, such as Actors and GARP.","This thesis shows $\\Delta$'s usefulness as a specification language. It describes how specifications are modularly and systematically designed in $\\Delta$. It also describes a technique for the static analysis of $\\Delta$-specifications. Classes of $\\Delta$-specifications that are confluent, terminating, deadlock-free, starvation-free, or efficient to execute are recognized by examining the structure of $\\Delta$-productions and the way in which $\\Delta$-productions interact, both with other $\\Delta$-productions and with state graphs. The technique for static analysis can be used to analyze existing $\\Delta$-specifications and as a guideline for the design of correct $\\Delta$-specifications.","The techniques are illustrated throughout with examples and tutorial introductions to graph grammars and $\\Delta$-grammars are included.","Made available in DSpace on 2011-05-07T12:15:11Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9210902.pdf: 8401265 bytes, checksum: 6c47633dd064824ab240e7a4d3e2a057 (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:38:43Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:16:11-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"]},{"key":"dc:title","label":"Title","values":["Specification of concurrent systems using graph grammars"]}]}],"canonical_facts":{"dc:contributor":["Kaplan, Simon M."],"dc:creator":["Loyall, Joseph Patrick"],"dc:date":["2011-05-07T12:15:11Z","10000-01-01","1991"],"dc:description":["Existing textual programming languages support sequential programming well because there is a correlation between the one-dimensional nature of text and the one-dimensional nature of sequential programs, i.e. the single flow of control in a program. Textual notation does not support concurrent programming as well, however, because concurrent programs have many threads of control, have a two-dimensional relationship between the flow of control in a process and the flow of information between processes, and are often dynamic. Most existing models for the specification of concurrent systems support one or two of these traits, but fall short of supporting all three.","Graph grammars are well suited for the specification of concurrent systems because they are also inherently concurrent, two-dimensional, and dynamic. We have developed a general graph rewriting model, $\\Delta$-grammars, based on the theory of graph grammars. Concurrent systems are specified in A by representing the state of the system as a graph and state transitions as graph transformations. Previously, we have developed a formal semantics for $\\Delta$-grammars and demonstrated its usefulness for giving a graphical semantics of existing concurrent languages, such as Actors and GARP.","This thesis shows $\\Delta$'s usefulness as a specification language. It describes how specifications are modularly and systematically designed in $\\Delta$. It also describes a technique for the static analysis of $\\Delta$-specifications. Classes of $\\Delta$-specifications that are confluent, terminating, deadlock-free, starvation-free, or efficient to execute are recognized by examining the structure of $\\Delta$-productions and the way in which $\\Delta$-productions interact, both with other $\\Delta$-productions and with state graphs. The technique for static analysis can be used to analyze existing $\\Delta$-specifications and as a guideline for the design of correct $\\Delta$-specifications.","The techniques are illustrated throughout with examples and tutorial introductions to graph grammars and $\\Delta$-grammars are included.","Made available in DSpace on 2011-05-07T12:15:11Z (GMT). No. of bitstreams: 2 license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5) 9210902.pdf: 8401265 bytes, checksum: 6c47633dd064824ab240e7a4d3e2a057 (MD5) Previous issue date: 1991","Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding (hding2@illinois.edu) on 2011-05-07T14:38:43Z Item is restricted indefinitely.","Restriction data tranferred 2014-07-01T11:16:11-05:00 Original Data Group with Access UIUC Users [automated] Release Date: none Reason: ETDs are only available to UIUC Users without author permission","ETDs are only available to UIUC Users without author permission","U of I Only"],"dc:identifier":["AAI9210902","(UMI)AAI9210902","http://hdl.handle.net/2142/19683"],"dc:language":["eng"],"dc:rights":["Copyright 1991 Loyall, Joseph Patrick"],"dc:subject":["Computer Science"],"dc:title":["Specification of concurrent systems using graph grammars"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:14Z"}