Expressivity within second-order transitive-closure logic

DOI10.4230/LIPICS.CSL.2018.22MaRDI QIDQ5079746zbMATH OpenFDO

Authors Flavio Ferrarotti, Jan Van den Bussche, Jonni Virtema

Publication date 28 May 2022

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

zbMATH Keywords

descriptive complexityexpressive powerhigher-order logics

Mathematics Subject Classification ID

Logic in computer science (03B70)

Recommendations

• scientific article; zbMATH DE number 408795
• On the power of deterministic transitive closures
• Monadic Second-Order Logic and Transitive Closure Logics over Trees
• scientific article; zbMATH DE number 1136077
• A restricted second order logic for finite structures

Cites work

• scientific article; zbMATH DE number 4180775 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• Abstract State Machines
• Abstract state machines and computationally complete query languages
• An existential fragment of second order logic
• Choiceless polynomial time
• Computer Science Logic
• Computer science logic. 18th international workshop, CSL 2004, 13th annual conference of the EACSL, Karpacz, Poland, September 20--24, 2004. Proceedings.
• Dependency learning for QBF
• Domino-tiling games
• Expressing properties in second- and third-order logic: hypercube graphs and SATQBF
• Finding topological subgraphs is fixed-parameter tractable
• Graph coloring and the immersion order
• Languages that Capture Complexity Classes
• Modeling in Event B. System and software engineering.
• Nondeterministic Space is Closed under Complementation
• On Context-Free Languages
• On fragments of higher order logics that on finite structures collapse to second order
• On static logics, dynamic logics, and complexity classes
• Regular queries on graph databases
• Shortening QBF proofs with dependency schemes
• Solution validation and extraction for QBF preprocessing
• The Computational Complexity of Provability in Systems of Modal Propositional Logic
• The monadic second-order logic of graphs. VIII: Orientations

Cited in

(1)

• scientific article; zbMATH DE number 176527 (Why is no real title available?)

Describes a project that uses

Uses Software

• Rodin

This page was built for publication: Expressivity within second-order transitive-closure logic

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