Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen

DOI10.1007/BF02025119MaRDI QIDQ4401927zbMATH OpenFDO

Authors Egon Börger

Publication date 1974

Published in Archiv für Mathematische Logik und Grundlagenforschung (Search for Journal in Brave)

Full work available at URL https://eudml.org/doc/137885

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25)

Cites work

• A property of sentences that define quasi-order
• An improved prenex normal form¹
• Certain logical reduction and decision problems
• ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
• scientific article; zbMATH DE number 3271481 (Why is no real title available?)
• scientific article; zbMATH DE number 3366917 (Why is no real title available?)
• On the reduction of the decision problem
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Some theorems on definability and decidability
• Tag systems and lag systems
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• The decision problem for formulas in prenex conjunctive normal form with binary disjunctions
• The Decision Problem for Segregated Formulas in First-Order Logic.
• Turing-machines and the Entscheidungsproblem

Cited in

(5)

• The reachability problem for Petri nets and decision problems for Skolem arithmetic
• The equivalence of Horn and network complexity for Boolean functions
• Prefix classes of krom formulae with identity
• Diem-Grade Logischer Entscheidungsprobleme
• Bemerkung zu Gurevich's Arbeit über das Entscheidungsproblem für Standardklassen

This page was built for publication: Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen

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