Linear Time Computable Problems and Logical Descriptions
Detlef G. Seese · Electronic Notes in Theoretical Computer Science · 1995
It is a general problem to investigate the trade off between the complexity of algorithmic problems, the structure of the input objects and the expressive power of problem description languages. The article concentrates on linear time algorithms and on first order logic (FO) as problem description language. One of the main results is a proof that each FO-problem can be solved in linear time for arbitrary relational structures of universally bounded degree.