Systematic Removal of Nondeterminism for Code Generation in I/O Automata

The Input/Output (I/O) automaton model developed by Lynch and Tuttle models components in asynchronous concurrentsystems as labeled transition systems. IOA is a precise language for describing I/O automata and for stating their properties. A toolset is beingdeveloped for IOA to support distribu...

Full description

Bibliographic Details
Main Authors: Vaziri, Mandana, Tauber, Joshua A., Tsai, Michael J., Lynch, Nancy
Other Authors: Theory of Computation
Language:en_US
Published: 2005
Online Access:http://hdl.handle.net/1721.1/30486
_version_ 1826197164682903552
author Vaziri, Mandana
Tauber, Joshua A.
Tsai, Michael J.
Lynch, Nancy
author2 Theory of Computation
author_facet Theory of Computation
Vaziri, Mandana
Tauber, Joshua A.
Tsai, Michael J.
Lynch, Nancy
author_sort Vaziri, Mandana
collection MIT
description The Input/Output (I/O) automaton model developed by Lynch and Tuttle models components in asynchronous concurrentsystems as labeled transition systems. IOA is a precise language for describing I/O automata and for stating their properties. A toolset is beingdeveloped for IOA to support distributed software design and implementation. One of the tools consists of a userassisted code generator fromIOA into an imperative programming language such as C or Java. One aspect that distinguishes IOA programs from programs written inimperative languages is the presence of nondeterminism which comesin the form of explicit nondeterministic statements and implicit scheduling choices made during execution. Code generation therefore consistspartially of systematically removing all forms of nondeterminism. In this paper, we describe our approach and design for code generation.We focus on the issue of removing implicit nondeterminism and specify a transformation on IOA programs that makes all nondeterminismexplicit. The programmer can then replace all explicit nondeterminismwith deterministic statements prior to code generation. We also describethis transformation at a semantic level i.e., at the level of the I/O automaton mathematical model. We show that the transformation definedat the IOA level conforms to the one at the semantic level.
first_indexed 2024-09-23T10:43:30Z
id mit-1721.1/30486
institution Massachusetts Institute of Technology
language en_US
last_indexed 2024-09-23T10:43:30Z
publishDate 2005
record_format dspace
spelling mit-1721.1/304862019-04-11T06:23:32Z Systematic Removal of Nondeterminism for Code Generation in I/O Automata Vaziri, Mandana Tauber, Joshua A. Tsai, Michael J. Lynch, Nancy Theory of Computation The Input/Output (I/O) automaton model developed by Lynch and Tuttle models components in asynchronous concurrentsystems as labeled transition systems. IOA is a precise language for describing I/O automata and for stating their properties. A toolset is beingdeveloped for IOA to support distributed software design and implementation. One of the tools consists of a userassisted code generator fromIOA into an imperative programming language such as C or Java. One aspect that distinguishes IOA programs from programs written inimperative languages is the presence of nondeterminism which comesin the form of explicit nondeterministic statements and implicit scheduling choices made during execution. Code generation therefore consistspartially of systematically removing all forms of nondeterminism. In this paper, we describe our approach and design for code generation.We focus on the issue of removing implicit nondeterminism and specify a transformation on IOA programs that makes all nondeterminismexplicit. The programmer can then replace all explicit nondeterminismwith deterministic statements prior to code generation. We also describethis transformation at a semantic level i.e., at the level of the I/O automaton mathematical model. We show that the transformation definedat the IOA level conforms to the one at the semantic level. 2005-12-22T01:35:40Z 2005-12-22T01:35:40Z 2004-07-19 MIT-CSAIL-TR-2004-047 MIT-LCS-TR-960 http://hdl.handle.net/1721.1/30486 en_US Massachusetts Institute of Technology Computer Science and Artificial Intelligence Laboratory 16 p. 14677208 bytes 626419 bytes application/postscript application/pdf application/postscript application/pdf
spellingShingle Vaziri, Mandana
Tauber, Joshua A.
Tsai, Michael J.
Lynch, Nancy
Systematic Removal of Nondeterminism for Code Generation in I/O Automata
title Systematic Removal of Nondeterminism for Code Generation in I/O Automata
title_full Systematic Removal of Nondeterminism for Code Generation in I/O Automata
title_fullStr Systematic Removal of Nondeterminism for Code Generation in I/O Automata
title_full_unstemmed Systematic Removal of Nondeterminism for Code Generation in I/O Automata
title_short Systematic Removal of Nondeterminism for Code Generation in I/O Automata
title_sort systematic removal of nondeterminism for code generation in i o automata
url http://hdl.handle.net/1721.1/30486
work_keys_str_mv AT vazirimandana systematicremovalofnondeterminismforcodegenerationinioautomata
AT tauberjoshuaa systematicremovalofnondeterminismforcodegenerationinioautomata
AT tsaimichaelj systematicremovalofnondeterminismforcodegenerationinioautomata
AT lynchnancy systematicremovalofnondeterminismforcodegenerationinioautomata