scientific article; zbMATH DE number 1560298

MaRDI QIDQ4527145zbMATH OpenFDO

Authors Zakaria Bouziane, Alain Finkel

Publication date 16 July 2001

zbMATH Keywords

commutative semigroups and reversible Petri nets equivalence problemEXPSPACE-completelower boundsemigroup presentationThue systemword problem

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Complexity of computation (including implicit computational complexity) (03D15) Word problems, etc. in computability and recursion theory (03D40) Free semigroups, generators and relations, word problems (20M05) Commutative semigroups (20M14) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Recommendations

• Completeness results for linear logic on Petri nets
• On the reachability and reversibility problems in a class of Petri nets
• scientific article; zbMATH DE number 4213467
• Nonprimitive recursive complexity and undecidability for Petri net equivalences
• Semi-commutations and Petri nets
• Petri nets and semilinear sets (extended abstract)
• scientific article; zbMATH DE number 1555184
• The completeness of linear logic for Petri net models
• scientific article; zbMATH DE number 1899812
• Complexity results for problems of communication-free Petri nets and related formalisms

Cited in

(2)

• Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups.
• The complexity of the coverability, the containment, and the equivalence problems for commutative semigroups

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4527145)