Exponential space complete problems for Petri nets and commutative semigroups: Preliminary report. (English) Zbl 0374.20067

Proc. 8th ann. ACM Symp. Theor. Comput., Hershey 1976, 50-54 (1976).


20M05 Free semigroups, generators and relations, word problems
03D60 Computability and recursion theory on ordinals, admissible sets, etc.
68Q25 Analysis of algorithms and problem complexity
68Q45 Formal languages and automata
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)