D.Phil. (Computer Science) / Please refer to full text to view abstract

Ph.D. (Computer Science) / Traditionally a formal language can be characterized in two ways: by a generative device (a grammar) and an acceptive device (an automaton). The characterization of two- and three-dimensional Random Context Grammars by two- and three-dimensional Random Context Automata are investigated. This thesis is an attempt to progressively extend a certain class of grammars to higher dimensions where the class of languages generated in each dimension is contained in the class of languages generated in the next higher dimension. Random Context Array Automata which characterizes Random Context Array Grammars (Von Solms [4,5]) are defined. The power of both Random Context Array Grammars and Random Context Array Automata is inherent in the fact that the replacement of symbols in figures is subject to horizontal, vertical and global context. A proof is given for the equivalence of the class of languages generated by Random Context Array Grammars and the class of languages accepted by Random Context Array Automata. The two-dimensional Random Context Array Grammars are extended to three dimensions. Random Context Structure Grammars generate three-dimensional structures. A characteristic of Random Context Structure Grammars is that the replacement of symbols in a structure is subject to seven relevant contexts. Random Context Structure Automata which characterize Random Context Structure Grammars are defined. It is shown that the class of languages generated by Random Context Structure Grammars are equivalent to the class of languages accepted by Random Context Array Automata...

No description available.

No description available.

This thesis investigates permutation pattern classes in a language theoretic context. Specifically we explored the regularity of sets of permutations under the rank encoding. We found that the subsets of plus- and minus-(in)decomposable permutations of a regular pattern class under the rank encoding are also regular languages under that encoding. Further we investigated the sets of permutations, which in their block-decomposition have the same simple permutation, and again we found that these sets of permutations are regular languages under the rank encoding. This natural progression from plus- and minus-decomposable to simple decomposable permutations led us further to the set of simple permutations under the rank encoding, which we have also shown to be regular under the rank encoding. This regular language enables us to find the set of simple permutations of any class, independent of whether the class is regular under the rank encoding. Furthermore the regularity of the languages of some types of classes is discussed. Under the rank encoding we show that in general the skew-sum of classes, separable classes and wreath classes are not regular languages; but that the direct-sum of classes, and with some restrictions on the cardinality of the input classes the skew-sum and wreath sum of classes in fact are regular under this encoding. Other encodings such as the insertion encoding and the geometric grid encoding are discussed and in the case of the geometric grid encoding alternative and constructive ways of retrieving the basis of a geometric grid class are suggested. The aforementioned results of the rank encoding have been implemented, amongst other previously shown results, and tested. The program is available and accessible to everyone. We show that the implementation for finding the block-decomposition of a permutation has cubic time complexity with respect to the length of the permutation. The code for constructing the automaton that accepts the language of all plus-indecomposable permutations of a regular class under the rank encoding has quadratic time complexity with respect to the alphabet of the language. The procedure to find the automaton that accepts the language of minus-decomposable permutations has complexity O(k⁵) and we show that the implementation of the automaton to find the language of simple permutations under the rank encoding has time complexity O(k⁵ 2ᵏ), where k is the size of the alphabet. Further we show benchmark testing on previous important results involving the rank encoding on classes and their bases.

Thesis (M.A (African Languages)) --University of Limpopo, 2010 / This study focuses on the morpheme le in Northern Sotho. It is sometimes confusing to establish the correct semantic function which the morpheme le expresses; and also to classify it into a certain word category. This study suggests the morphological features which the morpheme le bears in terms of its word categorization. The morpheme le in Northern Sotho can be used as a conjunction, a demonstrative pronoun, an agreement, a preposition, a copulative, an adverb and a complement as well. It is suggested in this study, ways of identifying the semantic function of the morpheme le in various contexts. This study reflects that the morpheme le in Northern Sotho can be used to denote: possession, accompaniment, location, additive focus, existentialism and honorifics.

According to the classical consistency presupposition, contradictions have an explosive character: Whenever they are present in a theory, anything goes, and no sensible reasoning can thus take place. A logic is paraconsistent if it disallows such presupposition, and allows instead for some inconsistent yet non-trivial theories to make perfect sense. The Logics of Formal Inconsistency, LFIs, form a particularly expressive class of paraconsistent logics in which the metatheoretical notion of consistency can be internalized at the object-language level. As a consequence, the LFIs are able to recapture consistent reasoning by the addition of appropriate consistency assumptions. The present monograph introduces the LFIs and provides several illustrations of them and of their properties, showing that such logics constitute in fact the majority of interesting paraconsistent systems in the literature. Several ways of performing the recapture of consistent reasoning inside such inconsistent systems are also illustrated. In each case, interpretations in terms of many-valued, possible-translations, or modal semantics are provided, and the problems related to providing algebraic counterparts to such logics are surveyed. A formal abstract approach is proposed to all related definitions and an extended investigation is made into the logical principles and the positive and negative properties of negation.

In this thesis, we cover the general topic of state complexity. In particular, we examine the bounds on the state complexity of some different representations of regular languages. As well, we consider the state complexity of the operation root(<i>L</i>). We give quick treatment of the deterministic state complexity bounds for nondeterministic finite automata and regular expressions. This includes an improvement on the worst-case lower bound for a regular expression, relative to its alphabetic length. The focus of this thesis is the study of the increase in state complexity of a regular language <i>L</i> under the operation root(<i>L</i>). This operation requires us to examine the connections between abstract algebra and formal languages. We present results, some original to this thesis, concerning the size of the largest monoid generated by two elements. Also, we give good bounds on the worst-case state complexity of root(<i>L</i>). In turn, these new results concerning root(<i>L</i>) allow us to improve previous bounds given for the state complexity of two-way deterministic finite automata.

In this thesis, we cover the general topic of state complexity. In particular, we examine the bounds on the state complexity of some different representations of regular languages. As well, we consider the state complexity of the operation root(<i>L</i>). We give quick treatment of the deterministic state complexity bounds for nondeterministic finite automata and regular expressions. This includes an improvement on the worst-case lower bound for a regular expression, relative to its alphabetic length. The focus of this thesis is the study of the increase in state complexity of a regular language <i>L</i> under the operation root(<i>L</i>). This operation requires us to examine the connections between abstract algebra and formal languages. We present results, some original to this thesis, concerning the size of the largest monoid generated by two elements. Also, we give good bounds on the worst-case state complexity of root(<i>L</i>). In turn, these new results concerning root(<i>L</i>) allow us to improve previous bounds given for the state complexity of two-way deterministic finite automata.

The rewrite relation with parameters m and n and with the possible lengthlimit = k or :::; k we denote by w~, =kW~· or ::;kw~ respectively. Theidempotency languages generated from a starting word w by the respectiveoperations are wD<l::', w=kD<l::' and W<;kD<l::'.Also other special cases of idempotency languages besides duplication havecome up in different contexts. The investigations of Ito et al. about insertionand deletion, Le., operations that are also observed in DNA molecules, haveestablished that w5 and w~ both preserve regularity.Our investigations about idempotency relations and languages start out fromthe case of a uniform length bound. For these relations =kW~ the conditionsfor confluence are characterized completely. Also the question of regularity is-k n answered for aH the languages w- D<lm . They are nearly always regular. Onlythe languages wD<lo for n > 1 are more complicated and belong to the class ofcontext-free languages.For a generallength bound, i.e."for the relations :"::kW~, confluence doesnot hold so frequently. This complicatedness of the relations results also inmore complicated languages, which are often non-regular, as for example thelanguages W<;kD<l::' for aH bounds k 2 4. For k :::; 2 they are regular. The case ofk :::; 3, though, remains open. We show, however, that none of these languagesever exceeds the complexity of being context-free.Without any length bound, idempotency relations have a very complicatedstructure. Over alphabets of one or two letters we still characterize the conditionsfor confluence. Over three or more letters, in contrast, only a few casesare solved. We determine the combinations of parameters that result in theregularity of wD<l::', when the alphabet of w contains only two letters. Only thecase of 2 :::; m < n remains open.In a second chapter sorne more involved questions are solved for the specialcase of duplication. First we shed sorne light on the reasons why it is so difficultto determine the context-freeness ofduplication languages. We show that theyfulfiH aH pumping properties and that they are very dense. Therefore aH thestandard tools to prove non-context-freness do not apply here.The concept of root in Formal Language ·Theory is frequently used to describethe reduction of a word to another one, which is in sorne sense elementary.For example, there are primitive roots, periodicity roots, etc. Elementaryin connection with duplication are square-free words, Le., words that do notcontain any repetition. Thus we define the duplication root of w to consist ofaH the square-free words, from which w can be reached via the relation w~.Besides sorne general observations we prove the decidability of the question,whether the duplication root of a language is finite.Then we devise acode, which is robust under duplication of its code words.This would keep the result of a computation from being destroyed by duplications in the code words. We determine the exact conditions, under whichinfinite such codes exist: over an alphabet of two letters they exist for a lengthbound of 2, over three letters already for a length bound of 1.Also we apply duplication to entire languages rather than to single words;then it is interesting to determine, whether regular and context-free languagesare closed under this operation. We show that the regular languages are closedunder uniformly bounded duplication, while they are not closed under duplicationwith a generallength bound. The context-free languages are closed underboth operations.The thesis concludes with a list of open problems related with the thesis'topics.