Expressive power of digraph solvability
Publication:409316
DOI10.1016/J.APAL.2011.08.004zbMATH Open1241.03007OpenAlexW3020929623MaRDI QIDQ409316FDOQ409316
Michał Walicki, Marc Bezem, Clemens Grabmayer
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
kernelcompletenessdigraphaxiom of choicereverse mathematicsset theorydaginfinitary propositional logicmany-one reduction
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?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Perfect graphs, kernels, and cores of cooperative games
- Solutions of irreflexive relations
- Graphes Noyau-Parfaits
- 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 (8)
- On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs
- Kernels in digraphs that are not kernel perfect
- The elimination of direct self-reference
- Quasi-Transitive Digraphs and Their Extensions
- Propositional discourse logic
- On the existence of 3- and 4-kernels in digraphs
- Kernels of digraphs with finitely many ends
- RESOLVING INFINITARY PARADOXES
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)
