Linear time computable problems and first-order descriptions
Author:
- 1 December 1996
- journal article
- research article
- Published by Cambridge University Press (CUP) in Mathematical Structures in Computer Science
- Vol. 6 (6) , 505-526
Abstract
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 inL(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 arbitraryFO-problem over relational structures of bounded degree can be solved in linear time.Keywords
This publication has 25 references indexed in Scilit:
- Monadic second-order definable graph transductions: a surveyTheoretical Computer Science, 1994
- An algebraic theory of graph reductionJournal of the ACM, 1993
- Monadic second-order evaluations on tree-decomposable graphsTheoretical Computer Science, 1993
- Introduction to AlgorithmsJournal of the Operational Research Society, 1991
- Easy problems for tree-decomposable graphsJournal of Algorithms, 1991
- Second-order and Inductive Definability on Finite StructuresMathematical Logic Quarterly, 1987
- Relational queries computable in polynomial timeInformation and Control, 1986
- Toward logic tailored for computational complexity1984
- Computable queries for relational data basesJournal of Computer and System Sciences, 1980
- Computation: Finite and Infinite Machines.The American Mathematical Monthly, 1968