The reachability problem for Petri nets and decision problems for Skolem arithmetic

DOI10.1016/0304-3975(80)90042-0MaRDI QIDQ1148890zbMATH OpenOpenAlexFDO

Authors Egon Börger, Hans Kleine Büning

Publication date 1980

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(80)90042-0

zbMATH Keywords

extended Skolem arithmeticPost canonical formreducibility of problems

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Thue and Post systems, etc. (03D03) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Undecidability and degrees of sets of sentences (03D35)

Cites work

• scientific article; zbMATH DE number 3001281 (Why is no real title available?)
• scientific article; zbMATH DE number 3248792 (Why is no real title available?)
• scientific article; zbMATH DE number 3266625 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3366917 (Why is no real title available?)
• scientific article; zbMATH DE number 3375482 (Why is no real title available?)
• A New General Approach to the Theory of the Many‐One Equivalence of Decision Problems for Algorithmic Systems
• Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen
• Decidability and essential undecidability
• Diem-Grade Logischer Entscheidungsprobleme
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Single premise Post canonical forms defined over one-letter alphabets
• Some post canonical systems in one letter

Cited in

(1)

• Some undecidable theories with monadic predicates and without equality

This page was built for publication: The reachability problem for Petri nets and decision problems for Skolem arithmetic

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