Machine-Independent Characterizations and Complete Problems for Deterministic Linear Time
From MaRDI portal
Publication:4785637
DOI10.1137/S0097539799360240zbMath1029.68058MaRDI QIDQ4785637
Etienne Grandjean, Thomas Schwentick
Publication date: 5 January 2003
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Related Items
A logical approach to locality in pictures languages ⋮ Graph properties checkable in linear time in the number of vertices ⋮ Computing thejth solution of a first-order query ⋮ A NORMAL FORM FOR FIRST-ORDER LOGIC OVER DOUBLY-LINKED DATA STRUCTURES ⋮ On the expressive power of monadic least fixed point logic