A conjunctive logical characterization of nondeterministic linear time

DOI10.1007/BFB0028025MaRDI QIDQ4218942zbMATH OpenFDO

Authors Frédéric Olive

Publication date 21 June 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0028025

zbMATH Keywords

descriptive complexity theoryfinite model theoryfunctional equationslogical characterization of complexity classes

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Review text

In this paper formulas of the form \(\exists f_1\cdots f_n \forall x\phi\) are considered where the \(f_i\) are unary function symbols and \(x\) is a first-order variable. It is shown that such formulas can be reduced to the case of formulas written without negation nor disjunction. As a corollary, a new logical characterization of the class of problems recognizable by nondeterministic, linear-time RAMs is obtained. The problem of this class, and notably most of the natural NP-complete problems, can be considered as models of some sequence of the type \(\exists f_1\cdots f_n \forall x\;\Lambda \sigma(x)= \tau(x)\), that is, in some sense, of some system of functional equations. For the entire collection see [Zbl 0891.00021].

Recommendations

• A logical characterisation of linear time on nondeterministic Turing machines
• Linear time and the power of one first-order universal quantifier
• Algebraic and logical characterizations of deterministic linear time classes
• Monadic logical definability of nondeterministic linear time

Cited in

(11)

• Implicit characterizations of FPTIME and NC revisited
• Linear time and the power of one first-order universal quantifier
• The expressive power of bijections over weakly arithmetized structures
• All Linear-Time Congruences for Familiar Operators Part 2: Infinite LTSs
• scientific article; zbMATH DE number 4205978 (Why is no real title available?)
• ON THE NOTION OF LINEAR TIME COMPUTABILITY
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• A logical characterisation of linear time on nondeterministic Turing machines
• A restricted second-order logic for non-deterministic poly-logarithmic time
• The Density of Linear-Time Properties
• Graph properties checkable in linear time in the number of vertices

This page was built for publication: A conjunctive logical characterization of nondeterministic linear time

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