A restricted second-order logic for non-deterministic poly-logarithmic time

DOI10.1093/JIGPAL/JZZ078zbMath1494.03027arXiv1912.00010OpenAlexW3000564918WikidataQ126806867 ScholiaQ126806867MaRDI QIDQ5082331

Klaus-Dieter Schewe, Flavio Ferrarotti, Jose Maria Turull Torres, Senén Gonzáles

Publication date: 16 June 2022

Published in: Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1912.00010

zbMATH Keywords

finite modelssecond-order logicdescriptive complexitypoly-logarithmic time

Mathematics Subject Classification ID

Database theory (68P15) Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19) Higher-order logic (03B16)

This page was built for publication: A restricted second-order logic for non-deterministic poly-logarithmic time