• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 70
  • 19
  • 15
  • 7
  • 5
  • 4
  • 4
  • 4
  • 4
  • 4
  • 4
  • 2
  • 2
  • 1
  • 1
  • Tagged with
  • 139
  • 139
  • 70
  • 64
  • 54
  • 54
  • 38
  • 27
  • 26
  • 26
  • 24
  • 22
  • 21
  • 18
  • 16
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Ogden's lemma for random permitting and forbidding context picture languages and table-driven context-free picture languages

Idahosa, Joy O 06 May 2015 (has links)
A dissertation submitted to the Faculty of Science, University of the Witwatersrand, Johannesburg, in fulfilment of requirements for the degree of Master of Science. Johannesburg, February 16, 2015. / Random context picture grammars are used to generate pictures through successive refinement. There are three important subclasses of random context picture grammars, namely random permitting context picture grammars, random forbidding context picture grammars and table-driven context-free picture grammars. These grammars generate the random permitting context picture languages, random forbidding context picture languages and table-driven context-free picture languages, respectively. Theorems exist which provide necessary conditions that have to be satisfied by a language before it can be classified under a particular subclass. Some of these theorems include the pumping and shrinking lemmas, which have been developed for random permitting context picture languages and random forbidding context picture languages respectively. Two characterization theorems were developed for the table-driven context-free picture languages. This dissertation examines these existing theorems for picture languages, i.e., the pumping and shrinking lemmas and the two characterisation theorems, and attempts to prove theorems, which will provide an alternative to the existing theorems and thus provide new tools for identifying languages that do not belong to the various classes. This will be done by adapting Ogden’s idea of marking parts of a word which was done for the string case. Our theorems essentially involve marking parts of a picture such that the pumping operation increases the number of marked symbols and the shrinking operation reduces it.
2

On context-free derivations

Mäkinen, Erkki. January 1985 (has links)
Thesis (Ph. D.)--University of Tampere, 1985. / Includes bibliographical references (p. 91-94).
3

Some combinatorial and algebraic problems related to subwords

Péladeau, Pierre. January 1986 (has links)
No description available.
4

Desátomat - aplikace pro názornou výuku problematiky formálních gramatik

Dusíková, Hana January 2011 (has links)
No description available.
5

Some combinatorial and algebraic problems related to subwords

Péladeau, Pierre. January 1986 (has links)
No description available.
6

A survey of Greibach normal form : transformation & analysis /

Ho, Man Chi. January 2006 (has links)
Thesis (M.Phil.)--Hong Kong University of Science and Technology, 2006. / Includes bibliographical references (leaves 49-50). Also available in electronic version.
7

Knowledge representation in mathematics : a case study in graph theory /

Epstein, Susan Lynn. January 1983 (has links)
Thesis (Ph. D.)--Rutgers University, 1983. / Includes bibliographical references (p. 271-274).
8

Some results on systolic tree automata as acceptors

Foufa, Aouaouche Fazileit January 1985 (has links)
No description available.
9

Applications of algebraic automata theory to quantum finite automata

Mercer, Mark. January 2007 (has links)
No description available.
10

Languages Generated by Iterated Idempotencies.

Leupold, Klaus-Peter 22 November 2006 (has links)
The rewrite relation with parameters m and n and with the possible length limit = k or :::; k we denote by w~, =kW~· or ::;kw~ respectively. The idempotency languages generated from a starting word w by the respective operations are wD<l::', w=kD<l::' and W<;kD<l::'.Also other special cases of idempotency languages besides duplication have come up in different contexts. The investigations of Ito et al. about insertion and deletion, Le., operations that are also observed in DNA molecules, have established that w5 and w~ both preserve regularity.Our investigations about idempotency relations and languages start out from the case of a uniform length bound. For these relations =kW~ the conditions for 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. Only the languages wD<lo for n > 1 are more complicated and belong to the class of context-free languages.For a generallength bound, i.e."for the relations :"::kW~, confluence does not hold so frequently. This complicatedness of the relations results also in more complicated languages, which are often non-regular, as for example the languages W<;kD<l::' for aH bounds k 2 4. For k :::; 2 they are regular. The case of k :::; 3, though, remains open. We show, however, that none of these languages ever exceeds the complexity of being context-free.Without any length bound, idempotency relations have a very complicated structure. Over alphabets of one or two letters we still characterize the conditions for confluence. Over three or more letters, in contrast, only a few cases are solved. We determine the combinations of parameters that result in the regularity of wD<l::', when the alphabet of w contains only two letters. Only the case of 2 :::; m < n remains open.In a second chapter sorne more involved questions are solved for the special case of duplication. First we shed sorne light on the reasons why it is so difficult to determine the context-freeness ofduplication languages. We show that they fulfiH aH pumping properties and that they are very dense. Therefore aH the standard tools to prove non-context-freness do not apply here.The concept of root in Formal Language ·Theory is frequently used to describe the reduction of a word to another one, which is in sorne sense elementary.For example, there are primitive roots, periodicity roots, etc. Elementary in connection with duplication are square-free words, Le., words that do not contain any repetition. Thus we define the duplication root of w to consist of aH 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 dupli cations in the code words. We determine the exact conditions, under which infinite such codes exist: over an alphabet of two letters they exist for a length bound 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 languages are closed under this operation. We show that the regular languages are closed under uniformly bounded duplication, while they are not closed under duplication with a generallength bound. The context-free languages are closed under both operations.The thesis concludes with a list of open problems related with the thesis' topics.

Page generated in 0.1258 seconds