Algebraic theory of minimal nondeterministic finite automata with applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA’s behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

The Pronunciation of the Aspirated Consonants P, T, and K in English by Native Speakers of Spanish and French

This study examines whether explicit phonetic instruction helps Spanish and French speakers more closely approximate native pronunciation of the aspirated variants of the English consonants p, t, and k. The study results indicate that phonetic instruction clearly benefited the subjects, and the findings warrant further investigation.

Gesture Recognition Using Neural Networks Based on HW/SW Cosimulation Platform

Hardware/software (HW/SW) cosimulation integrates software simulation and hardware simulation simultaneously. Usually, HW/SW co-simulation platform is used to ease debugging and verification for very large-scale integration (VLSI) design. To accelerate the computation of the gesture recognition technique, an HW/SW implementation using field programmable gate array (FPGA) technology is presented in this paper. The major contributions of this work are: (1) a novel design of memory controller in the Verilog Hardware Description Language (Verilog HDL) to reduce memory consumption and load on the processor. (2) The testing part of the neural network algorithm is being hardwired to improve the speed and performance. The American Sign Language gesture recognition is chosen to verify the performance of the approach. Several experiments were carried out on four databases of the gestures (alphabet signs A to Z). (3) The major benefit of this design is that it takes only few milliseconds to recognize the hand gesture which makes it computationally more efficient.

Algebraic Theory of Minimal Nondeterministic Finite Automata with Applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA's behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

A escrita no Ensino Fundamental II: uma análise dos desvios ortográficos e sugestões de estratégias de intervenção

This paper presents a reflection on the written language, a social practice that is increasingly strengthened in everyday life. Unveiling its nature, organization and function must be the first step for teachers to change their posture towards the teaching of this linguistic mode, helping students use it more effectively and securely. Considering these principles, this dissertation seeks to understand on the light of contemporary linguistic theories, the factors that influence the writing deviations were found in the text production of students of the 8th grade of elementary school II, enrolled in a public school in Rio Grande do Norte, whereas those deviations reveal the beginning of learning of this communication tool, representing the first hypotheses raised by students to dominate it. To analyze the data we used the works done by Lemle (1995), Cagliari (2009), Carraher (1985), Zorzi (1998), Guimarães (2005), Miller (2008), Veçossi (2010), among others, starting from of which, the scientific production on reading and writing learning come developing. The results of this analysis showed that the writing deviations present in the texts of the students are motivated not only by lack of knowledge of standard orthographic of the Portuguese language, but, also, stem from phonetic, phonological and grammatical factors. Thus, we seek to present new teaching and learning strategies of writing that might lead students to reflect on the use of the same, developing this ability more critically and creatively. We believe that the activities presented can minimize writing with orthographic deviations or linguistic variation practiced by students. Keywords: Variances writing, spelling, teaching strategies and students

O slogan empresarial como construção discursiva: uma abordagem cognitivo-funcional

In this paper, we analyze corporate slogans, understanding them as a discursive construction that is, as a pairing of form and function able to unite the notions of textual type and discursive genre. In this way, we developed a qualitative and quantitative analysis, aimed specifically to analyze the formal properties (phonetic, morphological and syntactic) and functional (semantic, pragmatic and discursive) of slogans. Furthermore, we attempted at verifying and quantifying recurring aspects involved in their construction, in order to capture configurational patterns underlying their formation. The data come from slogans collected in products and / or service stores in the metropolitan area of Natal city, Rio Grande do Norte. This research is based on the Cognitive-Functional Linguistics, that conjugates the North American functionalist tradition, represented by researchers as Talmy Givón, Paul Hopper, Joan Bybee, Elizabeth Closs-Traugott, with Cognitive Linguistics, in particular, the chain linked to Construction Grammar, as postulated by Adele Goldberg, William Croft e Jan-Olla Östman, among others. The results ratified the importance of the interface between the formal and functional aspects in the analysis of linguistic uses. These results point to the idea of the slogan as the pairing of form and function on textual / discursive level, in other words, as a discursive construction, constituting as cognitive storage of a scheme / model of textual formation with a specific discursive-pragmatic function.

O ciclo Slopiewnie opus 46 bis de Karol Szymanowski: uma abordagem de estudo e performance

This text presents a discussion about the song cycle Slopiewnie Opus 46 bis of Karol Szymanowski, one of the most important Polish composers of the 20th century. Slopiewnie was composed on texts of Julian Tuwim, poet born in 1894 in Łódź, who used ancient roots to create new words and search for special sonorities. First, this text introduces a brief biographical sketch about Szymanowski, in order to contextualize Slopiewnie in relation to the composer’s works. Afterwards, the text provides an analysis of the songs and their texts, which may serve as a study tool for future perfomers. Interpretative suggestions are offered, based on the experience of learning these songs and on references. The text also presents the phonetic transcription of the poems, as well as a suggested translation to Portuguese, making it easier for Brazilian singers to learn the cycle’s text and prosody.

Provocative feature deletion: a syntactic model of agreement alternations in noun incorporation contexts

The relationship between noun incorporation (NI) and the agreement alternations that occur in such contexts (NI Transitivity Alternations) remains inadequately understood. Three interpretations of these alternations (Baker, Aranovich & Golluscio 2005; Mithun 1984; Rosen 1989) are shown to be undermined by foundational or mechanical issues. I propose a syntactic model, adopting Branigan's (2011) interpretation of NI as the result of “provocative” feature valuation, which triggers generation of a copy of the object that subsequently merges inside the verb. Provocation triggers a reflexive Refine operation that deletes duplicate features from chains, making them interpretable for Transfer. NI Transitivity Alternations result from variant deletion preferences exhibited during Refine. I argue that the NI contexts discussed (Generic NI, Partial NI and Double Object NI) result from different restrictions on phonetic and semantic identity in chain formation. This provides us with a consistent definition of NI Transitivity Alternations across contexts, as well as a new typology that distinguishes NI contexts, rather than incorporating languages.

Alphabeti verè Naturalis Hebraici brevissima delineatio : Quæ simul Methodum suppenditat, juxta quam qui surdi nati sunt sic informari possunt, ut non alios saltem loquentes intelligant, sed & ipsi ad sermonis usum perveniant

in lucem edita à F. M. B. ab Helmont

As vogais médias tônicas: um estudo contrastivo da metafonia com base em corpus

This research analyzes the average previous stressed vowels [ε] and [e] and later [ɔ] and [o] in nominal and verbal forms in the 1st person singular and 3rd person singular and plural in the present tense, specifically the umlaut process of mid vowels /e/ and /o/, which assimilate in /ε/ and /ᴐ/ in stressed position. The general objective of this research is to describe and quantify the occurrence of umlaut and subsequently analyze in which words there is regularity or not. As specific objectives we have: i) to compile and to label an oral, spontaneous, synchronic and regional corpus, from radio programs produced in the city of Ituiutaba, Minas Gerais; ii) to describe the characteristics of the corpus to be compiled; iii) to investigate the alternating timbre of mid vowels in stressed position; iv) to identify instances of nominal and verbal umlaut of the middle vowels in stressed position; v) to describe the identified cases of nominal and verbal umlaut; vi) to analyze the probable causes for the variation of the middle vowels. To perform the proposed analysis, we have adopted as a theoretical-methodological basis multi-representational models: Phonology of Use (BYBEE, 2001) and Exemplar Theory (PIERREHUMBERT, 2001) combined with the precepts of Corpus Linguistics (BEBER SARDINHA, 2004). The corpus consisted of 16 radio programs – eight political and eight religious – from the city of Ituiutaba-MG, with recordings of about 20 to 40 minutes. We note, by means of the results generated by WordSmith Tools® software, version 6.0 (SCOTT, 2012), that the analyzed forms show little variation, which shows that the umlaut is a process already lexicalized in participants of the radio programs analyzed. We conclude that the results converge with the proposal of the Phonology of Use (BYBEE, 2001; PHILLIPS, 1984) that less frequent words that have no phonetic environment conducive to change, are changed first.

Across-formant integration and speech intelligibility:effects of acoustic source properties in the presence and absence of a contralateral interferer

The role of source properties in across-formant integration was explored using three-formant (F1+F2+F3) analogues of natural sentences (targets). In experiment 1, F1+F3 were harmonic analogues (H1+H3) generated using a monotonous buzz source and second-order resonators; in experiment 2, F1+F3 were tonal analogues (T1+T3). F2 could take either form (H2 or T2). Target formants were always presented monaurally; the receiving ear was assigned randomly on each trial. In some conditions, only the target was present; in others, a competitor for F2 (F2C) was presented contralaterally. Buzz-excited or tonal competitors were created using the time-reversed frequency and amplitude contours of F2. Listeners must reject F2C to optimize keyword recognition. Whether or not a competitor was present, there was no effect of source mismatch between F1+F3 and F2. The impact of adding F2C was modest when it was tonal but large when it was harmonic, irrespective of whether F2C matched F1+F3. This pattern was maintained when harmonic and tonal counterparts were loudness-matched (experiment 3). Source type and competition, rather than acoustic similarity, governed the phonetic contribution of a formant. Contrary to earlier research using dichotic targets, requiring across-ear integration to optimize intelligibility, H2C was an equally effective informational masker for H2 as for T2.

Other Than a Citizen: Vernacular Poetics in Postwar America

Few symbols of 1950s-1960s America remain as central to our contemporary conception of Cold War culture as the iconic ranch-style suburban home. While the house took center stage in the Nixon/Khrushchev kitchen debates as a symbol of modern efficiency and capitalist values, its popularity depended largely upon its obvious appropriation of vernacular architecture from the 19th century, those California haciendas and Texas dogtrots that dotted the American west. Contractors like William Levitt modernized the historical common houses, hermetically sealing their porous construction, all while using the ranch-style roots of the dwelling to galvanize a myth of an indigenous American culture. At a moment of intense occupational bureaucracy, political uncertainty and atomized social life, the rancher gave a self-identifying white consumer base reason to believe they could master their own plot in the expansive frontier. Only one example of America’s mid-century love affair with commodified vernacular forms, the ranch-style home represents a broad effort on the part of corporate and governmental interest groups to transform the vernacular into a style that expresses a distinctly homogenous vision of American culture. “Other than a Citizen” begins with an anatomy of that transformation, and then turns to the work of four poets who sought to reclaim the vernacular from that process of standardization and use it to countermand the containment-era strategies of Cold War America.

In four chapters, I trace references to common speech and verbal expressivity in the poetry and poetic theory of Charles Olson, Robert Duncan, LeRoi Jones/Amiri Baraka and Gwendolyn Brooks, against the historical backdrop of the Free-Speech Movement and the rise of mass-culture. When poets frame nonliterary speech within the literary page, they encounter the inability of writing to capture the vital ephemerality of verbal expression. Rather than treat this limitation as an impediment, the writers in my study use the poem to dramatize the fugitivity of speech, emphasizing it as a disruptive counterpoint to the technologies of capture. Where critics such as Houston Baker interpret the vernacular strictly in terms of resistance, I take a cue from the poets and argue that the vernacular, rooted etymologically at the intersection of domestic security and enslaved margin, represents a gestalt form, capable at once of establishing centralized power and sparking minor protest. My argument also expands upon Michael North’s exploration of the influence of minstrelsy and regionalism on the development of modernist literary technique in The Dialect of Modernism. As he focuses on writers from the early 20th century, I account for the next generation, whose America was not a culturally inferior collection of immigrants but an imperial power, replete with economic, political and artistic dominance. Instead of settling for an essentially American idiom, the poets in my study saw in the vernacular not phonetic misspellings, slang terminology and fragmented syntax, but the potential to provoke and thereby frame a more ethical mode of social life, straining against the regimentation of citizenship.

My attention to the vernacular argues for an alignment among writers who have been segregated by the assumption that race and aesthetics are mutually exclusive categories. In reading these writers alongside one another, “Other than a Citizen” shows how the avant-garde concepts of projective poetics and composition by field develop out of an interest in black expressivity. Conversely, I trace black radicalism and its emphasis on sociality back to the communalism practiced at the experimental arts college in Black Mountain, North Carolina, where Olson and Duncan taught. In pressing for this connection, my work reveals the racial politics embedded within the speech-based aesthetics of the postwar era, while foregrounding the aesthetic dimension of militant protest.

Not unlike today, the popular rhetoric of the Cold War insists that to be a citizen involves defending one’s status as a rightful member of an exclusionary nation. To be other than a citizen, as the poets in my study make clear, begins with eschewing the false certainty that accompanies categorical nominalization. In promoting a model of mutually dependent participation, these poets lay the groundwork for an alternative model of civic belonging, where volition and reciprocity replace compliance and self-sufficiency. In reading their lines, we become all the more aware of the cracks that run the length of our load-bearing walls.

Examining Cognitive Processing in Children with an Arithmetic Disability

Currently there is no consensus as to the specific cognitive impairments that characterize mathematical disabilities (MD) or specific subtypes such as an arithmetic disability (AD). The present study sought to address this concern by examining cognitive processes that might undergird AD in children. The present study utilized archival data to conduct two investigations. The first investigation examined the executive functioning and working memory of children with AD. An age-matched achievement-matched design was employed to explore whether children with AD exhibit developmental lags or deficits in these cognitive domains. While children with AD did not exhibit impairments in verbal working memory or colour word inhibition, they did demonstrate impairments in shifting attention, visual-spatial working memory, and quantity inhibition. As children with AD did not perform more poorly than their younger achievement-matched peers on any of these tasks, impairments in specific areas of executive functioning and working memory appeared to reflect a developmental lag rather than a cognitive deficit. The second study examined the phonological processing performance of children with AD compared to children with comorbid disabilities in arithmetic and word recognition (AD/WRD) and to typically achieving (TA) children. Results indicated that, while children with AD did demonstrate impairments on all isolated naming speed tasks, trail making digits, and memory for digits, they did not demonstrate impairments on measures of phonological awareness, nonword repetition, serial processing speed, or serial naming speed. In contrast, children with AD/WRD demonstrated impairments on measures of phonological awareness, phonological short-term memory, isolated naming speed, serial processing speed, and the alphabet a-z task. Overall, results suggested that phonological processing impairments are more prominent in children with a WRD than children with an AD. Together, these studies further our understanding of the nature of the cognitive processes that underlie AD by focusing upon rarely used methods (i.e., age-matched achievement-matched design) and under-examined cognitive domains (i.e., phonological processing).

Modern foreign languages get a voice: the role of the journals

This chapter investigates the significance of specialized journals for the development of modern language teaching. It begins by explaining the development of language journals up to the point at which language teaching reform really took off with the emergence of the so-called Reform Movement in the 1880s. The principal journal for this movement was Phonetische studien [Phonetic Studies] founded in 1888 and renamed Die neueren Sprachen [Modern languages] in 1894. The style of the early issues of this journal allows modern readers an insight into the discourse practices of that community of language scholars and teachers, the opportunity to hear its characteristic ‘voice’ and recreate the means by which modern foreign language teaching became an independent discipline.