Beitrag zur Reduktion des Entscheidungsproblems auf Klassen von Hornformeln mit kurzen Alternationen
From MaRDI portal
Publication:4401927
DOI10.1007/BF02025119zbMath0277.02009MaRDI QIDQ4401927
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
Related Items
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 form1
- On the reduction of the decision problem
- Some theorems on definability and decidability