The Bunk Bed Conjecture and the Skolem Problem
- UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
- James Rudzinski (Creator)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
- Advisor
- Clifford Smyth
Abstract: We present our results on two open problems, the Bunk Bed Conjecture and the Skolem Problem. The 35-year-old Bunk Bed Conjecture is a natural conjecture on connection events in a randomly disrupted network. We reduced this problem to a counting problem on graphs. As part of that research, we developed a new algorithm for calculating the inverse images of a monotone Boolean function. This algorithm greatly improves the space complexity of the existing Hansel’s algorithm for this problem. It is also parallelizable whereas Hansel’s algorithm is not. The 85-year-old Skolem Problem is to prove or disprove the existence of a decision procedure to determine whether a rational linear recurrence ever has a zero. We give a partial decision procedure for the more general problem of deciding whether a rational linear recurrence is non-negative. We give wide-ranging conditions under which our procedure is guaranteed to terminate.
The Bunk Bed Conjecture and the Skolem Problem
PDF (Portable Document Format)
681 KB
Created on 12/1/2021
Views: 34
Additional Information
- Publication
- Dissertation
- Language: English
- Date: 2021
- Keywords
- Bunk Bed Conjecture, Positivity Problem, Skolem Problem, Symmetric Chain Decomposition
- Subjects
- Discrete mathematics
- Prediction (Logic)