No label defined (Q3746869)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3982496
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3982496

      Statements

      0 references
      0 references
      1986
      0 references
      concurrency
      0 references
      modelling
      0 references
      fair termination problem
      0 references
      probabilistic concurrent finite-state programs
      0 references
      fairness constraints
      0 references
      complexity bounds
      0 references
      [For the entire collection see Zbl 0587.00019.] The main contribution of the paper is that the authors give a comprehensive analysis of the fair termination problem for probabilistic concurrent finite-state programs under 5 types of fairness constraints. Firstly, it is defined the model of probabilistic concurrent finite-state programs as well as five types of fairness criteria. Based on this model, it is shown that the fair termination problem depends only on the topological structure of the program's termination, and not on the particular values of the nonzero transition probabilities. This constitutes a generalization of a result known up to now. Therefore, the authors are able to use a graph-theoretical approach to determine whether programs will terminate with probability 1 under each of the fairness constraints. Next, there are investigated upper and lower complexity bounds for the problems considered. Lastly, it is considered the case when a more succinct representation of the inputs is allowed (it has been assumed that the inputs are essentially provided in the form of the global state graph).
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references