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

DOI10.1016/0304-3975(80)90042-0zbMath0453.03012OpenAlexW2056477654MaRDI QIDQ1148890

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

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

Related Items (1)

Some undecidable theories with monadic predicates and without equality

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Decidability and essential undecidability
• A New General Approach to the Theory of the Many‐One Equivalence of Decision Problems for Algorithmic Systems
• Single premise Post canonical forms defined over one-letter alphabets
• Some post canonical systems in one letter
• Diem-Grade Logischer Entscheidungsprobleme
• Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen
• Machine Configuration and Word Problems of Given Degree of Unsolvability

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