×

zbMATH — the first resource for mathematics

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.

MSC:
68N25 Theory of operating systems
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
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 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, (), 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 New York
[10] Francez, N.; Kozen, D., Generalized fair termination, (), 46-53
[11] Francez, N., Fairness, (1986), 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, (), 264-277 · Zbl 0468.68026
[16] Milner, R., A calculus of communicating systems, () · Zbl 0452.68027
[17] Muller, D.E., Infinite sequences and finite machines, (), 3-16
[18] Park, D., Concurrency and automata on infinite sequences, (), 167-183
[19] Perrin, D., Recent results on automata and infinite words, (), 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, (), 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, () · 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.