scientific article; zbMATH DE number 3582425

zbMath0374.20067MaRDI QIDQ4152749

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

Publication date: 1976

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Mathematics Subject Classification ID

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

Related Items

Complexity of certain decision problems about congruential languages ⋮ Forward analysis and model checking for trace bounded WSTS ⋮ On polynomial ideals, their complexity, and applications ⋮ Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states ⋮ History and basic features of the critical-pair/completion procedure ⋮ Completeness results for conflict-free vector replacement systems ⋮ On selective unboundedness of VASS ⋮ Ratio and Weight Quantiles ⋮ Unnamed Item ⋮ Speed faults in computation by chemical reaction networks ⋮ Reversing Unbounded Petri Nets ⋮ New decision algorithms for finitely presented commutative semigroups ⋮ Computing with chemical reaction networks: a tutorial ⋮ Verification of gap-order constraint abstractions of counter systems ⋮ A logspace solution to the word and conjugacy problem of generalized Baumslag-Solitar groups ⋮ The complexity of problems involving structurally bounded and conservative Petri nets ⋮ Proving nonreachability by modulo-invariants ⋮ Forward Analysis and Model Checking for Trace Bounded WSTS ⋮ A Framework for Classical Petri Net Problems: Conservative Petri Nets as an Application ⋮ Normal and sinkless Petri nets ⋮ The covering and boundedness problems for vector addition systems ⋮ On polynomial time isomorphisms of some new complete sets ⋮ Unnamed Item ⋮ Coverability Trees for Petri Nets with Unordered Data ⋮ Unbounded-Thread Program Verification using Thread-State Equations ⋮ Vector Addition System Reversible Reachability Problem ⋮ Unnamed Item ⋮ Composable computation in discrete chemical reaction networks ⋮ Structural liveness of Petri nets is \textsc{ExpSpace}-hard and decidable ⋮ The complexity of the word problems for commutative semigroups and polynomial ideals ⋮ Some complexity results for stateful network verification ⋮ Properties of congruences on commutative monoids ⋮ Complexity of the word problem for commutative semigroups of fixed dimension