This paper describes work aimed towards replacing traditional N-gram language models in a recognizer with a more linguistically motivated language model. We report on experiments involving an A* search through a large word graph of candidate hypotheses, within the ARPA ATIS domain. We show that the TINA natural language system, when properly trained, can compete favorably with a traditional word class 4-gram language model, both in terms of raw recognition performance and overall understanding ability.