Orientador: Clotilde de Almeida Azevedo Murakawa / Resumo: A derivação é apresentada pelas gramáticas tradicionais como uma lista de prefixos e sufixos, divididos em gregos e latinos, com seus significados e acompanhados de exemplos. Com essa limitação no estudo da derivação, não são apresentadas as possíveis combinações das unidades lexicais com os prefixos, nem tampouco é admitido que, para se formar um derivado prefixado, é preciso que a base a que se junta o prefixo aceite a significação que lhe será impressa. Outra falha ocorre nos dicionários que se limitam a definir as entradas lexicais não contextualizadas dificultando o entendimento do significado da unidade derivada, pois nem sempre é possível entender sua formação visto que o prefixo pode admitir significados diferentes e somente o contexto pode precisar esse significado. Desta forma, o processo de formação de palavras tradicionalmente atrbuído à morfologia deve envolver também outros níveis da língua: sintaxe, semântica e pragmática. Uma vez considerados esses níveis é possível estabelecer paradigmas que sistematizem a formação de palavras considerando o significado do derivado contextualizando e os semas contidos na base. Este trabalho teve como objetivo identificar o paradigma derivacional dos verbos formados por prefixos latinos de movimento, o tipo de base a que se anexam os prefixos, as classes gramticais que entram na formação do derivado e o dignificado contextual do prefixo na unidade lexical analisando o valor semântico do derivado, bem como as interferências pragmáticas. Cnclui-se que, analisando o derivado sob a perspectiva morfológica, semântica, sintática e pragmática, é possível estabelecer um paradigma do sistema prefixal da língua considerando o aspecto diacrônico dos prefixos, os semas das unidades lexicais, agrupando as unidades que apresentam semas comuns e o comportamento pragmético da unidade derivada. / Abstract: The derivation is presented by the traditional grammars as a list of prefixes and suffices, divided into Greek and Latin, with their meanings and accompained by examples. With this limitation in the study of the derivation, possible combinations of the lexical units with the prefixes are not presented. In addition, it is not admitted that, in order to from a derived prefix it is necessary that the base to which the prefix joins, accepts its new signification. Another failure occurs in dictionaries that only define the non-contextualized lexical entries, making it difficult to understand the meaning of the derived unit, as it is not always possible to undestand its formation, since the prefix can admit different meanings and only the context may clarify this meaning. Therefore, the formation process of words, traditionally ascribed to morphology, may also involve other levels of the language: syntax, semantics and pragmatics. Once considered these sectors, it is possible to establish that systematize the formation of words, considering the meaning of the contextualized derived and the semes contaimed in the base. This paper has had the aim to identiflay the derivational paradigm of the verbs formed by Latin prefixes of movement, the kind of base to which the prefixes attach, the grammatical classes that enter in the formation of the derived and the contextual meaning of the prefix in the lexical unit, analyzing the semantic value of the derived, as well as the pragmatic interferences. It was concluded that, analysing the derived under the morphological, semantic, and pragmatic perspectives, it is possoble to establish a paradigm of the prefix system of the language considering the diachronic aspect of the prefixes, the semes of the lexical units, joing the units that present common semes and the pragmatic behavior of the derived unit. / Doutor

Higher-Order Pushdown Automata (HOPDA) are abstract machines equipped with a nested stacks of stacks ... of stacks of stacks. Collapsible pushdown automata (CPDA) enhance these stacks with the addition of ‘links’ emanating from atomic elements to the higher-order stacks below. For trees CPDA are equi-expressive with recursion schemes, which can be viewed as simply-typed λY terms. With vanilla HOPDA, one can only capture schemes satisfying a syntactic constraint called safety. This dissertation begins with some results concerning the significance of links in terms of recursion schemes. We introduce a fine-grained notion of safety that allows us to correlate the need for links of a given order with the imposition of safety on variables of a corresponding order. This generalises some joint work with William Blum that shows we can dispense with homogeneous types when characterising safety. We complement this result with a demonstration that homogeneity by itself does not constrain the expressivity of otherwise unrestricted recursion schemes. The main results of the dissertation, however, concern the configuration graphs of CPDA. Whilst the configuration graphs of HOPDA are well understood and have decidable MSO theories (they coincide with the Caucal hierarchy), relatively little is known about the transition graphs of CPDA. It is known that they already have undecidable MSO theories at order-2, but Kartzow recently showed that 2-CPDA graphs are tree automatic and hence first-order logic is decidable at order-2. We provide a characterisation of the decidability of first-order logic on CPDA graphs in terms of quantifier-alternation and the order of CPDA stacks and the links contained within. Whilst this characterisation is fairly comprehensive, we do leave open the question of decidability for some sub-classes of CPDA. It turns out that decidability can be highly sensitive to the order of links in a stack relative to the order of the stack itself. In addition to some strong and surprising undecidability results, we also develop further Kartzow’s work on 2-CPDA. We introduce prefix-rewrite systems for nested-words that characterise the configuration graphs of both 2-CPDA and 2-HOPDA, capturing the power of collapse precisely in terms outside of the language of CPDA. It also formalises and demonstrates the inherent asymmetry of the collapse operation. This generalises the rational prefix-rewriting systems characterising conventional pushdown graphs and we believe establishes the 2-CPDA graphs as an interesting and robust class.

The master's thesis describes the semantic development and usage of prefixes s-, z- and vz- in Czech. The thesis begins with a short summary of theoretical background, definition of the subject matter and terms used. It then proceeds with etymological analysis and description of meanings of equivalents of these prefixes in Old Slavic. Following chapters analyze the competition of the three prefixes in Old Czech, describing the factors that impacted their use and provide an overview of the matter in New Czech, with regards to the semantic aspect of the mentioned prefixes. Subsequently, the thesis summarizes orthographic principles of s- and z- (and vz-) from the 16th century up to present times. The last chapter provides an overview of the situation in other Slavic languages with respect to the West Slavic branch. Attention is also paid to the matter of merging the prefixes s- and z- into one.

The dissertation deals with the question of verbal aspect and manner of verbal action in Czech and Ukrainian language. The aim is to describe prefixes, which are used as means of verbal derivation and formation of aspectual pairs. The present study is divided into chapters: Introduction, Resear of verbal aspekt and Aktionsart, Verbal aspect, Manner of verbal action (Aktionsart), Competition between prefixes in the meaning of aspectual pairs formation and derivation of verbs in Czech and Ukrainian langure, Summary. There are differences in the number of verbal prefixes, which have beside derivational function also grammatical function. Czech language has sixteen of these verbal prefixes, in Ukrainian there are only seven verbal prefixes, which are used in both of these processes. This is conspicuous difference, but the results of the analysis showed, that the possibilities of applying specific prefixes are in both compared languages remarkably consistent. Many verbs of various categories of verbal action manner are derived in West and East Slavic language by the same prefixes. Consensus is also in preference of identical prefixes, which are the most commonly used during pure perfectivization (especially Czech z- and Ukrainian з-/с-). Keywords verbal aspect manner of verbal action (Aktionsart) prefix

Applying basic linguistic theory, a grammatical analysis of Gothic verbs formed with the previously underdescribed quasi-prefix (or preverb) miþ- shows that it forms what could be called an atypical type of applicative, though in two cases it seems instead to mark verbal congruence to an adverbial. Of the possible meanings of the etymologically identical preposition miþ, the comitative seems most salient for the quasi-prefix. An introduced core argument in these constructions do not behave like a typicaltransitive object, as it cannot be passivised, and so is likely rather an extension E (or indirect object) to the core. An underlying transitive object O remains as is, and can be passivised. The construction is only used when E pertains to the topic of the discourse, either an overlapping or a new topic. It is never a background comment, as is attested with peripheral arguments. The dative case of the introduced E seems to be semantically motivated, it being thecombination—comparable to a complex case marking—of the preposition and the quasi-prefix with the dative case that signals the comitative meaning. This construction is formally unrestrained, being applied to intransitive, ambitransitive, and transitive verbs, either with or without vowel gradation. In most cases the introduced E has a human referent, but it can also be a concrete object or an abstract. It cannot be inferred from this investigation whether Gothic allowed more than one applicative construction to be applied to the same verb. It would seem there are indications that this construction might have been a relatively new and developing construction in Gothic. In the verbal template, miþ- occupies the outermost position, in itself an indication of late grammaticalization. The one extant exception to this position could indicate an uncertainty of the translator regarding as to which its proper place was. The two instances with both miþ- and a comitative adverbial suggest—unless an artifact of translation—a possible development from peripheral argument to an atypical E-introducing applicative via verbal congruence.

We consider a class of problems characterized by the need for a string based identifier that reflect the ontology of the application domain. We present rules for string-based identifier schemas that facilitate fast filtering in databases used for this class of problems. We provide runtime analysis of our schema and experimentally compare it with another solution. We also discuss performance in our solution to a game engine. The string-based identifier schema can be used in addition scenarios such as cloud computing. An identifier schema adds metadata about an element. So the solution hinges on additional memory but as long as queries operate only on the included metadata there is no need to load the element from disk which leads to huge performance gains.

Modern routers use specialized hardware, such as Ternary Content Addressable Memory (TCAM), to solve the Longest Prefix Matching Problem (LPMP) quickly. Due to the fact that TCAM is a non-standard type of memory and inherently parallel, there are concerns about its cost and power consumption. This problem is exacerbated by the growth in routing tables, which demands ever larger TCAMs. To reduce the size of the TCAMs in a distributed forwarding environment, a batch caching model is proposed and analyzed. The problem of determining which routing prefixes to store in the TCAMs reduces to the In-tree Knapsack Problem (ITKP) for unit weight vertices in this model. Several algorithms are analysed for solving the ITKP, both in the general case and when the problem is restricted to unit weight vertices. Additionally, a variant problem is proposed and analyzed, which exploits the caching model to provide better solutions. This thesis concludes with discussion of open problems and future experimental work.

Kraven på dagens trådlösa förbindelser kommer hela tiden att öka och med detta följer även högre krav på nya produkter som kan tillgodose de ökade kraven. För att göra processen från idé till produkt snabbare krävs enkla verktyg för att snabbt kunna gå från den formulerade standarden till en hårdvaruprototyp. Detta arbete har använt sig av ett av dessa verktyg som idag finns tillgängliga, Xilinx System Generator for DSP 1.1, för att ta fram sändare och mottagare för en del av den trådlösa standarden IEEE 802.11a. Arbetet ger en beskrivning av hur sändare och mottagare är uppbyggda samt även synpunkter på System Generator och beskrivningar av problem som uppstod under arbetet. / The demands on todays wireless communications will continue to increase and with this follows a demand for shorter and shorter development times for the products that are going to satisfy this demand. To accomplish this shorter development time simple tools for going from the formulated standard to a hardware prototype is needed. This work uses one of these tools today available, Xilinx System Generator for DSP 1.1, to develop a transmitter and a reciever for a part of the wireless standard IEEE 802.11a. The work gives a description of the building blocks of the transmitter and the reciever but also some views on System Generator and descriptions of problems that were encountered during the work.

Modern routers use specialized hardware, such as Ternary Content Addressable Memory (TCAM), to solve the Longest Prefix Matching Problem (LPMP) quickly. Due to the fact that TCAM is a non-standard type of memory and inherently parallel, there are concerns about its cost and power consumption. This problem is exacerbated by the growth in routing tables, which demands ever larger TCAMs. To reduce the size of the TCAMs in a distributed forwarding environment, a batch caching model is proposed and analyzed. The problem of determining which routing prefixes to store in the TCAMs reduces to the In-tree Knapsack Problem (ITKP) for unit weight vertices in this model. Several algorithms are analysed for solving the ITKP, both in the general case and when the problem is restricted to unit weight vertices. Additionally, a variant problem is proposed and analyzed, which exploits the caching model to provide better solutions. This thesis concludes with discussion of open problems and future experimental work.

For more than a decade, streaming media services, including on-line conferences, distance education and movie broadcasting, have gained much popularity on the Internet. Due to the high bandwidth requirements and long lived nature of video streaming, it requires huge transmission cost to support these streaming media services. In addition, how to adapt rich multimedia content to satisfy various resource-constrained devices presents a challenge. The limited and time-varying network bandwidth complicates the content adaptation tasks. Differentiated content delivery may be required to meet diverse client profiles and user preferences. Therefore, in order to reduce transmission cost to serve heterogeneous clients for efficient streaming, in this dissertation, several novel schemes including transcoding-enable proxy caching scheme, reactive transmission schemes, and network coding P2P content distribution scheme, are proposed to support efficient multiple-version and layered video delivery in the proxy-attached network environment as well as to provide efficient interactive IPTV service in a peer-to-peer network. Firstly, for multiple-version cache consideration in the transcoding-enable proxy, we focus on reducing the required server bandwidth and startup delay by caching the optimal versions of the video. A generalized video object profit function is derived from the extended weighted transcoding graph to calculate the individual cache profit of certain version of a video object, and the aggregate profit from caching multiple versions of the same video object. This proposed function takes into account the popularity of certain version of a video object, the transcoding delay among versions and the average access duration of each version. Based on the profit function, cache replacement algorithms are proposed to reduce the startup delay and network traffic by efficiently caching video objects with maximum profits. Next, a set of proxy-assisted transmission schemes are proposed to reduce the transmission cost for layered video streaming by integrating the proxy caching with reactive transmission schemes, peer-to-peer mesh networks and multicast capability. These proposed transmission schemes make multiple requests to be serviced by the single transmission and thus to significantly reduce the total required transmission cost. The optimal proxy prefix cache allocation is also calculated for each transmission scheme to identify the cache layers and cache length of each video to minimize the aggregate transmission cost. The process considers the fact that reduction in transmission cost by caching X layers of a video is not only from requests on X layers, but also from requests on less than X layers. Finally, we proposed a network coding equivalent content distribution (NCECD) scheme to decrease server stress, startup delay and jumping latency to support random access operations which are desirable for peer-to-peer on-demand video streaming. The random access operations are difficult to be efficiently supported, due to the asynchronous interactive behaviors of users and the dynamic nature of peers. In NCECD, videos are divided into segments which are then further divided into blocks. These blocks are then encoded into independent encoded blocks that are distributed to the local storage of different peers. With NCECD, a new client only needs to connect to a sufficient number of parent peers in order to view the whole video and rarely needs to find new parents when performing random access operations. Whereas most existing methods must search for parent peers containing interested segments, NCECD uses the properties of network coding to cache equivalent content on most peers, so that searches are rarely needed. The analysis of system parameters is given to achieve reasonable block loss rates for peer-to-peer interactive video-on-demand streaming. Experimental results demonstrate that these proposed schemes can lead to significant transmission cost saving, high delay saving ratio, high bandwidth saving ratio, low startup and jumping searching delays, connecting to a new parent peer delay and less server resources. Hence, these proposed schemes can further be integrated and utilized to build an efficient video streaming platform for providing high-performance and high-quality IPTV services to a diversity of clients.