The rapid growth of wireless communication systems makes the coexistence of heterogeneous technologies more and more important. This dissertation studies how cognitive radio concepts may provide an efficient framework for accessing and sharing spectrum by sensing and predicting temporal activity patterns. In this way, the spectrum access of interfering devices can be coordinated implicitly and coexistence be improved. The efficacy of this approach is studied for two common coexistence scenarios. First, we address the coexistence of a frequency hopping cognitive radio with a set of parallel ad-hoc bands, a setup that has conceptual similarities with interfering local and personal area networks. Temporal idle periods that remain between adhoc transmissions are reused efficiently by the cognitive radio through predicting ad-hoc radio activity and dynamically adapting the hopping pattern. Second, we address the coexistence of infrastructure and ad-hoc networks. Motivated by the superior resources of the infrastructure system, we study how its centralized resource allocation may accommodate the ad-hoc links based on adjusting the power and transmission time allocation. Despite adapting its behavior to coexist with the ad-hoc links, the infrastructure system maintains a specified quality of service level for its users by imposing rate constraints. Both of the above formulations are based on a two-state continuous-time Markov chain model for the ad-hoc system's temporal behavior which approxi- mates the carrier-sense multiple access typically employed in such systems. The model is discussed in detail and corroborated through empirical analysis of a practical system. Our analyses are based on the mathematical tools of constrained Markov decision processes and convex optimization and are validated by systemlevel simulations. Further, a real-time test bed has been developed for the cognitive frequency hopping protocol which enables us to corroborate model assumptions experimentally and gain further insight into fundamental tradeoffs. The results presented in this dissertation demonstrate a significant performance gain compared to reference schemes without sensing capabilities. While various implementation details remain to be addressed in future work, our study clearly shows the conceptual merits of this framework and the importance it might play in future wireless systems.