The unsolvability of some Petri net language problems

DOI10.1016/0020-0190(79)90128-5zbMath0414.68032OpenAlexW2074997215MaRDI QIDQ599503

Jan Grabowski

Publication date: 1979

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(79)90128-5

zbMATH Keywords

decision problemPetri net languagesequality problemcoemptiness problemnondeterministic sequential machine

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Decidability of theories and sets of sentences (03B25)

Cites Work

• Computation sequence sets
• Termination Properties of Generalized Petri Nets
• The Unsolvability of the Equivalence Problem for $\varepsilon $-Free NGSM’s with Unary Input (Output) Alphabet and Applications
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Unnamed Item