Expressive power of digraph solvability

DOI10.1016/j.apal.2011.08.004zbMath1241.03007OpenAlexW3020929623MaRDI QIDQ409316

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

zbMATH Keywords

digraphcompletenesskernelset theoryreverse mathematicsaxiom of choicedaginfinitary propositional logicmany-one reduction

Mathematics Subject Classification ID

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

Related Items (8)

Kernels of digraphs with finitely many ends ⋮ The elimination of direct self-reference ⋮ On the existence of 3- and 4-kernels in digraphs ⋮ Kernels in digraphs that are not kernel perfect ⋮ Propositional discourse logic ⋮ RESOLVING INFINITARY PARADOXES ⋮ On the complexity of the \(k\)-kernel problem on cyclically \(k\)-partite digraphs ⋮ Quasi-Transitive Digraphs and Their Extensions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness
• On kernels and semikernels of digraphs
• 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
• Perfect graphs, kernels, and cores of cooperative games
• Solutions of irreflexive relations
• On a Theorem of Richardson
• Graphes Noyau-Parfaits
• On kernels in strongly connected graphs
• Paradox without Self-Reference
• Patterns of paradox

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