Problems concerning fairness and temporal logic for conflict-free Petri nets (Q1121023): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
Set profile property.
ReferenceBot (talk | contribs)
Changed an Item
 
(One intermediate revision by one other user not shown)
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1016/0304-3975(89)90053-4 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1999917306 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3967058 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Bounds on Positive Integral Solutions of Linear Diophantine Equations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3766865 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3687727 / rank
 
Normal rank
Property / cites work
 
Property / cites work: A decidability theorem for a class of vector-addition systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Modalities for model checking: Branching time logic strikes back / rank
 
Normal rank
Property / cites work
 
Property / cites work: Vector addition systems and regular languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: The decidability of persistence for vector addition systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Termination of Probabilistic Concurrent Program / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the reachability problem for 5-dimensional vector addition systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states / rank
 
Normal rank
Property / cites work
 
Property / cites work: Completeness results for conflict-free vector replacement systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: An \(O(n^{1.5})\) algorithm to decide boundedness for conflict-free vector replacement systems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3802633 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Space-bounded reducibility among combinatorial problems / rank
 
Normal rank
Property / cites work
 
Property / cites work: Complexity of some problems in Petri nets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Parallel program schemata / rank
 
Normal rank
Property / cites work
 
Property / cites work: Decision problems forω-automata / rank
 
Normal rank
Property / cites work
 
Property / cites work: Properties of Conflict-Free and Persistent Petri Nets / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3922147 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3711745 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4190096 / rank
 
Normal rank
Property / cites work
 
Property / cites work: An Algorithm for the General Petri Net Reachability Problem / rank
 
Normal rank
Property / cites work
 
Property / cites work: Persistence of vector replacement systems is decidable / rank
 
Normal rank
Property / cites work
 
Property / cites work: Recursive unsolvability of Post's problem of ''Tag'' und other topics in theory of Turing machines / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3939247 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Proving Liveness Properties of Concurrent Programs / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3911403 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3330494 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Fairness and related properties in transition systems - a temporal logic to deal with fairness / rank
 
Normal rank
Property / cites work
 
Property / cites work: Logspace Hierarchies, Polynomial Time and the Complexity of Fairness Problems Concerning $\omega $-Machines / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the complexity of deciding fair termination of probabilistic concurrent finite-state programs / rank
 
Normal rank
Property / cites work
 
Property / cites work: The complexity of propositional linear temporal logics / rank
 
Normal rank
Property / cites work
 
Property / cites work: Petri nets and regular languages / rank
 
Normal rank
Property / cites work
 
Property / cites work: The residue of vector sets with applications to decidability problems in Petri nets / rank
 
Normal rank
Property / cites work
 
Property / cites work: On weak persistency of Petri nets / rank
 
Normal rank

Latest revision as of 14:29, 19 June 2024

scientific article
Language Label Description Also known as
English
Problems concerning fairness and temporal logic for conflict-free Petri nets
scientific article

    Statements

    Problems concerning fairness and temporal logic for conflict-free Petri nets (English)
    0 references
    0 references
    0 references
    1989
    0 references
    This paper is identical to the author's work [Advances in Petri Nets, Lect. Notes Comput. Sci. 340, 200-226 (1988)] except for the improvement of Section 4 about model checking. The complexity of the fair nontermination problem is studied for conflict-free Petri nets under several definitions of fairness. The question of determining whether a given structure defines a model of a specification expressed in temporal logic is proved to be undecidable for conflict-free Petri nets. Even if the logic is severely restricted, it is still not feasible: although it becomes decidable, it is then NP-complete.
    0 references
    conflict-free Petri nets
    0 references
    fairness property
    0 references
    model checking
    0 references
    complexity
    0 references
    temporal logic
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references

    Identifiers