Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-27T09:24:47.134Z Has data issue: false hasContentIssue false
  • English
  • Français

Muller condition and fairness on multitransition systems

Part of: Theory of computing

Published online by Cambridge University Press:  01 April 2011

Douadi Mihoubi
Douadi Mihoubi*
Affiliation:
Department of Mathematics, LMPA, M’sila University, P.O. Box 166, M’sila 28000, Algeria (email: [email protected])

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

This paper presents an extension of a result by Guessarian and Niar to the framework of multitransition systems. In the case of a single process, Guessarian and Niar had shown that the set of fair computations of regular SCCS processes coincides with the class of ε-free ω-regular languages. Here, in the case of multitransition systems, we show essentially that the sets of fair computations on multitransition systems are strictly included in the class of ε-free ω-regular N-languages. The inclusions of these fair sets into the class of ε-free ω-regular N-languages are obtained by showing that the strict (respectively weak, strong) fair condition can be simulated by the Muller acceptance condition on multitransition systems. The strictness of the inclusions is obtained by exhibiting two counter-examples showing that the reverse is false, that is, not every ω-regular N-language is the set of fair computations of some multitransition system.

MSC classification

Secondary: 68Q10: Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) 68Q85: Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Type
Research Article
Information
LMS Journal of Computation and Mathematics , Volume 14 , 2011 , pp. 99 - 107
Copyright
Copyright © London Mathematical Society 2011

References

[1]Arnold, A. and Nivat, M., ‘Comportements de processus’, Colloque AFCET, les mathématiques de l’informatique, Paris (1982), 35–68.Google Scholar
[2]Eilenberg, S., Automata languages and machines, vol. A (Academic Press, New York, 1974).Google Scholar
[3]Fernandez, M., Models of computations, an introduction to computability theory (Springer, Berlin, 2009).CrossRefGoogle Scholar
[4]Guessarian, I. and Niar, W., ‘Fairness and regularity for SCCS processes’, RAIRO Inform. Theor. 23 (1989) no. 1, 59–86.CrossRefGoogle Scholar