Juvenal Murwanashyaka

• Murwanashyaka, Juvenal (2022). Hilbert’s Tenth Problem for Term Algebras with a Substitution Operator. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 13359, p. 196–207. doi: 10.1007/978-3-031-08740-0_17. Full text in Research Archive Show summary

  We introduce a first-order theory of finite full binary trees and show that the analogue of Hilbert’s Tenth Problem is undecidable by constructing a many-to-one reduction of Post’s Correspondence Problem.

• Murwanashyaka, Juvenal (2022). Weak Sequential Theories of Finite Full Binary Trees. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 13359, p. 208–219. doi: 10.1007/978-3-031-08740-0_18. Full text in Research Archive Show summary

  We study a first-order theory of finite full binary trees with an axiom schema of open induction. We show that this theory is sequential by constructing a direct interpretation of Adjunctive Set Theory in a very weak finitely axiomatized subtheory. We show that weakening the latter theory by removal of an axiom which states that the subtree relation is transitive gives a theory that directly interprets Vaught’s weak set theory, a non-finitely axiomatizable fragment of Adjunctive Set Theory.

• Murwanashyaka, Juvenal (2022). Weak Essentially Undecidable Theories of Concatenation. Archive for Mathematical Logic. ISSN 0933-5846. doi: 10.1007/s00153-022-00820-y. Full text in Research Archive
• Kristiansen, Lars & Murwanashyaka, Juvenal (2020). On Interpretability between some weak essentially undecidable theories. Lecture Notes in Computer Science (LNCS). ISSN 0302-9743. 12098, p. 63–74. doi: 10.1007/978-3-030-51466-2_6. Full text in Research Archive
• Kristiansen, Lars & Murwanashyaka, Juvenal (2020). First-Order Concatenation Theory with Bounded Quantifiers (Preprint). arXiv.org. ISSN 2331-8422. doi: 10.1007/s00153-020-00735-6.
• Kristiansen, Lars & Murwanashyaka, Juvenal (2020). First-Order Concatenation Theory with Bounded Quantifiers. Archive for Mathematical Logic. ISSN 0933-5846. 60(1-2), p. 77–104. doi: 10.1007/s00153-020-00735-6. Full text in Research Archive
• Kristiansen, Lars & Murwanashyaka, Juvenal (2018). Decidable and Undecidable Fragments of First-Order Concatenation Theory. In Manea, Florin; Miller, Russel G. & Nowotka, Dirk (Ed.), Sailing Routes in the World of Computation. Springer Nature. ISSN 978-3-319-94417-3. p. 244–253. doi: 10.1007/978-3-319-94418-0_25. Full text in Research Archive

View all works in Cristin

• Murwanashyaka, Juvenal (2019). On First-Order Bit Theory.

View all works in Cristin