Presentation | 1997/1/23 A Memory-efficient Contruction of Labeled Transition Models for SCCS Expressions by Unfold Transformation Akira Suzuki, Shoji Yuen, Toshiki Sakabe, Yasuyoshi Inagaki, |
---|---|
PDF Download Page | PDF download Page Link |
Abstract(in Japanese) | (See Japanese page) |
Abstract(in English) | In this paper, we present a memory-efficient construction of LTS models (labeled transition system models) for SCCS expressions. In a construction of an LTS model, the combination of parallel compositions (|) and delay operators ($) will increase the number of states and state transitions. For this reason, a large amount of memory may be required to check if an SCCS specification satisfies some property. However, a typical SCCS specification is in the form of (P_1|…|P_n)\L where \L internalized the communications of L between P_i's. In this type of specification, it is often the case that the specification is deterministic externally although it is very nondeterministic internally because the restriction operation \L eliminates the internal nondeterminism that may cause the memory explosion by intermediate results. Based on this observation, we will give a transformation technique up to the strong equivalence of SCCS so that intermediate results may not be too large in constructing LTS models, where the SCCS expression is syntactically transformed beforehand. The transformation is given as the combination of process definition unfolding, expansion by the expansion theorem, and transformation by the strong equivalence. We show the impact of our transformation technique by presenting an example using Concurrency Workbench. |
Keyword(in Japanese) | (See Japanese page) |
Keyword(in English) | SCCS / LTS model / unfold transformastion / parallel process |
Paper # | COMP96-70,SS96-47 |
Date of Issue |
Conference Information | |
Committee | COMP |
---|---|
Conference Date | 1997/1/23(1days) |
Place (in Japanese) | (See Japanese page) |
Place (in English) | |
Topics (in Japanese) | (See Japanese page) |
Topics (in English) | |
Chair | |
Vice Chair | |
Secretary | |
Assistant |
Paper Information | |
Registration To | Theoretical Foundations of Computing (COMP) |
---|---|
Language | JPN |
Title (in Japanese) | (See Japanese page) |
Sub Title (in Japanese) | (See Japanese page) |
Title (in English) | A Memory-efficient Contruction of Labeled Transition Models for SCCS Expressions by Unfold Transformation |
Sub Title (in English) | |
Keyword(1) | SCCS |
Keyword(2) | LTS model |
Keyword(3) | unfold transformastion |
Keyword(4) | parallel process |
1st Author's Name | Akira Suzuki |
1st Author's Affiliation | Department of Information Engineering, Nagoya University() |
2nd Author's Name | Shoji Yuen |
2nd Author's Affiliation | Department of Information Engineering, Nagoya University |
3rd Author's Name | Toshiki Sakabe |
3rd Author's Affiliation | Department of Information Engineering, Nagoya University |
4th Author's Name | Yasuyoshi Inagaki |
4th Author's Affiliation | Department of Information Engineering, Nagoya University |
Date | 1997/1/23 |
Paper # | COMP96-70,SS96-47 |
Volume (vol) | vol.96 |
Number (no) | 487 |
Page | pp.pp.- |
#Pages | 8 |
Date of Issue |