Expressive power of digraph solvability

DOI10.1016/J.APAL.2011.08.004MaRDI QIDQ409316zbMATH OpenOpenAlexFDO

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

axiom of choicecompletenessdagdigraphinfinitary propositional logickernelmany-one reductionreverse mathematicsset theory

Mathematics Subject Classification ID

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

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

• Graphes Noyau-Parfaits
• 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?)
• 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

(12)

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

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)