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

DOI10.1016/0304-3975(80)90042-0zbMATH Open0453.03012OpenAlexW2056477654MaRDI QIDQ1148890FDOQ1148890

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

• Title not available (Why is that?)
• Title not available (Why is that?)
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Decidability and essential undecidability
• Title not available (Why is that?)
• Machine Configuration and Word Problems of Given Degree of Unsolvability
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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

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)