Formal Properties of Well-formed Data Flow Schemas
This thesis presents some results in comparative schematology and some undecidability results for two models of computer programs: the class of flowchart schemas and the class of well-formed data flow schemas (wfdfs's). Algorithms are given for translating a schema in each class into an equival...
| Main Author: | |
|---|---|
| Other Authors: | |
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/148894 |
| _version_ | 1811081473659240448 |
|---|---|
| author | Leung, Clement Kin Cho |
| author2 | Dennis, Jack B. |
| author_facet | Dennis, Jack B. Leung, Clement Kin Cho |
| author_sort | Leung, Clement Kin Cho |
| collection | MIT |
| description | This thesis presents some results in comparative schematology and some undecidability results for two models of computer programs: the class of flowchart schemas and the class of well-formed data flow schemas (wfdfs's). Algorithms are given for translating a schema in each class into an equivalent schema in the other class. The propertiees of freedom, _-freedom, openness, and completeness are defined and studied. For every path P in a free flowchart schema S, there exists an interpretation under which the flow of controls through S is along P. _-freedom is a generalization of freedom and captures the notion of freedom for wfdfs's. An open schema is one in which no basic component is redundant and a complete schema contains no subschema which, whenever enabled, does not terminate. A comparison of the expressive power of subclasses of flowchart schemas and wfdfs's possessing various combinations of these properties is made. It is shown that the class of free flowchart schemas properly contains the classes of free and _-free wfdfs's , and that the class of open and complete flowchart schemas is equivalent in expressive power to the class of open and complete wfdfs's. Three undecidabilty results for open and complete program schemas are established: openness is undecidable for complete program schemas, completeness is undecidable for open program schemas, and equivalence is undecidable for open and complete program schemas. |
| first_indexed | 2024-09-23T11:47:14Z |
| id | mit-1721.1/148894 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T11:47:14Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1488942023-03-30T03:49:40Z Formal Properties of Well-formed Data Flow Schemas Leung, Clement Kin Cho Dennis, Jack B. This thesis presents some results in comparative schematology and some undecidability results for two models of computer programs: the class of flowchart schemas and the class of well-formed data flow schemas (wfdfs's). Algorithms are given for translating a schema in each class into an equivalent schema in the other class. The propertiees of freedom, _-freedom, openness, and completeness are defined and studied. For every path P in a free flowchart schema S, there exists an interpretation under which the flow of controls through S is along P. _-freedom is a generalization of freedom and captures the notion of freedom for wfdfs's. An open schema is one in which no basic component is redundant and a complete schema contains no subschema which, whenever enabled, does not terminate. A comparison of the expressive power of subclasses of flowchart schemas and wfdfs's possessing various combinations of these properties is made. It is shown that the class of free flowchart schemas properly contains the classes of free and _-free wfdfs's , and that the class of open and complete flowchart schemas is equivalent in expressive power to the class of open and complete wfdfs's. Three undecidabilty results for open and complete program schemas are established: openness is undecidable for complete program schemas, completeness is undecidable for open program schemas, and equivalence is undecidable for open and complete program schemas. 2023-03-29T14:05:42Z 2023-03-29T14:05:42Z 1975-06 https://hdl.handle.net/1721.1/148894 02094205 MIT-LCS-TM-066 MAC-TM-066 application/pdf |
| spellingShingle | Leung, Clement Kin Cho Formal Properties of Well-formed Data Flow Schemas |
| title | Formal Properties of Well-formed Data Flow Schemas |
| title_full | Formal Properties of Well-formed Data Flow Schemas |
| title_fullStr | Formal Properties of Well-formed Data Flow Schemas |
| title_full_unstemmed | Formal Properties of Well-formed Data Flow Schemas |
| title_short | Formal Properties of Well-formed Data Flow Schemas |
| title_sort | formal properties of well formed data flow schemas |
| url | https://hdl.handle.net/1721.1/148894 |
| work_keys_str_mv | AT leungclementkincho formalpropertiesofwellformeddataflowschemas |