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

Priese, Lutz; Rehrmann, Ralf; Willecke-Klemme, Uwe

Theor. Comput. Sci. 54, 139-163 (1987).

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.

MSC:

68N25	Theory of operating systems
68Q45	Formal languages and automata

Keywords:

formal language theory; concurrent systems; fairness; \(\omega \)- regularity

References:

[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