Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time

DOI10.1137/S0097539799360240MaRDI QIDQ4785637zbMATH OpenFDO

Authors Etienne Grandjean, Thomas Schwentick

Publication date 5 January 2003

Published in SIAM Journal on Computing (Search for Journal in Brave)

zbMATH Keywords

completenesslinear timemodel of computationrecursion schemesRandom Access Machineaffine reductions

Mathematics Subject Classification ID

Computability and recursion theory (03D99)

Recommendations

• Algebraic and logical characterizations of deterministic linear time classes
• scientific article; zbMATH DE number 515738
• scientific article; zbMATH DE number 4101157
• Linear Time Algorithms and NP-Complete Problems
• Neat function algebraic characterizations of LOGSPACE and LINSPACE

Cited in

(7)

• A NORMAL FORM FOR FIRST-ORDER LOGIC OVER DOUBLY-LINKED DATA STRUCTURES
• Graph properties checkable in linear time in the number of vertices
• All Linear-Time Congruences for Familiar Operators Part 2: Infinite LTSs
• A logical approach to locality in pictures languages
• Computing thejth solution of a first-order query
• On the expressive power of monadic least fixed point logic
• scientific article; zbMATH DE number 4101157 (Why is no real title available?)

This page was built for publication: Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time

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