Undecidability in the Homomorphic Quasiorder of Finite Labelled Forests

DOI10.1093/LOGCOM/EXM038MaRDI QIDQ5441125zbMATH OpenOpenAlexWikidataFDO

Authors Oleg Kudinov, Victor Selivanov

Publication date 7 February 2008

Published in Journal Of Logic And Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1093/logcom/exm038

zbMATH Keywords

first-order theoryforesthomomorphic quasiorderlabelled treeundecidability

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• Logical Approaches to Computational Barriers
• Undecidability in Weihrauch degrees
• Definability in the Homomorphic Quasiorder of Finite Labeled Forests
• Definability in the \(h\)-quasiorder of labeled forests
• Theories of orders on the set of words

Cited in

(17)

• Definability in the \(h\)-quasiorder of labeled forests
• On the Wadge reducibility of \(k\)-partitions
• Alternating complexity of counting first-order logic for the subword order
• Complexity issues for preorders on finite labeled forests
• Well-Quasi Orders and Hierarchy Theory
• A Gandy theorem for abstract structures and applications to first-order definability
• Undecidability in Weihrauch degrees
• Definability in the Infix Order on Words
• Fine hierarchies via Priestley duality
• Complexity issues for preorders on finite labeled forests
• Complexity of counting first-order logic for the subword order
• Definability in the Homomorphic Quasiorder of Finite Labeled Forests
• Logical Approaches to Computational Barriers
• scientific article; zbMATH DE number 7770056 (Why is no real title available?)
• On the main scientific achievements of Victor Selivanov
• Definability of closure operations in the \(h\)-quasiorder of labeled forests
• Fine hierarchies and m-reducibilities in theoretical computer science

This page was built for publication: Undecidability in the Homomorphic Quasiorder of Finite Labelled Forests

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