Complexity issues for preorders on finite labeled forests

DOI10.1007/978-3-642-21875-0_12MaRDI QIDQ3091446zbMATH OpenOpenAlexFDO

Authors P. H. Hertling, Victor Selivanov

Publication date 9 September 2011

Published in Models of Computation in Context (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-21875-0_12

Mathematics Subject Classification ID

Computation over the reals, computable analysis (03D78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Complexity issues for preorders on finite labeled forests
• Logical Approaches to Computational Barriers
• Some notes on the universality of three-orders on finite labeled posets.
• Undecidability in the Homomorphic Quasiorder of Finite Labelled Forests
• Undecidability in Weihrauch degrees

Cites work

• A Gandy theorem for abstract structures and applications to first-order definability
• Effective Choice and Boundedness Principles in Computable Analysis
• Hierarchies of Δ⁰₂‐measurable k ‐partitions
• scientific article; zbMATH DE number 46423 (Why is no real title available?)
• scientific article; zbMATH DE number 192916 (Why is no real title available?)
• scientific article; zbMATH DE number 503392 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 1500515 (Why is no real title available?)
• scientific article; zbMATH DE number 1748069 (Why is no real title available?)
• scientific article; zbMATH DE number 2154085 (Why is no real title available?)
• Labeled posets are universal
• Logical Approaches to Computational Barriers
• NP-partitions over posets with an application to reducing the set of solutions of NP problems
• On the homomorphism order of labeled posets
• Undecidability in the Homomorphic Quasiorder of Finite Labelled Forests
• Undecidability in Weihrauch degrees
• Weihrauch degrees, omniscience principles and weak computability

Cited in

(4)

• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• Complexity issues for preorders on finite labeled forests
• Some notes on the universality of three-orders on finite labeled posets.
• On the main scientific achievements of Victor Selivanov

This page was built for publication: Complexity issues for preorders on finite labeled forests

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