Context-free and context-sensitive dynamics in recurrent neural networks

Continuous-valued recurrent neural networks can learn mechanisms for processing context-free languages. The dynamics of such networks is usually based on damped oscillation around fixed points in state space and requires that the dynamical components are arranged in certain ways. It is shown that qualitatively similar dynamics with similar constraints hold for a(n)b(n)c(n), a context-sensitive language. The additional difficulty with a(n)b(n)c(n), compared with the context-free language a(n)b(n), consists of 'counting up' and 'counting down' letters simultaneously. The network solution is to oscillate in two principal dimensions, one for counting up and one for counting down. This study focuses on the dynamics employed by the sequential cascaded network, in contrast to the simple recurrent network, and the use of backpropagation through time. Found solutions generalize well beyond training data, however, learning is not reliable. The contribution of this study lies in demonstrating how the dynamics in recurrent neural networks that process context-free languages can also be employed in processing some context-sensitive languages (traditionally thought of as requiring additional computation resources). This continuity of mechanism between language classes contributes to our understanding of neural networks in modelling language learning and processing.

On learning context-free and context-sensitive languages

The long short-term memory (LSTM) is not the only neural network which learns a context sensitive language. Second-order sequential cascaded networks (SCNs) are able to induce means from a finite fragment of a context-sensitive language for processing strings outside the training set. The dynamical behavior of the SCN is qualitatively distinct from that observed in LSTM networks. Differences in performance and dynamics are discussed.

Church-Rosser groups and growing context-sensitive groups

A finitely generated group is called a Church-Rosser group (growing context-sensitive group) if it admits a finitely generated presentation for which the word problem is a Church-Rosser (growing context-sensitive) language. Although the Church-Rosser languages are incomparable to the context-free languages under set inclusion, they strictly contain the class of deterministic context-free languages. As each context-free group language is actually deterministic context-free, it follows that all context-free groups are Church-Rosser groups. As the free abelian group of rank 2 is a non-context-free Church-Rosser group, this inclusion is proper. On the other hand, we show that there are co-context-free groups that are not growing context-sensitive. Also some closure and non-closure properties are established for the classes of Church-Rosser and growing context-sensitive groups. More generally, we also establish some new characterizations and closure properties for the classes of Church-Rosser and growing context-sensitive languages.

Context-sensitive analysis of obfuscated x86 executables

A method for context-sensitive analysis of binaries that may have obfuscated procedure call and return operations is presented. Such binaries may use operators to directly manipulate stack instead of using native call and ret instructions to achieve equivalent behavior. Since definition of context-sensitivity and algorithms for context-sensitive analysis have thus far been based on the specific semantics associated to procedure call and return operations, classic interprocedural analyses cannot be used reliably for analyzing programs in which these operations cannot be discerned. A new notion of context-sensitivity is introduced that is based on the state of the stack at any instruction. While changes in 'calling'-context are associated with transfer of control, and hence can be reasoned in terms of paths in an interprocedural control flow graph (ICFG), the same is not true of changes in 'stack'-context. An abstract interpretation based framework is developed to reason about stack-contexts and to derive analogues of call-strings based methods for the context-sensitive analysis using stack-context. The method presented is used to create a context-sensitive version of Venable et al.'s algorithm for detecting obfuscated calls. Experimental results show that the context-sensitive version of the algorithm generates more precise results and is also computationally more efficient than its context-insensitive counterpart. Copyright © 2010 ACM.

Context-sensitive analysis without calling-context

Since Sharir and Pnueli, algorithms for context-sensitivity have been defined in terms of 'valid' paths in an interprocedural flow graph. The definition of valid paths requires atomic call and ret statements, and encapsulated procedures. Thus, the resulting algorithms are not directly applicable when behavior similar to call and ret instructions may be realized using non-atomic statements, or when procedures do not have rigid boundaries, such as with programs in low level languages like assembly or RTL. We present a framework for context-sensitive analysis that requires neither atomic call and ret instructions, nor encapsulated procedures. The framework presented decouples the transfer of control semantics and the context manipulation semantics of statements. A new definition of context-sensitivity, called stack contexts, is developed. A stack context, which is defined using trace semantics, is more general than Sharir and Pnueli's interprocedural path based calling-context. An abstract interpretation based framework is developed to reason about stack-contexts and to derive analogues of calling-context based algorithms using stack-context. The framework presented is suitable for deriving algorithms for analyzing binary programs, such as malware, that employ obfuscations with the deliberate intent of defeating automated analysis. The framework is used to create a context-sensitive version of Venable et al.'s algorithm for analyzing x86 binaries without requiring that a binary conforms to a standard compilation model for maintaining procedures, calls, and returns. Experimental results show that a context-sensitive analysis using stack-context performs just as well for programs where the use of Sharir and Pnueli's calling-context produces correct approximations. However, if those programs are transformed to use call obfuscations, a contextsensitive analysis using stack-context still provides the same, correct results and without any additional overhead. © Springer Science+Business Media, LLC 2011.

A generic, context sensitive analysis framework for object oriented programs

Abstract interpreters rely on the existence of a nxpoint algorithm that calculates a least upper bound approximation of the semantics of the program. Usually, that algorithm is described in terms of the particular language in study and therefore it is not directly applicable to programs written in a different source language. In this paper we introduce a generic, block-based, and uniform representation of the program control flow graph and a language-independent nxpoint algorithm that can be applied to a variety of languages and, in particular, Java. Two major characteristics of our approach are accuracy (obtained through a topdown, context sensitive approach) and reasonable efficiency (achieved by means of memoization and dependency tracking techniques). We have also implemented the proposed framework and show some initial experimental results for standard benchmarks, which further support the feasibility of the solution adopted.

Random generation of sentences from context free and context sensitive phrase structure grammars.

Bibliography: p. 67.

Good readers use context-sensitive grapheme-phoneme correspondences

Fifth-grade children were given a series of word reading tasks. First, two sets of 16 disyllabic words with medial VCV spellings, and with a long initial vowel were selected, varying in frequency but with similar word-initial segments. Nonwords were derived from these sets of words by exchanging initial onsets. Children read these nonwords in a first testing session. In a second test session, children were given the Woodcock Word Identification Test and the set of analogue words from which the nonwords were derived. Initial analyses examined only nonwords derived from words that were correctly read. Both sets of nonwords were more likely to be read with a long initial vowel than a short initial vowel, although this tendency was stronger in nonwords derived from high frequency words. Furthennore, Word Identification ability showed a strong relationship with the preference for long initial vowels in this type of disyllabic nonword, both for nonwords derived from known analogues and for nonwords derived from words that children could not read correctly. This preference was also correlated with the preference for context-sensitive grapheme-phoneme correspondences in the reading of ambiguous monosyllabic nonwords.These results have strong implications for current theories of word reading.

Discourse and context in language teaching : a guide for language teachers.

Este texto recomienda a los profesores de lengua la incorporación del discurso y la pragmática a la enseñanza si quieren aplicar un enfoque comunicativo en las aulas. Los autores señalan que la utilización de estas dos disciplinas puede mejorar la enseñanza de la lingüística y el desarrollo de las habilidades de lectura, escritura, conversación y comprensión. También, trasladan el conocimiento del discurso al desarrollo curricular, a la evaluación del lenguaje y al estudio en el aula.

Semi-automatic knowledge extraction, representation and context-sensitive intelligent retrieval of video content using collateral context modelling with scalable ontological networks

Automatic indexing and retrieval of digital data poses major challenges. The main problem arises from the ever increasing mass of digital media and the lack of efficient methods for indexing and retrieval of such data based on the semantic content rather than keywords. To enable intelligent web interactions, or even web filtering, we need to be capable of interpreting the information base in an intelligent manner. For a number of years research has been ongoing in the field of ontological engineering with the aim of using ontologies to add such (meta) knowledge to information. In this paper, we describe the architecture of a system (Dynamic REtrieval Analysis and semantic metadata Management (DREAM)) designed to automatically and intelligently index huge repositories of special effects video clips, based on their semantic content, using a network of scalable ontologies to enable intelligent retrieval. The DREAM Demonstrator has been evaluated as deployed in the film post-production phase to support the process of storage, indexing and retrieval of large data sets of special effects video clips as an exemplar application domain. This paper provides its performance and usability results and highlights the scope for future enhancements of the DREAM architecture which has proven successful in its first and possibly most challenging proving ground, namely film production, where it is already in routine use within our test bed Partners' creative processes. (C) 2009 Published by Elsevier B.V.

L2 performance and context of language learning: a comparative study of learners in Tehran and London

The importance of learning context has stirred debates in the field of second language acquisition over the past two decades since studying a second language (L2) abroad is believed to provide authentic opportunities that facilitate L2 acquisition and development. The present paper examines whether language performance of learners studying English in a formal language classroom context at home (AH) is different from performance of learners who study English abroad (SA) where they would have to use English for a range of communicative purposes. The data for this comparative study is part of a larger corpus of L2 performance of 100 learners of English, 60 in Tehran and 40 in London, on four oral narrative tasks. The two groups’ performances are compared on a range of different measures of fluency, accuracy, syntactic complexity and lexical diversity. The results of the analyses indicate that learners in the two contexts are very similar with respect to the grammatical accuracy and aspects of the oral fluency of their performance. However, the SA group appears to have benefited from living and studying abroad in producing language of higher syntactic complexity and lexical diversity. These results have significant implications for language teaching in AH contexts.

Context-sensitive analysis of x86 obfuscated executables

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Context sensitive design of provincial road Galliera SP4.

In the past centuries and before the invention of automobile, roads consisted mainly of unpaved paths connecting only few cities. Later, in the beginning of the twentieth century, the automobile was introduced and a new type of the transportation system was born. Therefore, it was necessary to change the condition of roads to fit with the automobiles. With the spread and the development of the automobiles, roads also have developed and increased all over the world. That caused negative effects on the environment and humans’ life quality. Thus, highways associations and communities had to take some steps to reduce these effects and care about environmental and cultural issues with the traditional commitment to safety and mobility, and that is known as context sensitive design. The aim of this thesis is to use the concepts of context sensitive design to reduce the negative environmental impacts of provincial road Galliera, which connects via Colombo in city of Bologna to provincial road 3 in Argelato city. Some solutions were proposed in this thesis to reduce traffic noise, fragmentation, fauna mortality and to improve the aesthetics of the road.

Context-sensitive design in transportation infrastructure: relating tire/pavement noise with wearing course characteristics

A design can be defined as context-sensitive when it achieves effective technical and functional transportation solutions, while preserving and enhancing natural environments and minimizing impacts on local communities. Traffic noise is one of the most critical environmental impacts of transportation infrastructure and it affects both humans and ecosystems. Tire/pavement noise is caused by a set of interactions at the contact patch and it is the predominant source of road noise at the regular traffic speeds. Wearing course characteristics affect tire/pavement noise through various mechanisms. Furthermore, acoustic performance of road pavements varies over time and it is influenced by both aging and temperature. Three experimentations have been carried out to evaluate wearing course characteristics effects on tire/pavement noise. The first study involves the evaluation of skid resistance, surface texture and tire/pavement noise of an innovative application of multipurpose cold-laid microsurfacing. The second one involves the evaluation of the surface and acoustic characteristics of the different pavement sections of the test track of the Centre for Pavement and Transportation Technology (CPATT) at the University of Waterloo. In the third study, a set of highway sections have been selected in Southern Ontario with various types of pavements. Noise measurements were carried out by means of the Statistical Pass-by (SPB) method in the first case study, whereas in the second and in the third one, Close-proximity (CPX) and the On-Board Sound Intensity (OBSI) methods have been performed in parallel. Test results have contributed to understand the effects of pavement materials, temperature and aging on tire/pavement noise. Negligible correlation was found between surface texture and roughness with noise. As a general trend, aged and stiffer materials have shown to provide higher noise levels than newer and less stiff ones. Noise levels were also observed to be higher with temperature increase.