scientific article; zbMATH DE number 3582425

MaRDI QIDQ4152749zbMATH OpenFDO

Authors E. Cardoza, Richard J. Lipton, Albert R. Meyer

Publication date 1976

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Free semigroups, generators and relations, word problems (20M05)

Cited in

(35)

• On polynomial ideals, their complexity, and applications
• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• Completeness results for conflict-free vector replacement systems
• On polynomial time isomorphisms of some new complete sets
• Unbounded product-form Petri nets
• A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups
• Complexity of the word problem for commutative semigroups of fixed dimension
• Verification of gap-order constraint abstractions of counter systems
• Forward analysis and model checking for trace bounded WSTS
• Coverability trees for Petri nets with unordered data
• Forward analysis and model checking for trace bounded WSTS
• Verifying Generalised and Structural Soundness of Workflow Nets via Relaxations
• A Framework for Classical Petri Net Problems: Conservative Petri Nets as an Application
• Composable computation in discrete chemical reaction networks
• Ratio and weight quantiles
• Complexity of certain decision problems about congruential languages
• New decision algorithms for finitely presented commutative semigroups
• scientific article; zbMATH DE number 7269252 (Why is no real title available?)
• The covering and boundedness problems for vector addition systems
• Normal and sinkless Petri nets
• Some complexity results for stateful network verification
• Unbounded-thread program verification using thread-state equations
• The complexity of problems involving structurally bounded and conservative Petri nets
• Vector Addition System Reversible Reachability Problem
• The complexity of soundness in workflow nets
• History and basic features of the critical-pair/completion procedure
• On selective unboundedness of VASS
• Reversing Unbounded Petri Nets
• Speed faults in computation by chemical reaction networks
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Properties of congruences on commutative monoids
• Computing with chemical reaction networks: a tutorial
• scientific article; zbMATH DE number 3690734 (Why is no real title available?)
• Structural liveness of Petri nets is \textsc{ExpSpace}-hard and decidable
• Proving nonreachability by modulo-invariants

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 Q4152749)