An Insertion into the Chomsky Hierarchy? Robert McNaughton This review paper will report on some recent discoveries in the area of Formal Languages, chiefly by F. Otto, G. Buntrock and G. Niemann. These discoveries have pointed out certain break-throughs connected with the concept of growing context sensitive languages, which originated in the 1980's with a paper by E. Dahlhaus and M.K. Warmuth. One important result is that the deterministic growing context-sensitive languages turn out to be identical to an interesting family of formal languages definable in a certain way by confluent reduction systems. Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY cs-99-01
An Insertion into the Chomsky Hierarchy?
Robert McNaughton
This review paper will report on some recent discoveries in the area of Formal Languages, chiefly by F. Otto, G. Buntrock and G. Niemann. These discoveries have pointed out certain break-throughs connected with the concept of growing context sensitive languages, which originated in the 1980's with a paper by E. Dahlhaus and M.K. Warmuth. One important result is that the deterministic growing context-sensitive languages turn out to be identical to an interesting family of formal languages definable in a certain way by confluent reduction systems.
Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY
cs-99-01