A toolkit for first order extensions of monadic games

DOI10.1007/3-540-44693-1_31MaRDI QIDQ2762516zbMATH OpenFDO

Authors David Janin, Jerzy Marcinkowski

Publication date 9 January 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2010/20100353

zbMATH Keywords

monadic NPmonadic second-order logicnon-expressibilitysecond-order quantifiers

Mathematics Subject Classification ID

Second- and higher-order model theory (03C85) 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

• Game semantics for first-order logic
• Games and bisimulations for intuitionistic first-order Kripke models
• About effective versions of game theoretical semantics for first-order logic
• Game semantics for non-monotonic intensional logic programming
• Game semantics for non-monotonic intensional logic programming
• Axiomatizing core extensions on NTU games
• Model-Checking Games for Fixpoint Logics with Partial Order Models
• Model-checking games for fixpoint logics with partial order models
• scientific article; zbMATH DE number 1231521
• Games on Higher Order Multi-stack Pushdown Systems

Cited in

(5)

• The closure of monadic NP
• Expressibility in _1¹
• scientific article; zbMATH DE number 1775416 (Why is no real title available?)
• Directed reachability: From Ajtai-Fagin to Ehrenfeucht-Fraïssé games
• First order quantifiers in monadic second order logic

This page was built for publication: A toolkit for first order extensions of monadic games

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