Expressive power of digraph solvability

DOI10.1016/J.APAL.2011.08.004zbMATH Open1241.03007OpenAlexW3020929623MaRDI QIDQ409316FDOQ409316

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

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

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)

Cites Work

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

Cited In (9)

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

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)