An introduction to the regular theory of fairness. (English) Zbl 0643.68025

Summary: We present an approach to fairness in the style of the theory of \(\omega\)-regularity. Several concepts of fairness are researched and compared within the classical language theory of words of infinite length.


68N25 Theory of operating systems
68Q45 Formal languages and automata
Full Text: DOI


[1] Apt, K. R.; Olderog, E. R., Proof rules and transformation dealing with fairness, Sci. Comput. Programming, 3, 65-100 (1983) · Zbl 0512.68014
[2] Albert, J.; Ottmann, Th., Automaten, Sprachen und Maschinen für Anwender (1983), Bibliographisches Institut: Bibliographisches Institut Manheim · Zbl 0524.68034
[3] Best, E., Fairness and conspiracies, Inform. Process. Lett., 18, 215-220 (1984) · Zbl 0558.68052
[4] Boasson, L.; Nivat, M., Adherences of languages, J. Comput. System Sci., 20, 285-309 (1980) · Zbl 0471.68052
[5] Büchi, J. R., On a decision method in restricted second-order arithmetic, (Proc. 1960 Internat. Congr. on Logic, Methodology and Philosophy of Science (1960), Stanford University Press), 1-11 · Zbl 0147.25103
[6] Costa, G.; Stirling, C., A fair calculus of communicating systems, Acta Inform., 21, 417-441 (1984) · Zbl 0538.68014
[7] Darondeau, Ph., About fair asynchrony, Theoret. Comput. Sci., 37, 305-336 (1985) · Zbl 0607.68016
[8] Dayan, I.; Harel, D., Fair termination with cruel schedulers, Fund. Inform., IX, 1-12 (1986) · Zbl 0598.68026
[9] Eilenberg, S., Automata, Languages and Machines, Vol. A (1976), Academic Press: Academic Press New York
[10] Francez, N.; Kozen, D., Generalized fair termination, (Proc. ACM Symp. on Programming Languages (1984)), 46-53
[11] Francez, N., Fairness (1986), Springer: Springer Berlin · Zbl 0602.68007
[12] Harel, David, Effective transformations on infinite trees, with application to high undecidability, dominoes and fairness, J. ACM, 33, 224-248 (1986)
[13] Hennessy, M.; de Nicola, R., Testing equivalences for processes, Theoret. Comput. Sci., 34, 83-133 (1984) · Zbl 0985.68518
[14] Hoare, C. A.R., Communicating sequential processes, Comm. ACM, 21, 666-677 (1978) · Zbl 0383.68028
[15] Lehman, D.; Pnueli, A.; Stavi, J., Impartiality, justice and fairness, (Lecture Notes in Computer Science, 115 (1981), Springer: Springer Berlin), 264-277 · Zbl 0468.68026
[16] Milner, R., A Calculus of Communicating Systems, (Lecture Notes in Computer Science, 92 (1980), Springer: Springer Berlin) · Zbl 0452.68027
[17] Muller, D. E., Infinite sequences and finite machines, (Proc. 4th Ann. Symp. on Switching Circuit Theory and Logical Design (1963)), 3-16
[18] Park, D., Concurrency and automata on infinite sequences, (Lecture Notes in Computer Science, 104 (1981), Springer: Springer Berlin), 167-183
[19] Perrin, D., Recent results on automata and infinite words, (Lecture Notes in Computer Science, 176 (1984), Springer: Springer Berlin), 134-148
[20] Pomello, L., Some equivalence notions for concurrent systems, Arbeitspapiere der GMD, 103 (July 1984)
[21] Priese, L.; Rehrmann, R.; Willecke-Klemme, U., Some results on fairness: the regular case, (Lecture Notes in Computer Science, 247 (1987), Springer: Springer Berlin), 383-395 · Zbl 0612.68029
[22] Queille, J. P.; Sifakis, J., Fairness and related properties in transition systems—a temporal logic to deal with fairness, Acta Inform., 19, 195-220 (1983) · Zbl 0489.68024
[23] Rosier, L. E.; Yen, Hsu-Chun, Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines, (Tech. Rept. No. 85-08 (1985), Dept. of Computer Sciences, Univ. of Texas) · Zbl 0615.68041
[24] Tarjan, R., Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 146-160 (1972) · Zbl 0251.05107
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.