Expressive power of digraph solvability

DOI10.1016/J.APAL.2011.08.004MaRDI QIDQ409316zbMATHOpenAlexFDO

Authors Marc Bezem, Clemens Grabmayer, Michał Walicki

Publication date 13 April 2012

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2011.08.004

zbMATH Keywords

kernelcompletenessdigraphaxiom of choicereverse mathematicsset theorydaginfinitary propositional logicmany-one reduction

Mathematics Subject Classification ID

Classical propositional logic (03B05) Infinite graphs (05C63) Foundations of classical theories (including reverse mathematics) (03B30) Axiom of choice and related propositions (03E25) Second- and higher-order arithmetic and fragments (03F35) Other degrees and reducibilities in computability and recursion theory (03D30)

Recommendations

• Finding kernels or solving SAT
• scientific article; zbMATH DE number 4095497
• Combinatorial game theory foundations applied to digraph kernels
• On the complexity of the 3-kernel problem in some classes of digraphs
• scientific article; zbMATH DE number 1275896

Cites work

• scientific article; zbMATH DE number 1201510 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• Graphes Noyau-Parfaits
• On a Theorem of Richardson
• On directed graphs with an independent covering set
• On kernels and semikernels of digraphs
• On kernels in strongly connected graphs
• Paradox without Self-Reference
• Patterns of paradox
• Perfect graphs, kernels, and cores of cooperative games
• Solutions of irreflexive relations
• Subsystems of second order arithmetic
• The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
• Une généralisation du théorème de Richardson sur l'existence de noyaux dans les graphes orientes

Cited in

(9)

• Resolving infinitary paradoxes
• On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs
• Finding kernels or solving SAT
• On the existence of 3- and 4-kernels in digraphs
• Kernels in digraphs that are not kernel perfect
• Kernels of digraphs with finitely many ends
• The elimination of direct self-reference
• Propositional discourse logic
• Quasi-transitive digraphs and their extensions

This page was built for publication: Expressive power of digraph solvability

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