Fair computational tree logic

Fair computational tree logic is conventional computational tree logic studied with explicit fairness constraints.

Uses your system voice; voice and rate in settings.

≈ 2 min read

Cite, export and learn8 citation formats · 8 exports · lesson and quiz

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

Fair computational tree logic is conventional computational tree logic studied with explicit fairness constraints.

Weak fairness / justice

This declares conditions such as all processes execute infinitely often. If you consider the processes to be P i , then the condition becomes: \bigwedge GFP_{i}

Strong fairness / compassion

Here, if a process is requesting a resource infinitely often (R), it should be allowed to get the resource (C) infinitely often: \bigwedge( GFR \longrightarrow GFC)

Model checking for fair CTL

Consider a Kripke model with set of states F. A path \pi = s_o, s_1 \dots is considered a fair path, if and only if the path includes all members of F infinitely often. Fair CTL model checking restricts the checks to only fair paths. There are two kinds of fair quantifiers: 1.

M f , s i |= A \phi if and only if \phi holds in all fair paths. 2. M f , s i |= E \phi if and only if \phi holds in one or more fair paths.

A fair state is one from which at least one fair path originates. This translates to M f , s |= EGtrue.

SCC-based approach

A strongly connected component (SCC) of a directed graph is a maximal strongly connected subgraph—all the nodes are reachable from each other. A fair SCC is one that has an edge into at least one node for each of the fair conditions. To check for fair EG for any formula, Compute what is called the denotation of the formula φ: the set of states such that M, s |= φ.

Restrict the model to the denotation. Find the fair SCC. Obtain the union of all 3 (above).

Compute the states that can reach the union.

Emerson Lei algorithm

The fix point characterization of Exist Globally is given by: [EGφ] = νZ .([φ] ∩ [EXZ ]), which is basically the limit applied according to Kleene's theorem. To fair paths, it becomes [Ef Gφ] = νZ .([φ] ∩ Fi ∈FT [EX[E(Z U(Z ∧ Fi ))]), which means the formula holds in the current state and the next states and the next to next states until it meets all the members of the fair conditions.

This means that, the condition is equivalent to a sort of accepting point where the accepting condition is the entire set of Fair conditions.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1170470136 under CC BY-SA 4.0; modifications have been made.

Words in each sectionEmerson Lei algorithmEmerson Lei algorithmEmerson Lei algorithm: 115 words115Model checking for fair…Model checking for fair CTLModel checking for fair CTL: 109 words109SCC-based approachSCC-based approachSCC-based approach: 93 words93Weak fairness / justiceWeak fairness / justiceWeak fairness / justice: 26 words26Strong fairness / compa…Strong fairness / compassionStrong fairness / compassion: 26 words26
Words in each section. Measured from the stored article body; sections below the minimum are not plotted.

Provenance

snapshot enwiki-001170470136 · captured 2023-08-15 · ledger · version history

Cite this page as: encyclopegia.org, “Fair computational tree logic”, snapshot enwiki-001170470136. https://encyclopegia.org/a/fair-computational-tree-logic

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.