A double arity hierarchy theorem for transitive closure logic

DOI10.1007/BF01268616zbMath0844.03020OpenAlexW2067838189MaRDI QIDQ1913297

Lauri Hella, Martin Grohe

Publication date: 22 August 1996

Published in: Archive for Mathematical Logic (Search for Journal in Brave)

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

zbMATH Keywords

generalized quantifiersfragment of partial fixed point logicfragment of transitive closure logic

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Model theory of finite structures (03C13)

Related Items

Arity and alternation: a proper hierarchy in higher order logics ⋮ Arity hierarchies

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Logical hierarchies in PTIME
• Stationary logic and its friends. II
• Definability hierarchies of generalized quantifiers
• On the power of deterministic transitive closures
• Languages that Capture Complexity Classes
• Complete problems for fixed-point logics