Send us a comment. We have demonstrated that RTNs have certain clear notational advantages over FSTNs. They allow commonly occurring subpatterns to be expressed as named subnetworks, and large networks to be built up in a modular way. In addition, they allow us to deal naturally with some of the recursive structures in natural languages. The result is a conceptual and notational system that is clean, clear and efficient. As we have seen, however, there is a price to be paid in the complexity of the network traversal algorithms, and we might still prefer FSTNs for a given application for this reason, even though the resulting networks might be larger.
As regards mathematical adequacy, we have illustrated some recursive language structures that can be recognized by RTNs but cannot in principle be captured by FSTNs. The classical example showing the difference in power between the two notations is the language a\un\db\un\d. Whereas it is impossible for a FSTN to recognize precisely the legal strings in a\un\db\un\d, it is rather easy to construct an RTN that does. Here is another simple language for which the same is true. Assume that we have just two symbols, '(' and ')', and we want to recognize whether a string of such symbols has correctly matching brackets. Thus, the following strings will be legal:
( ) ( ( ) ) ( ( ( ) ) ) ( ( ) ( ) ) ( ( ) ) ( ( ( ) ) ( ) )
but the following will not:
) ( ( ) ( ) ( ( ( ) ) ( ( ) ) )
Although it is possible to construct an RTN to recognize the set of legal strings in this language (it needs to use recursion in a non-trivial way), it is not possible to do the same with an FSTN. Syntactic constructions with this formal character are rather common in natural languages, although English fails to provide a really clearcut example. However, if you imagine a language just like English except that (i) the 'then' in the 'if .. then ..' construction is obligatory, and (ii) this is the only usage of the word 'then', then you can get a sense of the phenomenon as it might occur naturally.
Are there sets of inputs that even RTNs cannot recognize? The answer is yes: whilst it is possible to write an RTN which will recognize precisely the strings of a\un\db\un\d, it is not possible to write one for the language a\un\db\un\dc\un\d - that is, the language of strings consisting of n number of as, followed by n number of bs, followed by n number of cs, for any n. Similarly, the language a\um\db\un\dc\um\dd\un\d is not amenable to recognition by an RTN.
Send us a comment.