Tree adjunct grammars

摘要

In this paper, a tree generating system called a tree adjunct grammar is described and its formal properties are studied relating them to the tree generating systems of Brainerd (Information and Control 14 (1969), 217–231) and Rounds (Mathematical Systems Theory 4 (1970), 257–287) and to the recognizable sets and local sets discussed by Thatcher (Journal of Computer and System Sciences 1 (1967), 317–322; 4 (1970), 339–367) and Rounds. Linguistic relevance of these systems has been briefly discussed also.