Hardness of monadic second-order formulae over succinct graphs

DOI10.46298/LMCS-22(1:3)2026MaRDI QIDQ6858374zbMATH OpenFDO

Authors Guilhem Gamard, Aliénor Goubault-Larrecq, Pierre Guillon, Pierre Ohlmann, Kévin Perrot, Guillaume Theyssier

Publication date 13 February 2026

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/LMCS-22(1:3)2026

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites work

• A note on succinct representations of graphs
• A spectrum hierarchy
• About block-parallel Boolean networks: a position paper
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Clique-width is NP-complete
• CNF and DNF succinct graph encodings
• Elements of finite model theory.
• Fifty years of the spectrum problem: survey and new results
• Fundamentals of parameterized complexity
• Graph structure and monadic second-order logic. A language-theoretic approach
• scientific article; zbMATH DE number 1696534 (Why is no real title available?)
• scientific article; zbMATH DE number 4042465 (Why is no real title available?)
• scientific article; zbMATH DE number 45557 (Why is no real title available?)
• scientific article; zbMATH DE number 3057871 (Why is no real title available?)
• Linear analysis of switching nets
• Linear time solvable optimization problems on graphs of bounded clique-width
• Maximum number of fixed points in regulatory Boolean networks
• Robust simulations and significant separations
• Succinct representations of graphs
• Turing machines and the spectra of first-order formulas
• Upper bounds to the clique width of graphs

This page was built for publication: Hardness of monadic second-order formulae over succinct graphs

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