Impossibility of an algorithm for the decision problem in finite classes

DOI10.1090/TRANS2/023/01MaRDI QIDQ5731786zbMATH OpenOpenAlexFDO

Authors B. A. Trakhtenbrot

Publication date 1963

Published in Nine Papers on Logic and Quantum Electrodynamics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1090/trans2/023/01

zbMATH Keywords

mathematical logic

Cited in

(13)

• Nonconvergence, undecidability, and intractability in asymptotic problems
• The decision problem for database dependencies
• Succinct definitions in the first order theory of graphs
• LTL over integer periodicity constraints
• Computational complexity of theories of a binary predicate with a small number of variables
• On the almighty wand
• Separation logics and modalities: a survey
• Expressive completeness of separation logic with two variables and no separating conjunction
• LOGICAL ASPECTS OF CAYLEY-GRAPHS: THE MONOID CASE
• A Short Note on the Early History of the Spectrum Problem and Finite Model Theory
• The umbilical cord of finite model theory
• Variations on the Kripke trick
• Trakhtenbrot theorem and first-order axiomatic extensions of MTL

This page was built for publication: Impossibility of an algorithm for the decision problem in finite classes

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