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

03B25: Decidability of theories and sets of sentences

Related Items

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

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