The use of temporal context in the generation of strings

[摘要] ENGLISH ABSTRACT:Grammars with regulated rewriting are used to restrict the application of contextfreeproductions in order to avoid certain derivations. This enables these grammarsto generate both context-free and non-context-free languages using only productionrules with a context-free format. These grammars are more powerful than contextfreegrammars, but usually not as powerful as context-sensitive grammars. Variousgrammars with regulated rewriting have been developed and some will be discussed inthis thesis.Propositional linear temporal logic is a formal system used to describe truth valuesof propositions over time. This is done by defining a timeline together with a set ofpropositions. It is then possible to construct temporal logic formulae, consisting of thesepropositions and temporal operators, to specify the truth values of the propositions forevery step in the timeline.In this thesis we define and discuss temporal grammars that combine grammars withpropositionallinear temporal logic. Since a derivation can be associated with a timeline,a regulating device can be constructed from temporal logic formulae, that willcontrol the application of productions within the derivation. The discussion on temporalgrammars includes some of the properties of these grammars, while many ideasare illustrated by examples.

[发布机构] Stellenbosch University