Definition and Expansion of Composite Automata in IOA
The IOA language provides notations for defining both primitive and composite I/O automata.This note describes, both formally and with examples, the constraints on these definitions, thecomposability requirements for the components of a composite automaton, and the transformationof a composite autom...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Language: | en_US |
| Published: |
2005
|
| Online Access: | http://hdl.handle.net/1721.1/30487 |
| _version_ | 1826210881585807360 |
|---|---|
| author | Tauber, Joshua A. Garland, Stephen J. |
| author2 | Theory of Computation |
| author_facet | Theory of Computation Tauber, Joshua A. Garland, Stephen J. |
| author_sort | Tauber, Joshua A. |
| collection | MIT |
| description | The IOA language provides notations for defining both primitive and composite I/O automata.This note describes, both formally and with examples, the constraints on these definitions, thecomposability requirements for the components of a composite automaton, and the transformationof a composite automaton into an equivalent primitive automaton.Section 2 introduces four examples used throughout this note to illustrate new definitions andoperations. Section 3 treats IOA programs for primitive I/O automata: it introduces notationsfor describing the syntactic structures that appear in these programs, and it lists syntactic andsemantic conditions that these programs must satisfy to represent valid primitive I/O automata.Section 4 describes how to reformulate primitive IOA programs into an equivalent but more regular(desugared) form that is used in later definitions in this note. Section 5 treats IOA programsfor composite I/O automata: it introduces notations for describing the syntactic structures thatappear in these programs, describes resortings induced by them, and lists syntactic and semanticconditions that these programs must satisfy to represent valid composite I/O automata. Section 6describes the translation of the name spaces of component automata into a unified name spacefor the composite automaton. Section 7 shows how to expand an IOA program for a compositeautomaton into an equivalent IOA program for a primitive automaton. The expansion is generatedby combining syntactic structures of the desugared programs for the component automata afterapplying appropriate replacements of sorts and variables. Section 8 details the expansion of thecomposite automaton introduced in Section 2 using the desugared forms developed throughoutSections 4Â6 and the techniques described in Section 7. Finally, Section 9 gives a precise definitionof the resortings and substitutions used to replace sorts and variables. |
| first_indexed | 2024-09-23T14:57:15Z |
| id | mit-1721.1/30487 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:57:15Z |
| publishDate | 2005 |
| record_format | dspace |
| spelling | mit-1721.1/304872019-04-11T06:23:32Z Definition and Expansion of Composite Automata in IOA Tauber, Joshua A. Garland, Stephen J. Theory of Computation The IOA language provides notations for defining both primitive and composite I/O automata.This note describes, both formally and with examples, the constraints on these definitions, thecomposability requirements for the components of a composite automaton, and the transformationof a composite automaton into an equivalent primitive automaton.Section 2 introduces four examples used throughout this note to illustrate new definitions andoperations. Section 3 treats IOA programs for primitive I/O automata: it introduces notationsfor describing the syntactic structures that appear in these programs, and it lists syntactic andsemantic conditions that these programs must satisfy to represent valid primitive I/O automata.Section 4 describes how to reformulate primitive IOA programs into an equivalent but more regular(desugared) form that is used in later definitions in this note. Section 5 treats IOA programsfor composite I/O automata: it introduces notations for describing the syntactic structures thatappear in these programs, describes resortings induced by them, and lists syntactic and semanticconditions that these programs must satisfy to represent valid composite I/O automata. Section 6describes the translation of the name spaces of component automata into a unified name spacefor the composite automaton. Section 7 shows how to expand an IOA program for a compositeautomaton into an equivalent IOA program for a primitive automaton. The expansion is generatedby combining syntactic structures of the desugared programs for the component automata afterapplying appropriate replacements of sorts and variables. Section 8 details the expansion of thecomposite automaton introduced in Section 2 using the desugared forms developed throughoutSections 4Â6 and the techniques described in Section 7. Finally, Section 9 gives a precise definitionof the resortings and substitutions used to replace sorts and variables. 2005-12-22T01:35:52Z 2005-12-22T01:35:52Z 2004-07-19 MIT-CSAIL-TR-2004-048 MIT-LCS-TR-959 http://hdl.handle.net/1721.1/30487 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 91 p. 77470182 bytes 2979546 bytes application/postscript application/pdf application/postscript application/pdf |
| spellingShingle | Tauber, Joshua A. Garland, Stephen J. Definition and Expansion of Composite Automata in IOA |
| title | Definition and Expansion of Composite Automata in IOA |
| title_full | Definition and Expansion of Composite Automata in IOA |
| title_fullStr | Definition and Expansion of Composite Automata in IOA |
| title_full_unstemmed | Definition and Expansion of Composite Automata in IOA |
| title_short | Definition and Expansion of Composite Automata in IOA |
| title_sort | definition and expansion of composite automata in ioa |
| url | http://hdl.handle.net/1721.1/30487 |
| work_keys_str_mv | AT tauberjoshuaa definitionandexpansionofcompositeautomatainioa AT garlandstephenj definitionandexpansionofcompositeautomatainioa |