On the minimal number of \(\times\) operators to model regularity in fair SCCS. (English) Zbl 0676.68036

Any \(\omega\)-regular language is a weakly, strongly or strictly fair language of some strict SCCS [R. Milner, Calculi for synchrony and asynchrony, Theor. Comput. Sci. 25, 267-310 (1983; Zbl 0512.68026)] process that consists of a parallel product of exactly two inherently sequential SCCS processes.
Reviewer: R.Janicki


68Q45 Formal languages and automata
68Q70 Algebraic theory of languages and automata


Zbl 0512.68026
Full Text: DOI


[1] Darondeau, P., About fair asynchrony, Theoret. Comput. Sci., 37, 305-336 (1985) · Zbl 0607.68016
[2] Guessarian, I.; Niar-Dinedane, W., An automaton characterization of fairness in SCCS, (Proc. STACS 88, Lecture Notes in Computer Science, Vol. 294 (1988), Springer: Springer Berlin), 356-372 · Zbl 0644.68036
[3] Hennessy, M., Modelling Finite Delay Operators, Tech. Rept. CSR-153-83 (1983), Edinburgh
[4] Milner, R., A Finite Delay Operator in Synchronous CCS, (Rept. CSR-116-82 (1982), Edinburgh Univ)
[5] Milner, R., Calculi for synchrony and asynchrony, Theoret. Comput. Sci., 25, 267-310 (1983) · Zbl 0512.68026
[6] Muller, D. E., The general synthesis problem for asynchronous digital networks, Proc. SWAT Conf., 71-82 (1967)
[7] Priese, L.; Rehrmann, R.; Willecke-Klemme, U., An introduction to the regular theory of fairness, Theoret. Comput. Sci., 54, 139-163 (1987) · Zbl 0643.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.