scientific article; zbMATH DE number 1304315

MaRDI QIDQ4251045zbMATH OpenFDO

Authors Clemens Lautemann, Nicole Schweikardt, Thomas Schwentick

Publication date 17 June 1999

zbMATH Keywords

Ehrenfeucht gamelinear timenondeterministic Turing machine

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 1223631
• Linear time and the power of one first-order universal quantifier
• Monadic logical definability of nondeterministic linear time

Cited in

(15)

• The quantifier structure of sentences that characterize nondeterministic time complexity
• Monadic logical definability of nondeterministic linear time
• A descriptive complexity approach to the linear hierarchy.
• Linear time and the power of one first-order universal quantifier
• Determinism versus nondeterminism for linear time RAMs with memory restrictions
• All Linear-Time Congruences for Familiar Operators Part 2: Infinite LTSs
• A logical approach to locality in pictures languages
• scientific article; zbMATH DE number 3872715 (Why is no real title available?)
• scientific article; zbMATH DE number 4160128 (Why is no real title available?)
• scientific article; zbMATH DE number 1223631 (Why is no real title available?)
• scientific article; zbMATH DE number 1543044 (Why is no real title available?)
• Algebraic and logical characterizations of deterministic linear time classes
• A restricted second-order logic for non-deterministic poly-logarithmic time
• The Density of Linear-Time Properties
• Logical Approaches to Computational Barriers

This page was built for publication:

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