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

DOI10.1007/BF02025119zbMath0277.02009MaRDI QIDQ4401927

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)

Related Items (5)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Certain logical reduction and decision problems
• Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
• Tag systems and lag systems
• A property of sentences that define quasi-order
• Turing-machines and the Entscheidungsproblem
• ENTSCHEIDUNGSPROBLEM REDUCED TO THE AEA CASE
• The Decision Problem for a Class of First‐Order Formulas in Which all Disjunctions are Binary
• The Decision Problem for Segregated Formulas in First-Order Logic.
• The decision problem for formulas in prenex conjunctive normal form with binary disjunctions
• An improved prenex normal form¹
• On the reduction of the decision problem
• Some theorems on definability and decidability

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