Language models for automatic speech recognition are used for computing probabilities of theories corresponding to partial interpretations of sentences. Algorithms have been developed for computing these probabilities when theories grow in a strictly left-to-right fashion. This paper introduces a new framework for the computation of probabilities of theories that contain a gap corresponding to an uninterpreted signal segment. Algorithms have been developed and their complexity is here derived. The use of these algorithms in an island-driven parser is also discussed.