Mathematical Structures in Computer Science · 1996 · 153 citations · 23 references
ComputingComputer ScienceMathematicsAlgorithmsLogicTheory Of ComputationComputational ComplexityFirst-order LogicPredicate LogicRelational AlgebraPolynomial Time ComplexityPolynomial-time Algorithms
It is well known that every algorithmic problem definable by a formula of first-order logic can be solved in polynomial time, since all these problems are in L (see Aho and Ullman (1979) and Immerman (1987)). Using an old technique of Hanf (Hanf 1965) and other techniques developed to prove the decidability of formal theories in mathematical logic, it is shown that an arbitrary FO -problem over relational structures of bounded degree can be solved in linear time.
23
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Computation: Finite and Infinite Machines.
D. A. Clarke, Marvin Minsky · American Mathematical Monthly · 1968 · 2.6K citations
Logic, Methodology and Philosophy of Science.
Max Black, Ernest Nagel, Patrick Suppes et al. · The Philosophical Review · 1963 · 2K citations
Easy problems for tree-decomposable graphs
Stefan Arnborg, Jens Lagergren, Detlef Seese · Journal of Algorithms · 1991 · 874 citations