Graphs and Grammars for Histology: An Introduction
Prewitt, Judith M. S.
1979-01-01
The invention of the microscope disclosed a whole new world, that of the hitherto invisibly small. Histologic evidence as revealed by the microscope has become a cornerstone of medical diagnosis, and efforts are now being made to lay foundations so that the medical visual information processing burden can be alleviated significantly by cost-effective automation. This paper lays image processing foundations by presenting a graph-theoretic and syntactic model for the analysis of histologic patterns, and presents results to date.
An approach to multiscale modelling with graph grammars
Ong, Yongzhi; Streit, Katarína; Henke, Michael; Kurth, Winfried
2014-01-01
Background and Aims Functional–structural plant models (FSPMs) simulate biological processes at different spatial scales. Methods exist for multiscale data representation and modification, but the advantages of using multiple scales in the dynamic aspects of FSPMs remain unclear. Results from multiscale models in various other areas of science that share fundamental modelling issues with FSPMs suggest that potential advantages do exist, and this study therefore aims to introduce an approach to multiscale modelling in FSPMs. Methods A three-part graph data structure and grammar is revisited, and presented with a conceptual framework for multiscale modelling. The framework is used for identifying roles, categorizing and describing scale-to-scale interactions, thus allowing alternative approaches to model development as opposed to correlation-based modelling at a single scale. Reverse information flow (from macro- to micro-scale) is catered for in the framework. The methods are implemented within the programming language XL. Key Results Three example models are implemented using the proposed multiscale graph model and framework. The first illustrates the fundamental usage of the graph data structure and grammar, the second uses probabilistic modelling for organs at the fine scale in order to derive crown growth, and the third combines multiscale plant topology with ozone trends and metabolic network simulations in order to model juvenile beech stands under exposure to a toxic trace gas. Conclusions The graph data structure supports data representation and grammar operations at multiple scales. The results demonstrate that multiscale modelling is a viable method in FSPM and an alternative to correlation-based modelling. Advantages and disadvantages of multiscale modelling are illustrated by comparisons with single-scale implementations, leading to motivations for further research in sensitivity analysis and run-time efficiency for these models. PMID:25134929
Conceptual graph grammar--a simple formalism for sublanguage.
Johnson, S B
1998-11-01
There are a wide variety of computer applications that deal with various aspects of medical language: concept representation, controlled vocabulary, natural language processing, and information retrieval. While technical and theoretical methods appear to differ, all approaches investigate different aspects of the same phenomenon: medical sublanguage. This paper surveys the properties of medical sublanguage from a formal perspective, based on detailed analyses cited in the literature. A review of several computer systems based on sublanguage approaches shows some of the difficulties in addressing the interaction between the syntactic and semantic aspects of sublanguage. A formalism called Conceptual Graph Grammar is presented that attempts to combine both syntax and semantics into a single notation by extending standard Conceptual Graph notation. Examples from the domain of pathology diagnoses are provided to illustrate the use of this formalism in medical language analysis. The strengths and weaknesses of the approach are then considered. Conceptual Graph Grammar is an attempt to synthesize the common properties of different approaches to sublanguage into a single formalism, and to begin to define a common foundation for language-related research in medical informatics.
Quantum graphs and random-matrix theory
NASA Astrophysics Data System (ADS)
Pluhař, Z.; Weidenmüller, H. A.
2015-07-01
For simple connected graphs with incommensurate bond lengths and with unitary symmetry we prove the Bohigas-Giannoni-Schmit (BGS) conjecture in its most general form. Using supersymmetry and taking the limit of infinite graph size, we show that the generating function for every (P,Q) correlation function for both closed and open graphs coincides with the corresponding expression of random-matrix theory. We show that the classical Perron-Frobenius operator is bistochastic and possesses a single eigenvalue +1. In the quantum case that implies the existence of a zero (or massless) mode of the effective action. That mode causes universal fluctuation properties. Avoiding the saddle-point approximation we show that for graphs that are classically mixing (i.e. for which the spectrum of the classical Perron-Frobenius operator possesses a finite gap) and that do not carry a special class of bound states, the zero mode dominates in the limit of infinite graph size.
Low-Rank Matrix Factorization With Adaptive Graph Regularizer.
Lu, Gui-Fu; Wang, Yong; Zou, Jian
2016-05-01
In this paper, we present a novel low-rank matrix factorization algorithm with adaptive graph regularizer (LMFAGR). We extend the recently proposed low-rank matrix with manifold regularization (MMF) method with an adaptive regularizer. Different from MMF, which constructs an affinity graph in advance, LMFAGR can simultaneously seek graph weight matrix and low-dimensional representations of data. That is, graph construction and low-rank matrix factorization are incorporated into a unified framework, which results in an automatically updated graph rather than a predefined one. The experimental results on some data sets demonstrate that the proposed algorithm outperforms the state-of-the-art low-rank matrix factorization methods.
Research on the Top-Down Parsing Method for Context-Sensitive Graph Grammars.
Wang, Yi; Zeng, XiaoQin; Ding, Han
2015-01-01
The parsing problem is one of the key problems of graph grammars. The typical parsing algorithm uses the bottom-up method. The time-complexity of this method is high, and it is difficult to apply. In order to reduce the time-complexity, this paper uses the top-down method for parsing. This method avoids the subgraph isomorphism judgment and selects the productions specifically, so that the time-complexity is greatly reduced.
Hermitian-Randić matrix and Hermitian-Randić energy of mixed graphs.
Lu, Yong; Wang, Ligong; Zhou, Qiannan
2017-01-01
Let M be a mixed graph and [Formula: see text] be its Hermitian-adjacency matrix. If we add a Randić weight to every edge and arc in M, then we can get a new weighted Hermitian-adjacency matrix. What are the properties of this new matrix? Motivated by this, we define the Hermitian-Randić matrix [Formula: see text] of a mixed graph M, where [Formula: see text] ([Formula: see text]) if [Formula: see text] is an arc of M, [Formula: see text] if [Formula: see text] is an undirected edge of M, and [Formula: see text] otherwise. In this paper, firstly, we compute the characteristic polynomial of the Hermitian-Randić matrix of a mixed graph. Furthermore, we give bounds on the Hermitian-Randić energy of a general mixed graph. Finally, we give some results about the Hermitian-Randić energy of mixed trees.
Automated Program Recognition by Graph Parsing
1992-07-01
programs are represented as attributed dataflow graphs and a library of clichis is encoded as an attributed graph grammar . Graph parsing is used to...recognition. Second, we investigate the expressiveness of our graph grammar formalism for capturing pro- gramming cliches. Third, we empirically and...library of cliches is encoded as an attributed graph grammar . Graph parsing is used to recognize clich6s in the code. We demonstrate that this graph
Local quality functions for graph clustering with non-negative matrix factorization
NASA Astrophysics Data System (ADS)
van Laarhoven, Twan; Marchiori, Elena
2014-12-01
Many graph clustering quality functions suffer from a resolution limit, namely the inability to find small clusters in large graphs. So-called resolution-limit-free quality functions do not have this limit. This property was previously introduced for hard clustering, that is, graph partitioning. We investigate the resolution-limit-free property in the context of non-negative matrix factorization (NMF) for hard and soft graph clustering. To use NMF in the hard clustering setting, a common approach is to assign each node to its highest membership cluster. We show that in this case symmetric NMF is not resolution-limit free, but that it becomes so when hardness constraints are used as part of the optimization. The resulting function is strongly linked to the constant Potts model. In soft clustering, nodes can belong to more than one cluster, with varying degrees of membership. In this setting resolution-limit free turns out to be too strong a property. Therefore we introduce locality, which roughly states that changing one part of the graph does not affect the clustering of other parts of the graph. We argue that this is a desirable property, provide conditions under which NMF quality functions are local, and propose a novel class of local probabilistic NMF quality functions for soft graph clustering.
Kuhlemann, Verena; Vassilevski, Panayot S.
2013-10-28
Matrix-vector multiplication is the key operation in any Krylov-subspace iteration method. We are interested in Krylov methods applied to problems associated with the graph Laplacian arising from large scale-free graphs. Furthermore, computations with graphs of this type on parallel distributed-memory computers are challenging. This is due to the fact that scale-free graphs have a degree distribution that follows a power law, and currently available graph partitioners are not efficient for such an irregular degree distribution. The lack of a good partitioning leads to excessive interprocessor communication requirements during every matrix-vector product. Here, we present an approach to alleviate this problem based on embedding the original irregular graph into a more regular one by disaggregating (splitting up) vertices in the original graph. The matrix-vector operations for the original graph are performed via a factored triple matrix-vector product involving the embedding graph. And even though the latter graph is larger, we are able to decrease the communication requirements considerably and improve the performance of the matrix-vector product.
Li, Qu; Yao, Min; Yang, Jianhua; Xu, Ning
2014-01-01
Online friend recommendation is a fast developing topic in web mining. In this paper, we used SVD matrix factorization to model user and item feature vector and used stochastic gradient descent to amend parameter and improve accuracy. To tackle cold start problem and data sparsity, we used KNN model to influence user feature vector. At the same time, we used graph theory to partition communities with fairly low time and space complexity. What is more, matrix factorization can combine online and offline recommendation. Experiments showed that the hybrid recommendation algorithm is able to recommend online friends with good accuracy.
Exact scattering matrix of graphs in magnetic field and quantum noise
Caudrelier, Vincent; Mintchev, Mihail; Ragoucy, Eric
2014-08-15
We consider arbitrary quantum wire networks modelled by finite, noncompact, connected quantum graphs in the presence of an external magnetic field. We find a general formula for the total scattering matrix of the network in terms of its local scattering properties and its metric structure. This is applied to a quantum ring with N external edges. Connecting the external edges of the ring to heat reservoirs, we study the quantum transport on the graph in ambient magnetic field. We consider two types of dynamics on the ring: the free Schrödinger and the free massless Dirac equations. For each case, a detailed study of the thermal noise is performed analytically. Interestingly enough, in presence of a magnetic field, the standard linear Johnson-Nyquist law for the low temperature behaviour of the thermal noise becomes nonlinear. The precise regime of validity of this effect is discussed and a typical signature of the underlying dynamics is observed.
Sanfilippo, Antonio P.
2005-12-27
Graph theory is a branch of discrete combinatorial mathematics that studies the properties of graphs. The theory was pioneered by the Swiss mathematician Leonhard Euler in the 18th century, commenced its formal development during the second half of the 19th century, and has witnessed substantial growth during the last seventy years, with applications in areas as diverse as engineering, computer science, physics, sociology, chemistry and biology. Graph theory has also had a strong impact in computational linguistics by providing the foundations for the theory of features structures that has emerged as one of the most widely used frameworks for the representation of grammar formalisms.
ERIC Educational Resources Information Center
Crawford, William J.
2013-01-01
Grammar is a component in all language skills: reading, writing, speaking, and listening. Teachers need to know rules of grammar (teacher knowledge) as well as techniques that help students use grammar effectively and effortlessly (teaching knowledge). Using reflective practice to help teachers become comfortable with teaching grammar, this…
A matrix product algorithm for stochastic dynamics on locally tree-like graphs
NASA Astrophysics Data System (ADS)
Barthel, Thomas; de Bacco, Caterina; Franz, Silvio
In this talk, I describe a novel algorithm for the efficient simulation of generic stochastic dynamics of classical degrees of freedom defined on the vertices of locally tree-like graphs. Such models correspond for example to spin-glass systems, Boolean networks, neural networks, or other technological, biological, and social networks. Building upon the cavity method and ideas from quantum many-body theory, the algorithm is based on a matrix product approximation of the so-called edge messages - conditional probabilities of vertex variable trajectories. The matrix product edge messages (MPEM) are constructed recursively. Computation costs and accuracy can be tuned by controlling the matrix dimensions of the MPEM in truncations. In contrast to Monte Carlo simulations, the approach has a better error scaling and works for both, single instances as well as the thermodynamic limit. Due to the absence of cancellation effects, observables with small expectation values can be evaluated accurately, allowing for the study of decay processes and temporal correlations with unprecedented accuracy. The method is demonstrated for the prototypical non-equilibrium Glauber dynamics of an Ising spin system. Reference: arXiv:1508.03295.
ERIC Educational Resources Information Center
Adams, Karen
2015-01-01
In this article Karen Adams demonstrates how to incorporate group grammar techniques into a classroom activity. In the activity, students practice using the target grammar to do something they naturally enjoy: learning about each other.
Hul, Oleh; Seba, Petr; Sirko, Leszek
2009-06-01
Parameter-dependent statistical properties of spectra of totally connected irregular quantum graphs with Neumann boundary conditions are studied. The autocorrelation functions of level velocities c(x) and c[over ](omega,x) as well as the distributions of level curvatures and avoided crossing gaps are calculated. The numerical results are compared with the predictions of random matrix theory for Gaussian orthogonal ensemble (GOE) and for coupled GOE matrices. The application of coupled GOE matrices was justified by studying localization phenomena in graphs' wave functions Psi(x) using the inverse participation ratio and the amplitude distribution P(Psi(x)) .
Community detection enhancement using non-negative matrix factorization with graph regularization
NASA Astrophysics Data System (ADS)
Liu, Xiao; Wei, Yi-Ming; Wang, Jian; Wang, Wen-Jun; He, Dong-Xiao; Song, Zhan-Jie
2016-06-01
Community detection is a meaningful task in the analysis of complex networks, which has received great concern in various domains. A plethora of exhaustive studies has made great effort and proposed many methods on community detection. Particularly, a kind of attractive one is the two-step method which first makes a preprocessing for the network and then identifies its communities. However, not all types of methods can achieve satisfactory results by using such preprocessing strategy, such as the non-negative matrix factorization (NMF) methods. In this paper, rather than using the above two-step method as most works did, we propose a graph regularized-based model to improve, specialized, the NMF-based methods for the detection of communities, namely NMFGR. In NMFGR, we introduce the similarity metric which contains both the global and local information of networks, to reflect the relationships between two nodes, so as to improve the accuracy of community detection. Experimental results on both artificial and real-world networks demonstrate the superior performance of NMFGR to some competing methods.
ERIC Educational Resources Information Center
Lovegren, Jesse Stuart James
2013-01-01
This dissertation is an attempt to state what is known at present about the grammar of Mungbam (ISO 693-3 [mij]). Mungbam is a Niger-Congo language spoken in the Northwest Region of Cameroon. The dissertation is a descriptive grammar, covering the phonetics, phonology morphology and syntax of the language. Source data are texts and elicited data…
ERIC Educational Resources Information Center
Wood, Mary McGee; Hudson, Richard, Ed.
Written as an objective critical assessment, this book is the first linguistic theory guide to categorial grammars. Categorial grammars offer a radical alternative to the phrase-structure paradigm, with roots in the philosophy of language, logic, and algebra. Their historical evolution is outlined and their formal basis is discussed, beginning…
NASA Astrophysics Data System (ADS)
Malyshev, V. A.
1998-04-01
Contents § 1. Definitions1.1. Grammars1.2. Random grammars and L-systems1.3. Semigroup representations § 2. Infinite string dynamics2.1. Cluster expansion2.2. Cluster dynamics2.3. Local observer § 3. Large time behaviour: small perturbations3.1. Invariant measures3.2. Classification § 4. Large time behaviour: context free case4.1. Invariant measures for grammars4.2. L-systems4.3. Fractal correlation functions4.4. Measures on languages Bibliography
Graphs, matrices, and the GraphBLAS: Seven good reasons
Kepner, Jeremy; Bader, David; Buluç, Aydın; ...
2015-01-01
The analysis of graphs has become increasingly important to a wide range of applications. Graph analysis presents a number of unique challenges in the areas of (1) software complexity, (2) data complexity, (3) security, (4) mathematical complexity, (5) theoretical analysis, (6) serial performance, and (7) parallel performance. Implementing graph algorithms using matrix-based approaches provides a number of promising solutions to these challenges. The GraphBLAS standard (istcbigdata.org/GraphBlas) is being developed to bring the potential of matrix based graph algorithms to the broadest possible audience. The GraphBLAS mathematically defines a core set of matrix-based graph operations that can be used to implementmore » a wide class of graph algorithms in a wide range of programming environments. This paper provides an introduction to the GraphBLAS and describes how the GraphBLAS can be used to address many of the challenges associated with analysis of graphs.« less
Graphs, matrices, and the GraphBLAS: Seven good reasons
Kepner, Jeremy; Bader, David; Buluç, Aydın; Gilbert, John; Mattson, Timothy; Meyerhenke, Henning
2015-01-01
The analysis of graphs has become increasingly important to a wide range of applications. Graph analysis presents a number of unique challenges in the areas of (1) software complexity, (2) data complexity, (3) security, (4) mathematical complexity, (5) theoretical analysis, (6) serial performance, and (7) parallel performance. Implementing graph algorithms using matrix-based approaches provides a number of promising solutions to these challenges. The GraphBLAS standard (istcbigdata.org/GraphBlas) is being developed to bring the potential of matrix based graph algorithms to the broadest possible audience. The GraphBLAS mathematically defines a core set of matrix-based graph operations that can be used to implement a wide class of graph algorithms in a wide range of programming environments. This paper provides an introduction to the GraphBLAS and describes how the GraphBLAS can be used to address many of the challenges associated with analysis of graphs.
ERIC Educational Resources Information Center
Sipe, Rebecca Bowers
2006-01-01
As a new faculty member, the author was invited by colleagues to help protect a resource they believed was essential to their instructional program. The importance of teaching grammar in a didactic fashion as a precursor to student writing constituted an unchallenged belief in the department. Faculty members were committed to the notion that…
ERIC Educational Resources Information Center
Berry, Roger
2015-01-01
This paper looks at the continued survival of "myths" about English grammar, for example, the statement that in negative and interrogative sentences "any" should be used instead of "some". It is based on a survey of 195 Hong Kong students majoring in English, in five different cohorts, which found that such myths are…
Zhang, Qin; Dong, Chunling; Cui, Yan; Yang, Zhihui
2014-04-01
Graphical models for probabilistic reasoning are now in widespread use. Many approaches have been developed such as Bayesian network. A newly developed approach named as dynamic uncertain causality graph (DUCG) is initially presented in a previous paper, in which only the inference algorithm in terms of individual events and probabilities is addressed. In this paper, we first explain the statistic basis of DUCG. Then, we extend the algorithm to the form of matrices of events and probabilities. It is revealed that the representation of DUCG can be incomplete and the exact probabilistic inference may still be made. A real application of DUCG for fault diagnoses of a generator system of a nuclear power plant is demonstrated, which involves > 600 variables. Most inferences take < 1 s with a laptop computer. The causal logic between inference result and observations is graphically displayed to users so that they know not only the result, but also why the result obtained.
Montague Grammar and Transformational Grammar
ERIC Educational Resources Information Center
Partee, Barbara
1975-01-01
Describes and partially presents a theory of grammar combining the most essential features of Montague's theory of syntax and semantics and the transformational approach to syntax. Appendices include examples of truth definitions, derivations according to Montague's theory and illustrations of types of intentional logic. A list of references…
ERIC Educational Resources Information Center
Lightfoot, David
1995-01-01
This paper discusses the biological and social views of grammar with reference to recent research on grammar and language acquisition, arguing that grammars are individual constructs existing in the minds of individual speakers. Contains 24 references. (MDM)
Constraining Multiple Grammars
ERIC Educational Resources Information Center
Hopp, Holger
2014-01-01
This article offers the author's commentary on the Multiple Grammars (MG) language acquisition theory proposed by Luiz Amaral and Tom Roeper in the present issue. Multiple Grammars advances the claim that optionality is a constitutive characteristic of any one grammar, with interlanguage grammars being perhaps the clearest examples of a…
Intrinsic graph structure estimation using graph Laplacian.
Noda, Atsushi; Hino, Hideitsu; Tatsuno, Masami; Akaho, Shotaro; Murata, Noboru
2014-07-01
A graph is a mathematical representation of a set of variables where some pairs of the variables are connected by edges. Common examples of graphs are railroads, the Internet, and neural networks. It is both theoretically and practically important to estimate the intensity of direct connections between variables. In this study, a problem of estimating the intrinsic graph structure from observed data is considered. The observed data in this study are a matrix with elements representing dependency between nodes in the graph. The dependency represents more than direct connections because it includes influences of various paths. For example, each element of the observed matrix represents a co-occurrence of events at two nodes or a correlation of variables corresponding to two nodes. In this setting, spurious correlations make the estimation of direct connection difficult. To alleviate this difficulty, a digraph Laplacian is used for characterizing a graph. A generative model of this observed matrix is proposed, and a parameter estimation algorithm for the model is also introduced. The notable advantage of the proposed method is its ability to deal with directed graphs, while conventional graph structure estimation methods such as covariance selections are applicable only to undirected graphs. The algorithm is experimentally shown to be able to identify the intrinsic graph structure.
Katan, Pesia; Kahta, Shani; Sasson, Ayelet; Schiff, Rachel
2016-10-19
Graph complexity as measured by topological entropy has been previously shown to affect performance on artificial grammar learning tasks among typically developing children. The aim of this study was to examine the effect of graph complexity on implicit sequential learning among children with developmental dyslexia. Our goal was to determine whether children's performance depends on the complexity level of the grammar system learned. We conducted two artificial grammar learning experiments that compared performance of children with developmental dyslexia with that of age- and reading level-matched controls. Experiment 1 was a high topological entropy artificial grammar learning task that aimed to establish implicit learning phenomena in children with developmental dyslexia using previously published experimental conditions. Experiment 2 is a lower topological entropy variant of that task. Results indicated that given a high topological entropy grammar system, children with developmental dyslexia who were similar to the reading age-matched control group had substantial difficulty in performing the task as compared to typically developing children, who exhibited intact implicit learning of the grammar. On the other hand, when tested on a lower topological entropy grammar system, all groups performed above chance level, indicating that children with developmental dyslexia were able to identify rules from a given grammar system. The results reinforced the significance of graph complexity when experimenting with artificial grammar learning tasks, particularly with dyslexic participants.
Charniak, E.
1996-12-31
By a {open_quotes}tree-bank grammar{close_quotes} we mean a context-free grammar created by reading the production rules directly from hand-parsed sentences in a tree bank. Common wisdom has it that such grammars do not perform well, though we know of no published data on the issue. The primary purpose of this paper is to show that the common wisdom is wrong. In particular, we present results on a tree-bank grammar based on the Penn Wall Street Journal tree bank. To the best of our knowledge, this grammar outperforms all other non-word-based statistical parsers/grammars on this corpus. That is, it outperforms parsers that consider the input as a string of tags and ignore the actual words of the corpus.
Completeness and regularity of generalized fuzzy graphs.
Samanta, Sovan; Sarkar, Biswajit; Shin, Dongmin; Pal, Madhumangal
2016-01-01
Fuzzy graphs are the backbone of many real systems like networks, image, scheduling, etc. But, due to some restriction on edges, fuzzy graphs are limited to represent for some systems. Generalized fuzzy graphs are appropriate to avoid such restrictions. In this study generalized fuzzy graphs are introduced. In this study, matrix representation of generalized fuzzy graphs is described. Completeness and regularity are two important parameters of graph theory. Here, regular and complete generalized fuzzy graphs are introduced. Some properties of them are discussed. After that, effective regular graphs are exemplified.
ERIC Educational Resources Information Center
McCracken, Chelsea Leigh
2012-01-01
This dissertation is a description of the grammar of Belep [yly], an Austronesian language variety spoken by about 1600 people in and around the Belep Isles in New Caledonia. The grammar begins with a summary of the cultural and linguistic background of Belep speakers, followed by chapters on Belep phonology and phonetics, morphology and word…
ERIC Educational Resources Information Center
Bryant, William H.
1984-01-01
Focuses on several myths and fallacies prevalent in the field of French grammar. The importance of keeping up-to-date with language and grammatical usage is stressed, since the rules of language do change. Thus, the validity of the linguistic content of French grammar books must be questioned, so that any outmoded or invalid concepts can be…
Gramatica generadora (Generative Grammar)
ERIC Educational Resources Information Center
Cruset, Jose
1975-01-01
Discusses the difficulty of describing the linguistic approach to the study of language to a non-linguist. Points out certain differences between traditional grammar, structural analysis and contemporary language analysis and gives a short description of the notion of generative grammar. (Text is in Spanish.) (TL)
Towards More Painless Grammar.
ERIC Educational Resources Information Center
Hoover, Regina M.
Teaching grammar to freshman composition students can be accomplished without turning the class into a remedial course or expending an undue amount of either student or teacher energy. Before grammar can have meaning for students, however, writing itself must become important to them. The teaching of the mechanics of language, therefore, should…
ERIC Educational Resources Information Center
Zepeda, Ofelia
A Papago grammar, intented to help Papago and other junior high, high school and college students learn and appreciate the language and give linguists an overview of the language, contains background information on the language and the book, two grammar units, a unit of five conversations in Papago, and a section of supplementary material. Text…
Grammar Instruction and Technology
ERIC Educational Resources Information Center
Lacina, Jan
2005-01-01
Much of the research literature from the past 25 years has supported the importance of teaching grammar in the context of writing instruction (Calkins, 1980; DiStefano & Killion, 1984; Weaver, 1996,1998). Unlike other content areas, practice does not make perfect when learning grammar. While isolated drill and practice of grammatical concepts may…
Grammar A and Grammar B: Rhetorical Life and Death.
ERIC Educational Resources Information Center
Guinn, Dorothy Margaret
In the past, writers have chosen stylistic devices within the parameters of the traditional grammar of style, "Grammar A," characterized by analyticity, coherence, and clarity. But many contemporary writers are creating a new grammar of style, "Grammar B," characterized by synchronicity, discontinuity, and ambiguity, which…
Phonology without universal grammar
Archangeli, Diana; Pulleyblank, Douglas
2015-01-01
The question of identifying the properties of language that are specific human linguistic abilities, i.e., Universal Grammar, lies at the center of linguistic research. This paper argues for a largely Emergent Grammar in phonology, taking as the starting point that memory, categorization, attention to frequency, and the creation of symbolic systems are all nonlinguistic characteristics of the human mind. The articulation patterns of American English rhotics illustrate categorization and systems; the distribution of vowels in Bantu vowel harmony uses frequencies of particular sequences to argue against Universal Grammar and in favor of Emergent Grammar; prefix allomorphy in Esimbi illustrates the Emergent symbolic system integrating phonological and morphological generalizations. The Esimbi case has been treated as an example of phonological opacity in a Universal Grammar account; the Emergent analysis resolves the pattern without opacity concerns. PMID:26388791
Phonology without universal grammar.
Archangeli, Diana; Pulleyblank, Douglas
2015-01-01
The question of identifying the properties of language that are specific human linguistic abilities, i.e., Universal Grammar, lies at the center of linguistic research. This paper argues for a largely Emergent Grammar in phonology, taking as the starting point that memory, categorization, attention to frequency, and the creation of symbolic systems are all nonlinguistic characteristics of the human mind. The articulation patterns of American English rhotics illustrate categorization and systems; the distribution of vowels in Bantu vowel harmony uses frequencies of particular sequences to argue against Universal Grammar and in favor of Emergent Grammar; prefix allomorphy in Esimbi illustrates the Emergent symbolic system integrating phonological and morphological generalizations. The Esimbi case has been treated as an example of phonological opacity in a Universal Grammar account; the Emergent analysis resolves the pattern without opacity concerns.
Schulz, Martin; Arnold, Dorian
2007-06-12
GraphLib is a support library used by other tools to create, manipulate, store, and export graphs. It provides a simple interface to specifS arbitrary directed and undirected graphs by adding nodes and edges. Each node and edge can be associated with a set of attributes describing size, color, and shape. Once created, graphs can be manipulated using a set of graph analysis algorithms, including merge, prune, and path coloring operations. GraphLib also has the ability to export graphs into various open formats such as DOT and GML.
La Grammaire: Lectures (Grammar: Readings).
ERIC Educational Resources Information Center
Arrive, Michel; Chevalier, Jean-Claude
A historical perspective of French grammar is developed in this chronologically arranged reader. Part One includes material on French grammar from the 16th to the 19th century: (1) the "Premiere Epoque": 1530-1660, (2) the general grammar of Port-Royal, and (3) the "philosophical grammars" treating syntax, sentence structure, and discourse…
Spectral fluctuations of quantum graphs
Pluhař, Z.; Weidenmüller, H. A.
2014-10-15
We prove the Bohigas-Giannoni-Schmit conjecture in its most general form for completely connected simple graphs with incommensurate bond lengths. We show that for graphs that are classically mixing (i.e., graphs for which the spectrum of the classical Perron-Frobenius operator possesses a finite gap), the generating functions for all (P,Q) correlation functions for both closed and open graphs coincide (in the limit of infinite graph size) with the corresponding expressions of random-matrix theory, both for orthogonal and for unitary symmetry.
Parsing and translation of (attributed) expansive graph languages for scene analysis.
Shi, Q Y; Fu, K S
1983-05-01
In this paper, we suggest a class of (attributed) expansive graph grammars which generate languages contained in a graph family ¿. It turns out that by means of node renumbering using a very effi-cient algorithm, any graph in ¿ can be converted into a standard form, which enables the use of related string representation for that graph to facilitate the syntax analysis. As a consequence, the syntax analysis of (attributed) expansive graph language is very efficient and almost like the parsing of tree languages. Furthermore, a syntax-directed transla-tion can be established for mapping one (attributed) expansive graph language to another. Finally, since many relational graphs for scene analysis can be considered as belonging to these graph languages, the proposed graph grammar model appears to be quite attractive from the application point of view.
Knowing Chinese character grammar.
Myers, James
2016-02-01
Chinese character structure has often been described as representing a kind of grammar, but the notion of character grammar has hardly been explored. Patterns in character element reduplication are particularly grammar-like, displaying discrete combinatoriality, binarity, phonology-like final prominence, and potentially the need for symbolic rules (X→XX). To test knowledge of these patterns, Chinese readers were asked to judge the acceptability of fake characters varying both in grammaticality (obeying or violating reduplication constraints) and in lexicality (of the reduplicative configurations). While lexical knowledge was important (lexicality improved acceptability and grammatical configurations were accepted more quickly when also lexical), grammatical knowledge was important as well, with grammaticality improving acceptability equally for lexical and nonlexical configurations. Acceptability was also higher for more frequent reduplicative elements, suggesting that the reduplicative configurations were decomposed. Chinese characters present an as-yet untapped resource for exploring fundamental questions about the nature of the human capacity for grammar.
Effective Grammar Teaching: Lessons from Confident Grammar Teachers
ERIC Educational Resources Information Center
Petraki, Eleni; Hill, Deborah
2011-01-01
Learning the grammar of a language is an integral part of learning a second or foreign language. Studies on teacher beliefs, teacher language awareness (TLA) and grammar teaching have reported that the majority of English language teachers recognise the importance of teaching grammar (Borg, 2001; Borg & Burns, 2008). At the same time, many…
Graph Coarsening for Path Finding in Cybersecurity Graphs
Hogan, Emilie A.; Johnson, John R.; Halappanavar, Mahantesh
2013-01-01
n the pass-the-hash attack, hackers repeatedly steal password hashes and move through a computer network with the goal of reaching a computer with high level administrative privileges. In this paper we apply graph coarsening in network graphs for the purpose of detecting hackers using this attack or assessing the risk level of the network's current state. We repeatedly take graph minors, which preserve the existence of paths in the graph, and take powers of the adjacency matrix to count the paths. This allows us to detect the existence of paths as well as find paths that have high risk of being used by adversaries.
Closure properties of Watson-Crick grammars
NASA Astrophysics Data System (ADS)
Zulkufli, Nurul Liyana binti Mohamad; Turaev, Sherzod; Tamrin, Mohd Izzuddin Mohd; Azeddine, Messikh
2015-12-01
In this paper, we define Watson-Crick context-free grammars, as an extension of Watson-Crick regular grammars and Watson-Crick linear grammars with context-free grammar rules. We show the relation of Watson-Crick (regular and linear) grammars to the sticker systems, and study some of the important closure properties of the Watson-Crick grammars. We establish that the Watson-Crick regular grammars are closed under almost all of the main closure operations, while the differences between other Watson-Crick grammars with their corresponding Chomsky grammars depend on the computational power of the Watson-Crick grammars which still need to be studied.
The Necessity of Grammar Teaching
ERIC Educational Resources Information Center
Wang, Fengjuan
2010-01-01
Mastering grammar is the foundation in the proficiency of a language. Grammar teaching is also an essential part of language teaching. However, with the communicative approach was introduced into China, many foreign language teachers gradually make little of grammar teaching. In terms of the theory of linguistics, this paper specifically explores…
Teaching Grammar: What Really Works
ERIC Educational Resources Information Center
Benjamin, Amy; Berger, Joan
2010-01-01
In this book, the authors share procedures for teaching grammar effectively and dynamically, in ways that appeal to students and teachers alike. Ideal for teachers just beginning their work in grammar instruction, this book includes day-by-day units and reproducibles to help them embed grammar lessons into writing instruction. Using visuals,…
La gramatica comunicativa (Communicative Grammar).
ERIC Educational Resources Information Center
Zierer, Ernesto
This paper explains the main concepts of communicative grammar and provides a detailed view of how communicative grammar analyses language at various levels. Language is discussed in terms of communication; the central elements in the analysis are those that carry information. Communicative grammar seeks to describe the process of the linguistic…
Grammar and Grammaring: Toward Modes for English Grammar Teaching in China
ERIC Educational Resources Information Center
Nan, Chengyu
2015-01-01
The value of grammar instruction in foreign language learning and teaching has been a focus of debate for quite some time, which has resulted in different views on grammar and grammar teaching as well as different teaching approaches based on different perspectives or in different language learning contexts. To explore some modes for grammar…
Exploring Hill Ciphers with Graphing Calculators.
ERIC Educational Resources Information Center
St. John, Dennis
1998-01-01
Explains how to code and decode messages using Hill ciphers which combine matrix multiplication and modular arithmetic. Discusses how a graphing calculator can facilitate the matrix and modular arithmetic used in the coding and decoding procedures. (ASK)
Grammar Gremlins Haunt Writers.
ERIC Educational Resources Information Center
Phillips, Kay
1999-01-01
Argues that grammar instruction is important and should begin early. Lists rules for using the comma, colon, and semi-colon. Notes 10 tips for top-notch writing. Notes grammatical areas often troublesome to students. Includes a short quiz. (SR)
ERIC Educational Resources Information Center
Bloom, Lois
1971-01-01
Children's early attempts at syntax, previously described in terms of pivot grammar, are discussed in the light of the author's research on the semantic intentions of early two-word sentences. Underlying conceptual relations were identified when such utterances were examined along with context and behavior. (Author/KW)
ERIC Educational Resources Information Center
Nunan, David
1998-01-01
Argues for an alternative to the conventional linear model of language acquisition in the learning of second-language grammar, proposing a more organic approach. The two approaches are contrasted, drawing on research in second-language learning and discourse analysis that supports the organic view. Some pedagogical implications of this approach…
ERIC Educational Resources Information Center
CARDONA, GEORGE
THIS REFERENCE GRAMMAR WAS WRITTEN TO FILL THE NEED FOR AN UP-TO-DATE ANALYSIS OF THE MODERN LANGUAGE SUITABLE FOR LANGUAGE LEARNERS AS WELL AS LINGUISTS. THE AUTHOR LISTS IN THE INTRODUCTION THOSE STUDIES PREVIOUS TO THIS ONE WHICH MAY BE OF INTEREST TO THE READER. INCLUDED IN HIS ANALYSIS OF THE LANGUAGE ARE MAJOR CHAPTERS ON--(1) PHONOLOGY, (2)…
ERIC Educational Resources Information Center
Claremont, Francesca
1993-01-01
This reprint of a lecture published in 1976 examines the uses of history and literary stories for instructing children in grammar, creative dramatics, natural history, and prehistory, as well as literary analysis. Provides a starting point for thinking about the power of literature as an integrating medium in the Montessori elementary classroom.…
ERIC Educational Resources Information Center
Beach, Matthew David
2012-01-01
This dissertation addresses a number of issues about the grammar of Eastern Canadian Inuktitut. Inuktitut is a dialect within the Inuit dialect continuum which is a group of languages/dialects within the Eskimo-Aleut language family. (Eastern Canadian Inuktitut has an ISO 693-3 language code of "ike".) Typologically, it is an ergative…
ERIC Educational Resources Information Center
Truscott, John
2014-01-01
Optionality is a central phenomenon in second language acquisition (SLA), for which any adequate theory must account. Amaral and Roeper (this issue; henceforth A&R) offer an appealing approach to it, using Roeper's Multiple Grammars Theory, which was created with first language in mind but which extends very naturally to SLA. They include…
ERIC Educational Resources Information Center
Arlington County Public Schools, VA. REEP, Arlington Education and Employment Program.
This document provides the Arlington Education and Employment Program's (REEP) favorite techniques for teaching English-as-a-Second-Language (ESL) grammar. The focus, levels, and materials needed are presented for each of the techniques as well as the steps to follow. (Adjunct ERIC Clearinghouse for ESL Literacy Education) (Author/VWL)
ERIC Educational Resources Information Center
Leslau, Wolf
This reference grammar presents a structural description of the orthography, phonology, morphology, and syntax of Amharic, the national language of Ethiopia. The Amharic material in this work, designed to prepare the student for speaking and reading the language, appears in both Amharic script and phonetic transcription. See ED 012 044-5 for the…
ERIC Educational Resources Information Center
Russell, James S.
The grammar which is concerned with meaning (the province of New Semantics), with its foundations in our perceptions of the surrounding world, can be learned in the elementary classroom through storytelling. Understanding of the sentence concept develops by allowing the child to use his language responsively and deliberately to organize the world…
ERIC Educational Resources Information Center
Connery, Keely Flynn
2007-01-01
Graphing predictions is especially important in classes where relationships between variables need to be explored and derived. In this article, the author describes how his students sketch the graphs of their predictions before they begin their investigations on two laboratory activities: Distance Versus Time Cart Race Lab and Resistance; and…
Single-View 3D Scene Reconstruction and Parsing by Attribute Grammar.
Liu, Xiaobai; Zhao, Yibiao; Zhu, Song-Chun
2017-03-29
In this paper, we present an attribute grammar for solving two coupled tasks: i) parsing an 2D image into semantic regions; and ii) recovering the 3D scene structures of all regions. The proposed grammar consists of a set of production rules, each describing a kind of spatial relation between planar surfaces in 3D scenes. These production rules are used to decompose an input image into a hierarchical parse graph representation where each graph node indicates a planar surface or a composite surface. Different from other stochastic image grammars, the proposed grammar augments each graph node with a set of attribute variables to depict scene-level global geometry, e.g. camera focal length, or local geometry, e.g., surface normal, contact lines between surfaces. These geometric attributes impose constraints between a node and its off-springs in the parse graph. Under a probabilistic framework, we develop a Markov Chain Monte Carlo method to construct a parse graph that optimizes the 2D image recognition and 3D scene reconstruction purposes simultaneously. We evaluated our method on both public benchmarks and newly collected datasets. Experiments demonstrate that the proposed method is capable of achieving state-of-the-art scene reconstruction of a single image.
Spectral correlations of individual quantum graphs
Gnutzmann, Sven; Altland, Alexander
2005-11-01
We investigate the spectral properties of chaotic quantum graphs. We demonstrate that the energy-average over the spectrum of individual graphs can be traded for the functional average over a supersymmetric nonlinear {sigma}-model action. This proves that spectral correlations of individual quantum graphs behave according to the predictions of Wigner-Dyson random matrix theory. We explore the stability of the universal random matrix behavior with regard to perturbations, and discuss the crossover between different types of symmetries.
Scenario Graphs and Attack Graphs
2004-04-14
46 6.1 Vulnerability Analysis of a Network . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.2 Sandia Red Team Attack Graph...asymptotic bound. The test machine was a 1Ghz Pentium III with 1GB of RAM, running Red Hat Linux 7.3. Figure 4.1(a) plots running time of the implemen...host scanning tools network information vulnerability Attack Graph network Red
2009-10-01
such as the difference between policy and politics; the first is the sausage , the second is everything that goes into making it. Put differently...grammar cannot cover how to strike deals and make bargains, as these require finesse unique to specific cultures; but it can underscore the...first or second grammar. In the face of imperceptible logic, we will make a choice. In other words, war’s second grammar gives those responsible for
Multibody graph transformations and analysis
2013-01-01
This two-part paper uses graph transformation methods to develop methods for partitioning, aggregating, and constraint embedding for multibody systems. This first part focuses on tree-topology systems and reviews the key notion of spatial kernel operator (SKO) models for such systems. It develops systematic and rigorous techniques for partitioning SKO models in terms of the SKO models of the component subsystems based on the path-induced property of the component subgraphs. It shows that the sparsity structure of key matrix operators and the mass matrix for the multibody system can be described using partitioning transformations. Subsequently, the notions of node contractions and subgraph aggregation and their role in coarsening graphs are discussed. It is shown that the tree property of a graph is preserved after subgraph aggregation if and only if the subgraph satisfies an aggregation condition. These graph theory ideas are used to develop SKO models for the aggregated tree multibody systems. PMID:24288438
1987-05-01
can be represented in FUG notation, as a step toward creating a grammatical analysis program for English . Because FUG has been developed as a... English for text generation started at the Information Sciences Institute of the University of Southern California. It is called the Nigel grammar and...Fawcett is developing a computational systemic grammar of English , implementing his contributions to systemic grammar (cf. Fawcett (1980)). The present
Zhou, Feng; de la Torre, Fernando
2015-11-19
Graph matching (GM) is a fundamental problem in computer science, and it plays a central role to solve correspondence problems in computer vision. GM problems that incorporate pairwise constraints can be formulated as a quadratic assignment problem (QAP). Although widely used, solving the correspondence problem through GM has two main limitations: (1) the QAP is NP-hard and difficult to approximate; (2) GM algorithms do not incorporate geometric constraints between nodes that are natural in computer vision problems. To address aforementioned problems, this paper proposes factorized graph matching (FGM). FGM factorizes the large pairwise affinity matrix into smaller matrices that encode the local structure of each graph and the pairwise affinity between edges. Four are the benefits that follow from this factorization: (1) There is no need to compute the costly (in space and time) pairwise affinity matrix; (2) The factorization allows the use of a path-following optimization algorithm, that leads to improved optimization strategies and matching performance; (3) Given the factorization, it becomes straight-forward to incorporate geometric transformations (rigid and non-rigid) to the GM problem. (4) Using a matrix formulation for the GM problem and the factorization, it is easy to reveal commonalities and differences between different GM methods. The factorization also provides a clean connection with other matching algorithms such as iterative closest point; Experimental results on synthetic and real databases illustrate how FGM outperforms state-of-the-art algorithms for GM. The code is available at http://humansensing.cs.cmu.edu/fgm.
Grammar Dilemma: Teaching Grammar as a Resource for Making Meaning
ERIC Educational Resources Information Center
Liamkina, Olga; Ryshina-Pankova, Marianna
2012-01-01
Adopting a functional perspective that views grammar as a rich resource for making contextualized meanings in a culture- and language-specific way, the article reconsiders the role of explicit grammar instruction in developing communicative abilities of second language learners. It draws on two distinct but complementary research frameworks,…
Blind Identification of Graph Filters
NASA Astrophysics Data System (ADS)
Segarra, Santiago; Mateos, Gonzalo; Marques, Antonio G.; Ribeiro, Alejandro
2017-03-01
Network processes are often represented as signals defined on the vertices of a graph. To untangle the latent structure of such signals, one can view them as outputs of linear graph filters modeling underlying network dynamics. This paper deals with the problem of joint identification of a graph filter and its input signal, thus broadening the scope of classical blind deconvolution of temporal and spatial signals to the less-structured graph domain. Given a graph signal $\\mathbf{y}$ modeled as the output of a graph filter, the goal is to recover the vector of filter coefficients $\\mathbf{h}$, and the input signal $\\mathbf{x}$ which is assumed to be sparse. While $\\mathbf{y}$ is a bilinear function of $\\mathbf{x}$ and $\\mathbf{h}$, the filtered graph signal is also a linear combination of the entries of the lifted rank-one, row-sparse matrix $\\mathbf{x} \\mathbf{h}^T$. The blind graph-filter identification problem can thus be tackled via rank and sparsity minimization subject to linear constraints, an inverse problem amenable to convex relaxations offering provable recovery guarantees under simplifying assumptions. Numerical tests using both synthetic and real-world networks illustrate the merits of the proposed algorithms, as well as the benefits of leveraging multiple signals to aid the blind identification task.
Creative Grammar and Art Education
ERIC Educational Resources Information Center
Cunliffe, Leslie
2011-01-01
The grammar of creative practices is described by George Steiner as the "articulate organisation of perception, reflection and experience, the nerve structure of consciousness when it communicates with itself and with others." Steiner's description of creative grammar is consistent with Lev Vygotsky's comment that "art is the social within us, and…
A Bemba Grammar with Exercises.
ERIC Educational Resources Information Center
Hoch, Ernst
This Bemba grammar begins with an introduction which traces the history of the language, stresses the importance of learning it well and offers hints towards achieving this goal. The grammar itself is divided into three major sections: Part 1, "Phonetics," deals with the Bemba alphabet, tonality, and orthography; Part 2, "Parts of Speech,"…
A Pedagogical Grammar of Tboli.
ERIC Educational Resources Information Center
Forsberg, Vivian M.
1992-01-01
Tboli is a language spoken by people living in southwestern Mindanao, Philippines, in the province of South Cotabato. The pedagogical grammar of Tboli has been written to help non-Tboli interested in learning to speak Tboli. A discussion of spelling and pronunciation includes the alphabet and spelling rules. Other forms of grammar described are…
ERIC Educational Resources Information Center
Morrison, Michelle Elizabeth
2011-01-01
This dissertation is a grammar of Rena (ISO bez), a Bantu language spoken in southwestern Tanzania by approximately 600,000 people. Bena is largely undocumented, and though aspects of Bena grammar have been described, there is no usable, detailed treatment of the Bena language. Therefore the goal of this dissertation is provide the first detailed…
French String Grammar. Final Report.
ERIC Educational Resources Information Center
New York Univ., NY. Linguistic String Project.
This work reports on an initial study of the possibility of providing a suitable framework for the teaching of a foreign language grammar through string analysis, using French as the target language. Analysis of a string word list (word-class sequences) yields an overall view of the grammar. Details are furnished in a set of restrictions which…
Network Analysis with Stochastic Grammars
2015-09-17
forensics analysis of computer network traffic. SCFG is leveraged to provide context to the low-level data collected as evidence and to build behavior ...grammars was developed to compare behavior patterns represented as grammars. Finally, the SCFG capabilities were demonstrated in performing association...Comparison. After determining suitability for computer network traffic analysis, this research examines representing profiles as behavioral patterns and
Adjusting protein graphs based on graph entropy.
Peng, Sheng-Lung; Tsay, Yu-Wei
2014-01-01
Measuring protein structural similarity attempts to establish a relationship of equivalence between polymer structures based on their conformations. In several recent studies, researchers have explored protein-graph remodeling, instead of looking a minimum superimposition for pairwise proteins. When graphs are used to represent structured objects, the problem of measuring object similarity become one of computing the similarity between graphs. Graph theory provides an alternative perspective as well as efficiency. Once a protein graph has been created, its structural stability must be verified. Therefore, a criterion is needed to determine if a protein graph can be used for structural comparison. In this paper, we propose a measurement for protein graph remodeling based on graph entropy. We extend the concept of graph entropy to determine whether a graph is suitable for representing a protein. The experimental results suggest that when applied, graph entropy helps a conformational on protein graph modeling. Furthermore, it indirectly contributes to protein structural comparison if a protein graph is solid.
Test of Graphing and Graph Interpretation Skills.
ERIC Educational Resources Information Center
Hermann, J.
This monograph is a test of graphing and graph interpretation skills which assesses performance on all the skills of graphing which are contained in the AAAS program, Science - A Process Approach. The testing includes construction of bar graphs, interpreting information on graphs, the use of the Cartesian coordinate system, making predictions from…
NASA Astrophysics Data System (ADS)
Beeken, Paul
2014-11-01
Graphing is an essential skill that forms the foundation of any physical science.1 Understanding the relationships between measurements ultimately determines which modeling equations are successful in predicting observations.2 Over the years, science and math teachers have approached teaching this skill with a variety of techniques. For secondary school instruction, the job of graphing skills falls heavily on physics teachers. By virtue of the nature of the topics we cover, it is our mission to develop this skill to the fine art that it is.
Threshold Graph Limits and Random Threshold Graphs
Diaconis, Persi; Holmes, Susan; Janson, Svante
2010-01-01
We study the limit theory of large threshold graphs and apply this to a variety of models for random threshold graphs. The results give a nice set of examples for the emerging theory of graph limits. PMID:20811581
ERIC Educational Resources Information Center
Beeken, Paul
2014-01-01
Graphing is an essential skill that forms the foundation of any physical science. Understanding the relationships between measurements ultimately determines which modeling equations are successful in predicting observations. Over the years, science and math teachers have approached teaching this skill with a variety of techniques. For secondary…
Sukumar, Sreenivas R.; Hong, Seokyong; Lee, Sangkeun; Lim, Seung-Hwan
2016-06-01
GraphBench is a benchmark suite for graph pattern mining and graph analysis systems. The benchmark suite is a significant addition to conducting apples-apples comparison of graph analysis software (databases, in-memory tools, triple stores, etc.)
NASA Astrophysics Data System (ADS)
Warchalowski, Wiktor; Krawczyk, Malgorzata J.
2017-03-01
We found the Lindenmayer systems for line graphs built on selected fractals. We show that the fractal dimension of such obtained graphs in all analysed cases is the same as for their original graphs. Both for the original graphs and for their line graphs we identified classes of nodes which reflect symmetry of the graph.
Painless Grammar: Revising with the Help of a Grammar Checker.
ERIC Educational Resources Information Center
Milone, Michael N., Jr.
1990-01-01
Teaching techniques and the use of grammar checking programs are described. Assignments using these programs are suggested. Four specific packages are reviewed. The importance of the revision process in writing is stressed. (CW)
Inferring Pedigree Graphs from Genetic Distances
NASA Astrophysics Data System (ADS)
Tamura, Takeyuki; Ito, Hiro
In this paper, we study a problem of inferring blood relationships which satisfy a given matrix of genetic distances between all pairs of n nodes. Blood relationships are represented by our proposed graph class, which is called a pedigree graph. A pedigree graph is a directed acyclic graph in which the maximum indegree is at most two. We show that the number of pedigree graphs which satisfy the condition of given genetic distances may be exponential, but they can be represented by one directed acyclic graph with n nodes. Moreover, an O(n3) time algorithm which solves the problem is also given. Although phylogenetic trees and phylogenetic networks are similar data structures to pedigree graphs, it seems that inferring methods for phylogenetic trees and networks cannot be applied to infer pedigree graphs since nodes of phylogenetic trees and networks represent species whereas nodes of pedigree graphs represent individuals. We also show an O(n2) time algorithm which detects a contradiction between a given pedigreee graph and distance matrix of genetic distances.
Universal spectral statistics in quantum graphs.
Gnutzmann, Sven; Altland, Alexander
2004-11-05
We prove that the spectrum of an individual chaotic quantum graph shows universal spectral correlations, as predicted by random-matrix theory. The stability of these correlations with regard to nonuniversal corrections is analyzed in terms of the linear operator governing the classical dynamics on the graph.
CUDA Enabled Graph Subset Examiner
Johnston, Jeremy T.
2016-12-22
Finding Godsil-McKay switching sets in graphs is one way to demonstrate that a specific graph is not determined by its spectrum--the eigenvalues of its adjacency matrix. An important area of active research in pure mathematics is determining which graphs are determined by their spectra, i.e. when the spectrum of the adjacency matrix uniquely determines the underlying graph. We are interested in exploring the spectra of graphs in the Johnson scheme and specifically seek to determine which of these graphs are determined by their spectra. Given a graph G, a Godsil-McKay switching set is an induced subgraph H on 2k vertices with the following properties: I) H is regular, ii) every vertex in G/H is adjacent to either 0, k, or 2k vertices of H, and iii) at least one vertex in G/H is adjacent to k vertices in H. The software package examines each subset of a user specified size to determine whether or not it satisfies those 3 conditions. The software makes use of the massive parallel processing power of CUDA enabled GPUs. It also exploits the vertex transitivity of graphs in the Johnson scheme by reasoning that if G has a Godsil-McKay switching set, then it has a switching set which includes vertex 1. While the code (in its current state) is tuned to this specific problem, the method of examining each induced subgraph of G can be easily re-written to check for any user specified conditions on the subgraphs and can therefore be used much more broadly.
Generalized graph states based on Hadamard matrices
Cui, Shawn X.; Yu, Nengkun; Zeng, Bei
2015-07-15
Graph states are widely used in quantum information theory, including entanglement theory, quantum error correction, and one-way quantum computing. Graph states have a nice structure related to a certain graph, which is given by either a stabilizer group or an encoding circuit, both can be directly given by the graph. To generalize graph states, whose stabilizer groups are abelian subgroups of the Pauli group, one approach taken is to study non-abelian stabilizers. In this work, we propose to generalize graph states based on the encoding circuit, which is completely determined by the graph and a Hadamard matrix. We study the entanglement structures of these generalized graph states and show that they are all maximally mixed locally. We also explore the relationship between the equivalence of Hadamard matrices and local equivalence of the corresponding generalized graph states. This leads to a natural generalization of the Pauli (X, Z) pairs, which characterizes the local symmetries of these generalized graph states. Our approach is also naturally generalized to construct graph quantum codes which are beyond stabilizer codes.
Fibonacci Identities, Matrices, and Graphs
ERIC Educational Resources Information Center
Huang, Danrun
2005-01-01
General strategies used to help discover, prove, and generalize identities for Fibonacci numbers are described along with some properties about the determinants of square matrices. A matrix proof for identity (2) that has received immense attention from many branches of mathematics, like linear algebra, dynamical systems, graph theory and others…
Deterministic dense coding and faithful teleportation with multipartite graph states
Huang, C.-Y.; Yu, I-C.; Lin, F.-L.; Hsu, L.-Y.
2009-05-15
We propose schemes to perform the deterministic dense coding and faithful teleportation with multipartite graph states. We also find the sufficient and necessary condition of a viable graph state for the proposed schemes. That is, for the associated graph, the reduced adjacency matrix of the Tanner-type subgraph between senders and receivers should be invertible.
Pattern vectors from algebraic graph theory.
Wilson, Richard C; Hancock, Edwin R; Luo, Bin
2005-07-01
Graph structures have proven computationally cumbersome for pattern analysis. The reason for this is that, before graphs can be converted to pattern vectors, correspondences must be established between the nodes of structures which are potentially of different size. To overcome this problem, in this paper, we turn to the spectral decomposition of the Laplacian matrix. We show how the elements of the spectral matrix for the Laplacian can be used to construct symmetric polynomials that are permutation invariants. The coefficients of these polynomials can be used as graph features which can be encoded in a vectorial manner. We extend this representation to graphs in which there are unary attributes on the nodes and binary attributes on the edges by using the spectral decomposition of a Hermitian property matrix that can be viewed as a complex analogue of the Laplacian. To embed the graphs in a pattern space, we explore whether the vectors of invariants can be embedded in a low-dimensional space using a number of alternative strategies, including principal components analysis (PCA), multidimensional scaling (MDS), and locality preserving projection (LPP). Experimentally, we demonstrate that the embeddings result in well-defined graph clusters. Our experiments with the spectral representation involve both synthetic and real-world data. The experiments with synthetic data demonstrate that the distances between spectral feature vectors can be used to discriminate between graphs on the basis of their structure. The real-world experiments show that the method can be used to locate clusters of graphs.
Tight Lower Bound for Percolation Threshold on an Infinite Graph
NASA Astrophysics Data System (ADS)
Hamilton, Kathleen E.; Pryadko, Leonid P.
2014-11-01
We construct a tight lower bound for the site percolation threshold on an infinite graph, which becomes exact for an infinite tree. The bound is given by the inverse of the maximal eigenvalue of the Hashimoto matrix used to count nonbacktracking walks on the original graph. Our bound always exceeds the inverse spectral radius of the graph's adjacency matrix, and it is also generally tighter than the existing bound in terms of the maximum degree. We give a constructive proof for existence of such an eigenvalue in the case of a connected infinite quasitransitive graph, a graph-theoretic analog of a translationally invariant system.
Replica methods for loopy sparse random graphs
NASA Astrophysics Data System (ADS)
Coolen, ACC
2016-03-01
I report on the development of a novel statistical mechanical formalism for the analysis of random graphs with many short loops, and processes on such graphs. The graphs are defined via maximum entropy ensembles, in which both the degrees (via hard constraints) and the adjacency matrix spectrum (via a soft constraint) are prescribed. The sum over graphs can be done analytically, using a replica formalism with complex replica dimensions. All known results for tree-like graphs are recovered in a suitable limit. For loopy graphs, the emerging theory has an appealing and intuitive structure, suggests how message passing algorithms should be adapted, and what is the structure of theories describing spin systems on loopy architectures. However, the formalism is still largely untested, and may require further adjustment and refinement. This paper is dedicated to the memory of our colleague and friend Jun-Ichi Inoue, with whom the author has had the great pleasure and privilege of collaborating.
Dynamic graph system for a semantic database
Mizell, David
2015-01-27
A method and system in a computer system for dynamically providing a graphical representation of a data store of entries via a matrix interface is disclosed. A dynamic graph system provides a matrix interface that exposes to an application program a graphical representation of data stored in a data store such as a semantic database storing triples. To the application program, the matrix interface represents the graph as a sparse adjacency matrix that is stored in compressed form. Each entry of the data store is considered to represent a link between nodes of the graph. Each entry has a first field and a second field identifying the nodes connected by the link and a third field with a value for the link that connects the identified nodes. The first, second, and third fields represent the rows, column, and elements of the adjacency matrix.
Dynamic graph system for a semantic database
Mizell, David
2016-04-12
A method and system in a computer system for dynamically providing a graphical representation of a data store of entries via a matrix interface is disclosed. A dynamic graph system provides a matrix interface that exposes to an application program a graphical representation of data stored in a data store such as a semantic database storing triples. To the application program, the matrix interface represents the graph as a sparse adjacency matrix that is stored in compressed form. Each entry of the data store is considered to represent a link between nodes of the graph. Each entry has a first field and a second field identifying the nodes connected by the link and a third field with a value for the link that connects the identified nodes. The first, second, and third fields represent the rows, column, and elements of the adjacency matrix.
Grammar: Rules and Reasons Working Together.
ERIC Educational Resources Information Center
Larsen-Freeman, Diane
2000-01-01
Suggests that from a pedagogical perspective, there is a cost to associating grammar with rules. Discusses reasons for underlying rules and gives implications for a reason-based approach to teaching grammar. (Author/VWL)
A Learning Algorithm for Multimodal Grammar Inference.
D'Ulizia, A; Ferri, F; Grifoni, P
2011-12-01
The high costs of development and maintenance of multimodal grammars in integrating and understanding input in multimodal interfaces lead to the investigation of novel algorithmic solutions in automating grammar generation and in updating processes. Many algorithms for context-free grammar inference have been developed in the natural language processing literature. An extension of these algorithms toward the inference of multimodal grammars is necessary for multimodal input processing. In this paper, we propose a novel grammar inference mechanism that allows us to learn a multimodal grammar from its positive samples of multimodal sentences. The algorithm first generates the multimodal grammar that is able to parse the positive samples of sentences and, afterward, makes use of two learning operators and the minimum description length metrics in improving the grammar description and in avoiding the over-generalization problem. The experimental results highlight the acceptable performances of the algorithm proposed in this paper since it has a very high probability of parsing valid sentences.
Synchronizability of random rectangular graphs
Estrada, Ernesto Chen, Guanrong
2015-08-15
Random rectangular graphs (RRGs) represent a generalization of the random geometric graphs in which the nodes are embedded into hyperrectangles instead of on hypercubes. The synchronizability of RRG model is studied. Both upper and lower bounds of the eigenratio of the network Laplacian matrix are determined analytically. It is proven that as the rectangular network is more elongated, the network becomes harder to synchronize. The synchronization processing behavior of a RRG network of chaotic Lorenz system nodes is numerically investigated, showing complete consistence with the theoretical results.
Multi-Centrality Graph Spectral Decompositions and Their Application to Cyber Intrusion Detection
Chen, Pin-Yu; Choudhury, Sutanay; Hero, Alfred
2016-03-01
Many modern datasets can be represented as graphs and hence spectral decompositions such as graph principal component analysis (PCA) can be useful. Distinct from previous graph decomposition approaches based on subspace projection of a single topological feature, e.g., the centered graph adjacency matrix (graph Laplacian), we propose spectral decomposition approaches to graph PCA and graph dictionary learning that integrate multiple features, including graph walk statistics, centrality measures and graph distances to reference nodes. In this paper we propose a new PCA method for single graph analysis, called multi-centrality graph PCA (MC-GPCA), and a new dictionary learning method for ensembles of graphs, called multi-centrality graph dictionary learning (MC-GDL), both based on spectral decomposition of multi-centrality matrices. As an application to cyber intrusion detection, MC-GPCA can be an effective indicator of anomalous connectivity pattern and MC-GDL can provide discriminative basis for attack classification.
Nigel: A Systemic Grammar for Text Generation.
1983-02-01
text which meets a prior need is a challenging research task. As part of such research, Nigel, a large programmed grammar of English, has been...generation task has led to creation of a large systemic grammar of English, embedded in a computer program and fitted with a semantic stratum. The grammar...grammar of English. The changes have been evolutionary and largely in the direction of making well-precedented ideas more explicit or detailed. The result
The Philosophical Significance of Universal Grammar
ERIC Educational Resources Information Center
Hinzen, Wolfram
2012-01-01
Throughout its long history, the project of a science of grammar has always been an inherently philosophical one, in which the study of grammar was taken to have special epistemological significance. I ask why 20th and 21st century inquiry into Universal Grammar (UG) has largely lost this dimension, a fact that I argue is partially responsible for…
SPECIFICATION AND UTILIZATION OF A TRANSFORMATIONAL GRAMMAR.
ERIC Educational Resources Information Center
LIEBERMAN, D.; AND OTHERS
SCIENTIFIC REPORT NO. 1 OF THIS PROJECT CONTAINS FOUR PARTS. THE FIRST, BY P. ROSENBAUM AND D. LOCHAK, PRESENTS AND EXPLAINS THE "IBM CORE GRAMMAR OF ENGLISH" AND GIVES A SET OF 66 DERIVATIONS CONSTRUCTED IN TERMS OF THE CORE GRAMMAR. PART II, "DESIGN OF A GRAMMAR TESTER" BY D. LIEBERMAN, SUMMARIZES THE DESIGN CONSIDERATIONS OF…
Teaching the Topography of Gretel Ehrlich's Grammar.
ERIC Educational Resources Information Center
Gessell, Donna A.
When writing, few students have any concept that word placement affects the content of their writing. They seldom rework their papers at the sentence level in order to assure that their grammar reflects and enhances their content. Recognizing the relationship of grammar to meaning, composition researchers are reasserting the place of grammar in…
Integrating Grammar in Adult TESOL Classrooms
ERIC Educational Resources Information Center
Borg, Simon; Burns, Anne
2008-01-01
This paper examines the beliefs and practices about the integration of grammar and skills teaching reported by 176 English language teachers from 18 countries. Teachers completed a questionnaire which elicited beliefs about grammar teaching generally as well as specific beliefs and reported practices about the integration of grammar and skills…
Reframing the English Grammar Schools Debate
ERIC Educational Resources Information Center
Morris, Rebecca; Perry, Thomas
2017-01-01
In October 2015 the Department for Education (DfE) permitted a grammar school in Tonbridge, Kent, to open up an annexe in Sevenoaks, 10 miles away. Amidst claims that the annexe was essentially a new grammar school, the decision reignited an old debate about the value of academically-selective "grammar" schools in England. The intensity…
Grammar Making a Comeback in Composition Teaching.
ERIC Educational Resources Information Center
McCleary, Bill
1995-01-01
This journal article focuses on the return of grammar in composition teaching. After about 2 decades of virtual banishment from the higher reaches of English teaching theory, grammar has returned as a subject of serious discussion. This is the result in part of a new assertiveness by a group of people who never lost interest in grammar as part of…
A Construction Grammar for the Classroom
ERIC Educational Resources Information Center
Holme, Randal
2010-01-01
Construction grammars (Lakoff, Women, fire and dangerous things: What categories reveal about the Mind, University of Chicago Press, 1987; Langacker, Foundations of cognitive grammar: Theoretical pre-requisites, Stanford University Press, 1987; Croft, Radical construction grammar: Syntactic theory in typological perspective, Oxford University…
Drama Grammar: Towards a Performative Postmethod Pedagogy
ERIC Educational Resources Information Center
Even, Susanne
2011-01-01
This article presents the original concept of drama grammar, the synthesis of grammar instruction and drama pedagogy, which integrates both structural and communicative paradigms through a dialectic combination of acting and linguistic analysis. Based on the principles of drama pedagogy, drama grammar makes use of techniques from the performing…
An introduction to chordal graphs and clique trees
Blair, J.R.S.; Peyton, B.W.
1992-11-01
Clique trees and chordal graphs have carved out a niche for themselves in recent work on sparse matrix algorithms, due primarily to research questions associated with advanced computer architectures. This paper is a unified and elementary introduction to the standard characterizations of chordal graphs and clique trees. The pace is leisurely, as detailed proofs of all results are included. We also briefly discuss applications of chordal graphs and clique trees in sparse matrix computations.
Document recognition: an attribute grammar approach
NASA Astrophysics Data System (ADS)
Viswanathan, Mahesh; Green, Edward; Krishnamoorthy, Mukkai
1996-03-01
A formulation of a hierarchical page decomposition technique for technical journal pages using attribute grammars is presented. In this approach, block-grammars are recursively applied until a page is classified into its most significant sub-blocks. While a grammar devised for each block depends on its logical function, it is possible to formulate a generic description for all block grammars using attribute grammars. This attribute grammar formulation forms a generic framework on which this syntactic approach is based, while the attributes themselves are derived from publication-specific knowledge. The attribute extraction process and the formulation itself are covered in this paper. We discuss an application of attribute grammars to a document analysis problem, the extraction of logical, relational information from the image of tables.
Teaching Grammar through Community Issues
ERIC Educational Resources Information Center
Schneider, Jason
2005-01-01
In recent years, ELT researchers have begun exploring how teachers can link their lessons to student communities and student concerns; however, little attention has been given to the potential for explicit grammar focus in the context of such approaches. In this paper, it is proposed that language lessons structured around local issues and…
Theories of Artificial Grammar Learning
ERIC Educational Resources Information Center
Pothos, Emmanuel M.
2007-01-01
Artificial grammar learning (AGL) is one of the most commonly used paradigms for the study of implicit learning and the contrast between rules, similarity, and associative learning. Despite five decades of extensive research, however, a satisfactory theoretical consensus has not been forthcoming. Theoretical accounts of AGL are reviewed, together…
Transformational Generative Grammar: A Bibliography.
ERIC Educational Resources Information Center
Dingwall, William Orr
This is an attempt to compile, from public sources, as complete a bibliography as possible of works related to linguistics and having to do with transformational generative grammar. The arrangement is alphabetical by author and chronological by publication or delivery date of works of a given author. The majority of items are also indexed by…
Prosody and Grammar in Kabardian
ERIC Educational Resources Information Center
Applebaum, Ayla Ayda Bozkurt
2013-01-01
This study provides a systematic phonetic analysis of the basic entities of Kabardian prosodic units above the word and investigates the predictability of prosodic units from grammatical and discourse factors. This dissertation is the first extensive description of Kabardian prosody and grammar based on natural data. This study proposes that…
A REFERENCE GRAMMAR OF BENGALI.
ERIC Educational Resources Information Center
RAY, PUNYA SLOKA; AND OTHERS
A REFERENCE GRAMMAR WAS PRODUCED FOR THE BENGALI LANGUAGE. THE WORK CONTAINS CHAPTERS ON--(1) SOCIAL AND HISTORICAL BACKGROUND, (2) HISTORY OF THE LANGUAGE, (3) SOURCES OF LEXICAL ITEMS, (4) ORTHOGRAPHY, (5) PHONOLOGY, (6) NOUN INFLECTIONS, (7) VERBS, (8) POSTPOSITIONS, (9) ENCLITICS, (10) NUMERALS, (11) NEGATION, (12) FORMATIVE AFFIXES IN…
A Reference Grammar of Kashmiri.
ERIC Educational Resources Information Center
Kachru, Braj B.
This study was developed for two pedagogical purposes--first, to provide a skeleton grammar of the Kashmiri language which could be used by teachers of Kashmiri to develop teaching materials for both Indian and non-Indian learners of Kashmiri; and second, to provide an introductory reference manual of Kashmiri for students of the language. The…
Micmac Teaching Grammar. Preliminary Version.
ERIC Educational Resources Information Center
Delisle, Gilles L.; Metallic, Manny L.
This teaching grammar is designed primarily for university-level students, but may also be used for adult courses, high school classes, and in junior colleges. The text takes the transformational-generative approach to language, in which the notions of system, derivation, and relation are emphasized rather than categorization and classification.…
A Grammar of Inupiaq Morphosyntax
ERIC Educational Resources Information Center
Lanz, Linda A.
2010-01-01
This dissertation is a reference grammar of the Malimiut Coastal dialect of Inupiaq (ISO: ESI, ESK, IPK), an Eskimo-Aleut language of northwestern Alaska spoken by the Inupiat people. It complements existing descriptions of Inupiaq by filling gaps in documentation. With approximately 2000 speakers, mainly above 50 years of age, Inupiaq is…
Kent Sakoda Discusses Pidgin Grammar
ERIC Educational Resources Information Center
Sakoda, Kent; Tamura, Eileen H.
2008-01-01
For a number of years, Kent Sakoda has been teaching at the University of Hawai'i at Manoa in the Department of Second Language Studies. His course, "Pidgin and Creole English in Hawai'i," is popular among students on campus. He has also taught at Hawai'i Pacific University. Because of his expertise on the grammar of Pidgin (Hawai'i…
Readings in Applied Transformational Grammar.
ERIC Educational Resources Information Center
Lester, Mark, Ed.
This volume contains nineteen essays, dealing with various aspects of transformational grammar, by scholars such as Noam Chomsky, Eric H. Lenneberg, and Leon Jakobovits. These essays have been reprinted from sources such as "College English" and "Language Learning" and are intended for the most part for a nontechnical audience. The anthology is…
Transformational Grammar and Cognitive Psycholinguistics.
ERIC Educational Resources Information Center
Lester, Mark
1973-01-01
An overview of Noam Chomsky's theories about transformational grammar and phonology is given. Since Chomsky was interested in characterizing what it is to know a language, the ways in which we demonstrate knowledge of our native language are discussed in detail. Particular emphasis is placed on describing how the transformational approach actually…
Grammar Texts and Consumerist Subtexts
ERIC Educational Resources Information Center
Sokolik, M. E.
2007-01-01
While several checklists exist for the evaluation of ESL/EFL textbooks, none includes suggestions for looking for specific biases, especially those found in the content of examples and sample sentences. Growing awareness in publishing has reduced problems in the presentation of gender-based and racial biases in most ESL/EFL grammar textbooks, but…
Learnable Classes of Categorial Grammars.
ERIC Educational Resources Information Center
Kanazawa, Makoto
Learnability theory is an attempt to illuminate the concept of learnability using a mathematical model of learning. Two models of learning of categorial grammars are examined here: the standard model, in which sentences presented to the learner are flat strings of words, and one in which sentences are presented in the form of functor-argument…
Grammar Rules as Computer Algorithms.
ERIC Educational Resources Information Center
Rieber, Lloyd
1992-01-01
One college writing teacher engaged his class in the revision of a computer program to check grammar, focusing on improvement of the algorithms for identifying inappropriate uses of the passive voice. Process and problems of constructing new algorithms, effects on student writing, and other algorithm applications are discussed. (MSE)
ERIC Educational Resources Information Center
Lawes, Jonathan F.
2013-01-01
Graphing polar curves typically involves a combination of three traditional techniques, all of which can be time-consuming and tedious. However, an alternative method--graphing the polar function on a rectangular plane--simplifies graphing, increases student understanding of the polar coordinate system, and reinforces graphing techniques learned…
Gonzalez-Diaz, Humberto; Arrasate, Sonia; Juan, Asier Gomez-San; Sotomayor, Nuria; Lete, Esther; Speck-Planche, Alejandro; Ruso, Juan M; Luan, Feng; Cordeiro, Maria Natalia Dias Soeiro
2014-01-01
The study of quantitative structure-property relationships (QSPR) is important to study complex networks of chemical reactions in drug synthesis or metabolism or drug-target interaction networks. A difficult but possible goal is the prediction of drug absorption, distribution, metabolism, and excretion (ADME) process with a single QSPR model. For this QSPR modelers need to use flexible structural parameters useful for the description of many different systems at different structural scales (multi-scale parameters). Also they need to use powerful analytical methods able to link in a single multi-scale hypothesis structural parameters of different target systems (multi-target modeling) with different experimental properties of these systems (multi-output models). In this sense, the QSPR study of complex bio-molecular systems may benefit substantially from the combined application of spectral moments of graph representations of complex systems with perturbation theory methods. On one hand, spectral moments are almost universal parameters that can be calculated to many different matrices used to represent the structure of the states of different systems. On the other hand, perturbation methods can be used to add "small" variation terms to parameters of a known state of a given system in order to approach to a solution of another state of the same or similar system with unknown properties. Here we present one state-of-art review about the different applications of spectral moments to describe complex bio-molecular systems. Next, we give some general ideas and formulate plausible linear models for a general-purpose perturbation theory of QSPR problems of complex systems. Last, we develop three new QSPR-Perturbation theory models based on spectral moments for three different problems with multiple in-out boundary conditions that are relevant to biomolecular sciences. The three models developed correctly classify more than pairs 115,600; 48,000; 134,900 cases of the
Grammar Teaching Revisited: EFL Teachers between Grammar Abstinence and Formal Grammar Teaching
ERIC Educational Resources Information Center
Nazari, Ahmad; Allahyar, Negah
2012-01-01
The study of English language teachers' cognitions and its relationship to teachers' classroom practices have recently been the focus of language teaching and teacher education (Borg, 2006 & 2010). However, rarely have the studies delved into teachers' knowledge about grammar (reviewed by Borg, 2001) or investigated the relationships between…
Inverse scattering problem for quantum graph vertices
Cheon, Taksu; Turek, Ondrej; Exner, Pavel
2011-06-15
We demonstrate how the inverse scattering problem of a quantum star graph can be solved by means of diagonalization of the Hermitian unitary matrix when the vertex coupling is of the scale-invariant (or Fueloep-Tsutsui) form. This enables the construction of quantum graphs with desired properties in a tailor-made fashion. The procedure is illustrated on the example of quantum vertices with equal transmission probabilities.
Partitioning sparse matrices with eigenvectors of graphs
NASA Technical Reports Server (NTRS)
Pothen, Alex; Simon, Horst D.; Liou, Kang-Pu
1990-01-01
The problem of computing a small vertex separator in a graph arises in the context of computing a good ordering for the parallel factorization of sparse, symmetric matrices. An algebraic approach for computing vertex separators is considered in this paper. It is shown that lower bounds on separator sizes can be obtained in terms of the eigenvalues of the Laplacian matrix associated with a graph. The Laplacian eigenvectors of grid graphs can be computed from Kronecker products involving the eigenvectors of path graphs, and these eigenvectors can be used to compute good separators in grid graphs. A heuristic algorithm is designed to compute a vertex separator in a general graph by first computing an edge separator in the graph from an eigenvector of the Laplacian matrix, and then using a maximum matching in a subgraph to compute the vertex separator. Results on the quality of the separators computed by the spectral algorithm are presented, and these are compared with separators obtained from other algorithms for computing separators. Finally, the time required to compute the Laplacian eigenvector is reported, and the accuracy with which the eigenvector must be computed to obtain good separators is considered. The spectral algorithm has the advantage that it can be implemented on a medium-size multiprocessor in a straightforward manner.
Does complexity matter? Meta-analysis of learner performance in artificial grammar tasks.
Schiff, Rachel; Katan, Pesia
2014-01-01
Complexity has been shown to affect performance on artificial grammar learning (AGL) tasks (categorization of test items as grammatical/ungrammatical according to the implicitly trained grammar rules). However, previously published AGL experiments did not utilize consistent measures to investigate the comprehensive effect of grammar complexity on task performance. The present study focused on computerizing Bollt and Jones's (2000) technique of calculating topological entropy (TE), a quantitative measure of AGL charts' complexity, with the aim of examining associations between grammar systems' TE and learners' AGL task performance. We surveyed the literature and identified 56 previous AGL experiments based on 10 different grammars that met the sampling criteria. Using the automated matrix-lift-action method, we assigned a TE value for each of these 10 previously used AGL systems and examined its correlation with learners' task performance. The meta-regression analysis showed a significant correlation, demonstrating that the complexity effect transcended the different settings and conditions in which the categorization task was performed. The results reinforced the importance of using this new automated tool to uniformly measure grammar systems' complexity when experimenting with and evaluating the findings of AGL studies.
Multiword Constructions in the Grammar.
Culicover, Peter W; Jackendoff, Ray; Audring, Jenny
2017-03-07
There is ample evidence that speakers' linguistic knowledge extends well beyond what can be described in terms of rules of compositional interpretation stated over combinations of single words. We explore a range of multiword constructions (MWCs) to get a handle both on the extent of the phenomenon and on the grammatical constraints that may govern it. We consider idioms of various sorts, collocations, compounds, light verbs, syntactic nuts, and assorted other constructions, as well as morphology. Our conclusion is that MWCs highlight the central role that grammar plays in licensing MWCs in the lexicon and the creation of novel MWCs, and they help to clarify how the lexicon articulates with the rest of the grammar.
Grammar Games: A Case for Instructionist Game Models to Enhance Grammar Awareness and Accuracy
ERIC Educational Resources Information Center
Raftery, Brian; Santos, Jennifer
2015-01-01
Based on our own experiences teaching grammar in developmental writing classes and classes not dedicated to writing instruction, along with a history of scholarship that indicates a need for grammar pedagogies (e.g., Dougherty, 2012), instructor-designed grammar games can likely help facilitate learning about these mechanics of writing while…
A REFERENCE GRAMMAR OF HINDI, A STUDY OF SOME SELECTED TOPICS IN HINDI GRAMMAR.
ERIC Educational Resources Information Center
BAHL, KALI C.
A REFERENCE GRAMMAR WAS COMPILED FOR MODERN STANDARD HINDI GRAMMAR. THIS GRAMMAR IS BASED UPON A VIEW THAT HINDI IS A LITERARY LANGUAGE, AND THAT ITS SYNTAX SHOULD THEREFORE BE STUDIED NOT ONLY AS THE SYNTAX OF A COLLOQUIAL LANGUAGE BUT ALSO AS THE SYNTAX OF A LITERARY LANGUAGE. THE MATERIAL FOR THE STUDY WAS TAKEN FROM LITERARY TEXTS. SOME…
The minimalist grammar of action
Pastra, Katerina; Aloimonos, Yiannis
2012-01-01
Language and action have been found to share a common neural basis and in particular a common ‘syntax’, an analogous hierarchical and compositional organization. While language structure analysis has led to the formulation of different grammatical formalisms and associated discriminative or generative computational models, the structure of action is still elusive and so are the related computational models. However, structuring action has important implications on action learning and generalization, in both human cognition research and computation. In this study, we present a biologically inspired generative grammar of action, which employs the structure-building operations and principles of Chomsky's Minimalist Programme as a reference model. In this grammar, action terminals combine hierarchically into temporal sequences of actions of increasing complexity; the actions are bound with the involved tools and affected objects and are governed by certain goals. We show, how the tool role and the affected-object role of an entity within an action drives the derivation of the action syntax in this grammar and controls recursion, merge and move, the latter being mechanisms that manifest themselves not only in human language, but in human action too. PMID:22106430
Flexible processing and the design of grammar.
Sag, Ivan A; Wasow, Thomas
2015-02-01
We explore the consequences of letting the incremental and integrative nature of language processing inform the design of competence grammar. What emerges is a view of grammar as a system of local monotonic constraints that provide a direct characterization of the signs (the form-meaning correspondences) of a given language. This "sign-based" conception of grammar has provided precise solutions to the key problems long thought to motivate movement-based analyses, has supported three decades of computational research developing large-scale grammar implementations, and is now beginning to play a role in computational psycholinguistics research that explores the use of underspecification in the incremental computation of partial meanings.
Product Grammars for Alignment and Folding.
Höner Zu Siederdissen, Christian; Hofacker, Ivo L; Stadler, Peter F
2015-01-01
We develop a theory of algebraic operations over linear and context-free grammars that makes it possible to combine simple "atomic" grammars operating on single sequences into complex, multi-dimensional grammars. We demonstrate the utility of this framework by constructing the search spaces of complex alignment problems on multiple input sequences explicitly as algebraic expressions of very simple one-dimensional grammars. In particular, we provide a fully worked frameshift-aware, semiglobal DNA-protein alignment algorithm whose grammar is composed of products of small, atomic grammars. The compiler accompanying our theory makes it easy to experiment with the combination of multiple grammars and different operations. Composite grammars can be written out in L(A)T(E)X for documentation and as a guide to implementation of dynamic programming algorithms. An embedding in Haskell as a domain-specific language makes the theory directly accessible to writing and using grammar products without the detour of an external compiler. Software and supplemental files available here: http://www.bioinf. uni-leipzig.de/Software/gramprod/.
On molecular graph comparison.
Melo, Jenny A; Daza, Edgar
2011-06-01
Since the last half of the nineteenth century, molecular graphs have been present in several branches of chemistry. When used for molecular structure representation, they have been compared after mapping the corresponding graphs into mathematical objects. However, direct molecular comparison of molecular graphs is a research field less explored. The goal of this mini-review is to show some distance and similarity coefficients which were proposed to directly compare molecular graphs or which could be useful to do so.
Graphing Inequalities, Connecting Meaning
ERIC Educational Resources Information Center
Switzer, J. Matt
2014-01-01
Students often have difficulty with graphing inequalities (see Filloy, Rojano, and Rubio 2002; Drijvers 2002), and J. Matt Switzer's students were no exception. Although students can produce graphs for simple inequalities, they often struggle when the format of the inequality is unfamiliar. Even when producing a correct graph of an…
ERIC Educational Resources Information Center
Reading Teacher, 2012
2012-01-01
The "Toolbox" column features content adapted from ReadWriteThink.org lesson plans and provides practical tools for classroom teachers. This issue's column features a lesson plan adapted from "Graphing Plot and Character in a Novel" by Lisa Storm Fink and "Bio-graph: Graphing Life Events" by Susan Spangler. Students retell biographic events…
Graph distance for complex networks
NASA Astrophysics Data System (ADS)
Shimada, Yutaka; Hirata, Yoshito; Ikeguchi, Tohru; Aihara, Kazuyuki
2016-10-01
Networks are widely used as a tool for describing diverse real complex systems and have been successfully applied to many fields. The distance between networks is one of the most fundamental concepts for properly classifying real networks, detecting temporal changes in network structures, and effectively predicting their temporal evolution. However, this distance has rarely been discussed in the theory of complex networks. Here, we propose a graph distance between networks based on a Laplacian matrix that reflects the structural and dynamical properties of networked dynamical systems. Our results indicate that the Laplacian-based graph distance effectively quantifies the structural difference between complex networks. We further show that our approach successfully elucidates the temporal properties underlying temporal networks observed in the context of face-to-face human interactions.
Graph distance for complex networks
Shimada, Yutaka; Hirata, Yoshito; Ikeguchi, Tohru; Aihara, Kazuyuki
2016-01-01
Networks are widely used as a tool for describing diverse real complex systems and have been successfully applied to many fields. The distance between networks is one of the most fundamental concepts for properly classifying real networks, detecting temporal changes in network structures, and effectively predicting their temporal evolution. However, this distance has rarely been discussed in the theory of complex networks. Here, we propose a graph distance between networks based on a Laplacian matrix that reflects the structural and dynamical properties of networked dynamical systems. Our results indicate that the Laplacian-based graph distance effectively quantifies the structural difference between complex networks. We further show that our approach successfully elucidates the temporal properties underlying temporal networks observed in the context of face-to-face human interactions. PMID:27725690
Bipartite graph partitioning and data clustering
Zha, Hongyuan; He, Xiaofeng; Ding, Chris; Gu, Ming; Simon, Horst D.
2001-05-07
Many data types arising from data mining applications can be modeled as bipartite graphs, examples include terms and documents in a text corpus, customers and purchasing items in market basket analysis and reviewers and movies in a movie recommender system. In this paper, the authors propose a new data clustering method based on partitioning the underlying biopartite graph. The partition is constructed by minimizing a normalized sum of edge weights between unmatched pairs of vertices of the bipartite graph. They show that an approximate solution to the minimization problem can be obtained by computing a partial singular value decomposition (SVD) of the associated edge weight matrix of the bipartite graph. They point out the connection of their clustering algorithm to correspondence analysis used in multivariate analysis. They also briefly discuss the issue of assigning data objects to multiple clusters. In the experimental results, they apply their clustering algorithm to the problem of document clustering to illustrate its effectiveness and efficiency.
Flexible Processing and the Design of Grammar
ERIC Educational Resources Information Center
Sag, Ivan A.; Wasow, Thomas
2015-01-01
We explore the consequences of letting the incremental and integrative nature of language processing inform the design of competence grammar. What emerges is a view of grammar as a system of local monotonic constraints that provide a direct characterization of the signs (the form-meaning correspondences) of a given language. This…
Can the Grammar of Schooling Be Changed?
ERIC Educational Resources Information Center
Arbelaiz, Asuncion Martinez; Correa Gorospe, Jose Miguel
2009-01-01
In this article we propose that the grammar of schooling [Tyack, D., & Tobin, W. (1994). "The 'grammar' of schooling: Why has it been so hard to change?" "American Educational Research Journal, 31"(3), 453-479.] is responsible not only for the well-known and world-wide difficulties in integrating ICT into formal educational settings, but also for…
Student Teacher Beliefs on Grammar Instruction
ERIC Educational Resources Information Center
Graus, Johan; Coppen, Peter-Arno
2016-01-01
The role of grammar teaching in foreign language education is a controversial one both in second language acquisition (SLA) research and language pedagogy and, as a result, a potential source of confusion to student teachers. The objective of this study was to gain insight into the beliefs on grammar teaching of student teachers of English as a…
Albanian Basic Course: Exercises in Grammar.
ERIC Educational Resources Information Center
Defense Language Inst., Washington, DC.
This volume of exercises in grammar has been designed by the Defense Language Institute as a supplement to volumes 2-6 to reinforce and overlearn grammar patterns, with emphasis on case structure through specially developed sentences. Contents include exercises on: (1) interrogative pronouns, (2) declension of nouns, (3) demonstrative adjectives,…
Generalized Categorial Grammar for Unbounded Dependencies Recovery
ERIC Educational Resources Information Center
Nguyen, Luan Viet
2014-01-01
Accurate recovery of predicate-argument dependencies is vital for interpretation tasks like information extraction and question answering, and unbounded dependencies may account for a significant portion of the dependencies in any given text. This thesis describes a Generalized Categorial Grammar (GCG) which, like other categorial grammars,…
Reading and Grammar Learning through Mobile Phones
ERIC Educational Resources Information Center
Wang, Shudong; Smith, Simon
2013-01-01
This paper describes an ongoing language-learning project, three years into its development. We examine both the feasibility and the limitations of developing English reading and grammar skills through the interface of mobile phones. Throughout the project, reading and grammar materials were regularly sent to students' mobile phones. Students read…
Video Game Based Learning in English Grammar
ERIC Educational Resources Information Center
Singaravelu, G.
2008-01-01
The study enlightens the effectiveness of Video Game Based Learning in English Grammar at standard VI. A Video Game package was prepared and it consisted of self-learning activities in play way manner which attracted the minds of the young learners. Chief objective: Find out the effectiveness of Video-Game based learning in English grammar.…
Research into Practice: Grammar Learning and Teaching
ERIC Educational Resources Information Center
Larsen-Freeman, Diane
2015-01-01
This selective review of the second language acquisition and applied linguistics research literature on grammar learning and teaching falls into three categories: where research has had little impact (the non-interface position), modest impact (form-focused instruction), and where it potentially can have a large impact (reconceiving grammar).…
Exploring Dyslexics' Phonological Deficit II: Phonological Grammar
ERIC Educational Resources Information Center
Szenkovits, Gayaneh; Darma, Quynliaan; Darcy, Isabelle; Ramus, Franck
2016-01-01
Language learners have to acquire the phonological grammar of their native language, and different levels of representations on which the grammar operates. Developmental dyslexia is associated with a phonological deficit, which is commonly assumed to stem from degraded phonological representations. The present study investigates one aspect of the…
Studies in French Grammar and Phonology.
ERIC Educational Resources Information Center
Benguerel, Andre-Pierre; Grundstrom, Allan W.
The monograph contains two papers. The first presents a generative grammar for verbal forms in French. It consists of an ordered set of rewrite rules and a set of tables. It generates all existing verbal forms without generating any non-existing ones. The departure from an ordinary generative grammar lies in the use of a tabular form for…
What Is Grammar and Why Teach It?
ERIC Educational Resources Information Center
Greenbaum, Sidney
The word "grammar" can be used in many ways: a general theory of language description; a theory for describing one language; a description of a particular language, either in the form of a book (an "English grammar") or the contents of that book; an ideal as opposed to actual description of a language; the properties and processes of a language…
A Comparative Evaluation of French Grammar Checkers.
ERIC Educational Resources Information Center
Burston, Jack
1996-01-01
Four grammar checkers, all of French Canadian origin, were evaluated: "Le Correcteur 101,""GramR,""Hugo Plus," and "French Proofing Tools." Results indicate that "Le Correcteur 101" is the best French grammar checker on the market and worth its premium cost. (two references) (CK)
Towards a Framework for Teaching Spoken Grammar
ERIC Educational Resources Information Center
Timmis, Ivor
2005-01-01
Since the advent of spoken corpora, descriptions of native speaker spoken grammar have become far more detailed and comprehensive. These insights, however, have been relatively slow to filter through to ELT practice. The aim of this article is to outline an approach to the teaching of native-speaker spoken grammar which is not only pedagogically…
Non-Intrusive Grammar in Writing.
ERIC Educational Resources Information Center
Roberts, Claudette M.; Boggase, Barbara A.
Since introducing a grammar unit can be daunting and frustrating for both teachers and students, a collaborative unit for a 10th-grade class was planned that would satisfy an administrative requirement but also maintain the integrity of the writing program. The unit was planned by developing an approach of non-intrusive grammar instruction at the…
Propelling Students into Active Grammar Participation
ERIC Educational Resources Information Center
Jurhill, Dennis A.
2011-01-01
"O! this learning, what a thing it is." -W. Shakespeare, "The Taming of the Shrew." The aim of this action research was to find out if active grammar involvement amongst students might lead to better results. My approach was to activate my students during grammar instruction by using cooperative learning: that is a form of…
Towards a Pedagogy of Grammar Instruction
ERIC Educational Resources Information Center
Richards, Jack C.; Reppen, Randi
2014-01-01
Grammar can be viewed both as knowledge and as ability. When viewed as knowledge, the focus is on rules for sentence formation. When viewed as ability, the focus is on how grammar is used as a resource in the creation of spoken and written texts. Twelve principles are proposed as the basis for a pedagogy that focusses on acquiring learning to use…
A Prototype Grammar Kit in Prolog.
ERIC Educational Resources Information Center
Kahn, Kenneth M.
1984-01-01
Presents a prototype of a computerized grammar kit written in PROLOG and designed for children interested in exploring language. PROLOG's advantages for building parsers, generators, translators, and question-answering systems are discussed, and a scenario of a child working on a grammar project using the kit and implementation issues are…
Wong, Pak C.; Mackey, Patrick S.; Perrine, Kenneth A.; Foote, Harlan P.; Thomas, James J.
2008-12-23
Methods for visualizing a graph by automatically drawing elements of the graph as labels are disclosed. In one embodiment, the method comprises receiving node information and edge information from an input device and/or communication interface, constructing a graph layout based at least in part on that information, wherein the edges are automatically drawn as labels, and displaying the graph on a display device according to the graph layout. In some embodiments, the nodes are automatically drawn as labels instead of, or in addition to, the label-edges.
Kolodny, Oren; Lotem, Arnon; Edelman, Shimon
2015-03-01
We introduce a set of biologically and computationally motivated design choices for modeling the learning of language, or of other types of sequential, hierarchically structured experience and behavior, and describe an implemented system that conforms to these choices and is capable of unsupervised learning from raw natural-language corpora. Given a stream of linguistic input, our model incrementally learns a grammar that captures its statistical patterns, which can then be used to parse or generate new data. The grammar constructed in this manner takes the form of a directed weighted graph, whose nodes are recursively (hierarchically) defined patterns over the elements of the input stream. We evaluated the model in seventeen experiments, grouped into five studies, which examined, respectively, (a) the generative ability of grammar learned from a corpus of natural language, (b) the characteristics of the learned representation, (c) sequence segmentation and chunking, (d) artificial grammar learning, and (e) certain types of structure dependence. The model's performance largely vindicates our design choices, suggesting that progress in modeling language acquisition can be made on a broad front-ranging from issues of generativity to the replication of human experimental findings-by bringing biological and computational considerations, as well as lessons from prior efforts, to bear on the modeling approach.
Using a Linguistic Theory of Humour in Teaching English Grammar
ERIC Educational Resources Information Center
Abdulmajeed, Rufaidah Kamal; Hameed, Sarab Khalil
2017-01-01
Teachers who teach a new language grammar do not usually have the time and the proper situation to introduce humour when starting a new topic in grammar. There are many different opinions about teaching grammar. Many teachers seem to believe in the importance of grammar lessons devoted to a study of language rules and practical exercises. Other…
Grammar and Its Teaching: Challenging the Myths. ERIC Digest.
ERIC Educational Resources Information Center
Larsen-Freeman, Diane
This digest considers the misconception that grammar is a collection of arbitrary rules about static structures in a language by challenging 10 common myths about grammar and its teaching. The myths include the following: (1) grammar is acquired naturally; it need not be taught; (2) grammar is a collection of meaningless forms; (3) grammar…
What English Teachers Need to Know about Grammar.
ERIC Educational Resources Information Center
Murdick, William
1996-01-01
Suggests that English teachers need to know that grammar is a difficult subject; know what children know about grammar; know that grammatical error is complex; and know more about language than just grammar. Concludes with the advice of Noam Chomsky--that grammar should be taught for its own intrinsic interest. (RS)
ANTLR Tree Grammar Generator and Extensions
NASA Technical Reports Server (NTRS)
Craymer, Loring
2005-01-01
A computer program implements two extensions of ANTLR (Another Tool for Language Recognition), which is a set of software tools for translating source codes between different computing languages. ANTLR supports predicated- LL(k) lexer and parser grammars, a notation for annotating parser grammars to direct tree construction, and predicated tree grammars. [ LL(k) signifies left-right, leftmost derivation with k tokens of look-ahead, referring to certain characteristics of a grammar.] One of the extensions is a syntax for tree transformations. The other extension is the generation of tree grammars from annotated parser or input tree grammars. These extensions can simplify the process of generating source-to-source language translators and they make possible an approach, called "polyphase parsing," to translation between computing languages. The typical approach to translator development is to identify high-level semantic constructs such as "expressions," "declarations," and "definitions" as fundamental building blocks in the grammar specification used for language recognition. The polyphase approach is to lump ambiguous syntactic constructs during parsing and then disambiguate the alternatives in subsequent tree transformation passes. Polyphase parsing is believed to be useful for generating efficient recognizers for C++ and other languages that, like C++, have significant ambiguities.
Smoly, Ilan; Carmel, Amir; Shemer-Avni, Yonat; Yeger-Lotem, Esti; Ziv-Ukelson, Michal
2016-03-01
Network querying is a powerful approach to mine molecular interaction networks. Most state-of-the-art network querying tools either confine the search to a prespecified topology in the form of some template subnetwork, or do not specify any topological constraints at all. Another approach is grammar-based queries, which are more flexible and expressive as they allow for expressing the topology of the sought pattern according to some grammar-based logic. Previous grammar-based network querying tools were confined to the identification of paths. In this article, we extend the patterns identified by grammar-based query approaches from paths to trees. For this, we adopt a higher order query descriptor in the form of a regular tree grammar (RTG). We introduce a novel problem and propose an algorithm to search a given graph for the k highest scoring subgraphs matching a tree accepted by an RTG. Our algorithm is based on the combination of dynamic programming with color coding, and includes an extension of previous k-best parsing optimization approaches to avoid isomorphic trees in the output. We implement the new algorithm and exemplify its application to mining viral infection patterns within molecular interaction networks. Our code is available online.
NASA Technical Reports Server (NTRS)
Lieberman, R. N.
1972-01-01
Given a directed graph, a natural topology is defined and relationships between standard topological properties and graph theoretical concepts are studied. In particular, the properties of connectivity and separatedness are investigated. A metric is introduced which is shown to be related to separatedness. The topological notions of continuity and homeomorphism. A class of maps is studied which preserve both graph and topological properties. Applications involving strong maps and contractions are also presented.
Terminal context in context-sensitive grammars.
NASA Technical Reports Server (NTRS)
Book, R. V.
1972-01-01
Investigation of the conditions whereunder context-sensitive grammars generate context-free languages. The obtained results indicate that, if every noncontext-free rewriting rule of a context-sensitive grammar has as left context a string of terminal symbols and the left context is at least as long as the right context, then the language generated is context-free. Likewise, if every noncontext-free rewriting rule of a context-sensitive grammar has strings of terminal symbols as left and right contexts, then the language generated is also context-free.
Recognition of Probe Ptolemaic Graphs
NASA Astrophysics Data System (ADS)
Chang, Maw-Shang; Hung, Ling-Ju
Let G denote a graph class. An undirected graph G is called a probe G graph if one can make G a graph in G by adding edges between vertices in some independent set of G. By definition graph class G is a subclass of probe G graphs. Ptolemaic graphs are chordal and induced gem free. They form a subclass of both chordal graphs and distance-hereditary graphs. Many problems NP-hard on chordal graphs can be solved in polynomial time on ptolemaic graphs. We proposed an O(nm)-time algorithm to recognize probe ptolemaic graphs where n and m are the numbers of vertices and edges of the input graph respectively.
Lothian, Josh; Powers, Sarah S; Sullivan, Blair D; Baker, Matthew B; Schrock, Jonathan; Poole, Stephen W
2013-12-01
The benchmarking effort within the Extreme Scale Systems Center at Oak Ridge National Laboratory seeks to provide High Performance Computing benchmarks and test suites of interest to the DoD sponsor. The work described in this report is a part of the effort focusing on graph generation. A previously developed benchmark, SystemBurn, allowed the emulation of dierent application behavior profiles within a single framework. To complement this effort, similar capabilities are desired for graph-centric problems. This report examines existing synthetic graph generator implementations in preparation for further study on the properties of their generated synthetic graphs.
Frishman, Yaniv; Tal, Ayellet
2008-01-01
This paper presents an algorithm for drawing a sequence of graphs online. The algorithm strives to maintain the global structure of the graph and thus the user's mental map, while allowing arbitrary modifications between consecutive layouts. The algorithm works online and uses various execution culling methods in order to reduce the layout time and handle large dynamic graphs. Techniques for representing graphs on the GPU allow a speedup by a factor of up to 17 compared to the CPU implementation. The scalability of the algorithm across GPU generations is demonstrated. Applications of the algorithm to the visualization of discussion threads in Internet sites and to the visualization of social networks are provided.
Constrained Markovian Dynamics of Random Graphs
NASA Astrophysics Data System (ADS)
Coolen, A. C. C.; de Martino, A.; Annibale, A.
2009-09-01
We introduce a statistical mechanics formalism for the study of constrained graph evolution as a Markovian stochastic process, in analogy with that available for spin systems, deriving its basic properties and highlighting the role of the `mobility' (the number of allowed moves for any given graph). As an application of the general theory we analyze the properties of degree-preserving Markov chains based on elementary edge switchings. We give an exact yet simple formula for the mobility in terms of the graph's adjacency matrix and its spectrum. This formula allows us to define acceptance probabilities for edge switchings, such that the Markov chains become controlled Glauber-type detailed balance processes, designed to evolve to any required invariant measure (representing the asymptotic frequencies with which the allowed graphs are visited during the process). As a corollary we also derive a condition in terms of simple degree statistics, sufficient to guarantee that, in the limit where the number of nodes diverges, even for state-independent acceptance probabilities of proposed moves the invariant measure of the process will be uniform. We test our theory on synthetic graphs and on realistic larger graphs as studied in cellular biology, showing explicitly that, for instances where the simple edge swap dynamics fails to converge to the uniform measure, a suitably modified Markov chain instead generates the correct phase space sampling.
Robust Spectral Clustering Using Statistical Sub-Graph Affinity Model
Eichel, Justin A.; Wong, Alexander; Fieguth, Paul; Clausi, David A.
2013-01-01
Spectral clustering methods have been shown to be effective for image segmentation. Unfortunately, the presence of image noise as well as textural characteristics can have a significant negative effect on the segmentation performance. To accommodate for image noise and textural characteristics, this study introduces the concept of sub-graph affinity, where each node in the primary graph is modeled as a sub-graph characterizing the neighborhood surrounding the node. The statistical sub-graph affinity matrix is then constructed based on the statistical relationships between sub-graphs of connected nodes in the primary graph, thus counteracting the uncertainty associated with the image noise and textural characteristics by utilizing more information than traditional spectral clustering methods. Experiments using both synthetic and natural images under various levels of noise contamination demonstrate that the proposed approach can achieve improved segmentation performance when compared to existing spectral clustering methods. PMID:24386111
Kim, Namhee; Zheng, Zhe; Elmetwaly, Shereef; Schlick, Tamar
2014-01-01
Graph representations have been widely used to analyze and design various economic, social, military, political, and biological networks. In systems biology, networks of cells and organs are useful for understanding disease and medical treatments and, in structural biology, structures of molecules can be described, including RNA structures. In our RNA-As-Graphs (RAG) framework, we represent RNA structures as tree graphs by translating unpaired regions into vertices and helices into edges. Here we explore the modularity of RNA structures by applying graph partitioning known in graph theory to divide an RNA graph into subgraphs. To our knowledge, this is the first application of graph partitioning to biology, and the results suggest a systematic approach for modular design in general. The graph partitioning algorithms utilize mathematical properties of the Laplacian eigenvector (µ2) corresponding to the second eigenvalues (λ2) associated with the topology matrix defining the graph: λ2 describes the overall topology, and the sum of µ2's components is zero. The three types of algorithms, termed median, sign, and gap cuts, divide a graph by determining nodes of cut by median, zero, and largest gap of µ2's components, respectively. We apply these algorithms to 45 graphs corresponding to all solved RNA structures up through 11 vertices (∼ 220 nucleotides). While we observe that the median cut divides a graph into two similar-sized subgraphs, the sign and gap cuts partition a graph into two topologically-distinct subgraphs. We find that the gap cut produces the best biologically-relevant partitioning for RNA because it divides RNAs at less stable connections while maintaining junctions intact. The iterative gap cuts suggest basic modules and assembly protocols to design large RNA structures. Our graph substructuring thus suggests a systematic approach to explore the modularity of biological networks. In our applications to RNA structures, subgraphs also suggest
Developmental assessment of Spanish grammar.
Toronto, A S
1976-05-01
The Developmental Assessment of Spanish Grammar (DASG) provides a language analysis procedure for Spanish-speaking children similar to the Developmental Sentence Scoring (DSS) procedure in English. The DASG is not an attempted translation of the DSS but was developed independently, taking into consideration the present knowledge of Spanish language acquisition. The purpose of the DASG is to evaluate the language of children with deficient grammatical skills in Spanish and to serve as a model for structuring Spanish language therapy. Proposed syntactic hierarchies for the following six grammatical categories are presented: indefinite pronouns and noun modifiers, personal pronouns, primary verbs, secondary verbs, conjunctions, and interrogative words. Weighted scores are assigned to groups of structures within the hierarchies and are used to score Spanish sentences children use spontaneously in conversation with an adult. The DASG was standardized on 128 Spanish-speaking children between the ages of 3.0 and 6.11 years. Norms and reliability measures are presented.
Cognitive grammar and aphasic discourse.
Manning, Molly; Franklin, Sue
2016-01-01
In cognitive grammar (CG), there is no clear division between language and other cognitive processes; all linguistic form is conceptually meaningful. In this pilot study, a CG approach was applied to investigate whether people with aphasia (PWA) have cognitive linguistic difficulty not predicted from traditional, componential models of aphasia. Narrative samples from 22 PWA (6 fluent, 16 non-fluent) were compared with samples from 10 participants without aphasia. Between-group differences were tested statistically. PWA had significant difficulty with temporal sequencing, suggesting problems that are not uniquely linguistic. For some, these problems were doubly dissociated with naming, used as a general measure of severity, which indicates that cognitive linguistic difficulties are not linked with more widespread brain damage. Further investigation may lead to a richer account of aphasia in line with contemporary linguistics and cognitive science approaches.
Description of the human hand grasp using graph theory.
Liu, Xiancan; Zhan, Qiang
2013-07-01
This paper presents a method to describe and analyze the human hand grasp postures so as to indicate which fingers should act during grasping and the required movements of those fingers. The method first describes the human hand with human hand tree graph and incidence matrix, and then the relationship between the human hand and the grasped object is described by grasp contact graph and basic cycle matrix that can be divided into an identity matrix and a Bf12 matrix. The nonzero columns of the Bf12 matrix can be described by a graph called VF-tree, which can indicate which fingers are active while grasping and the required degree of freedom of each finger. The method is validated by describing and analyzing the six basic grasp postures of the human hand.
ERIC Educational Resources Information Center
Hirsch, Christian R.
1975-01-01
Using a set of worksheets, students will discover and apply Euler's formula regarding connected planar graphs and play and analyze the game of Sprouts. One sheet leads to the discovery of Euler's formula; another concerns traversability of a graph; another gives an example and a game involving these ideas. (Author/KM)
ERIC Educational Resources Information Center
Lind, Joy; Narayan, Darren
2009-01-01
We present the topic of graph connectivity along with a famous theorem of Menger in the real-world setting of the national computer network infrastructure of "National LambdaRail". We include a set of exercises where students reinforce their understanding of graph connectivity by analysing the "National LambdaRail" network. Finally, we give…
Caetano, Tibério S; McAuley, Julian J; Cheng, Li; Le, Quoc V; Smola, Alex J
2009-06-01
As a fundamental problem in pattern recognition, graph matching has applications in a variety of fields, from computer vision to computational biology. In graph matching, patterns are modeled as graphs and pattern recognition amounts to finding a correspondence between the nodes of different graphs. Many formulations of this problem can be cast in general as a quadratic assignment problem, where a linear term in the objective function encodes node compatibility and a quadratic term encodes edge compatibility. The main research focus in this theme is about designing efficient algorithms for approximately solving the quadratic assignment problem, since it is NP-hard. In this paper we turn our attention to a different question: how to estimate compatibility functions such that the solution of the resulting graph matching problem best matches the expected solution that a human would manually provide. We present a method for learning graph matching: the training examples are pairs of graphs and the 'labels' are matches between them. Our experimental results reveal that learning can substantially improve the performance of standard graph matching algorithms. In particular, we find that simple linear assignment with such a learning scheme outperforms Graduated Assignment with bistochastic normalisation, a state-of-the-art quadratic assignment relaxation algorithm.
ERIC Educational Resources Information Center
Petrosino, Anthony
2012-01-01
This article responds to arguments by Skidmore and Thompson (this issue of "Educational Researcher") that a graph published more than 10 years ago was erroneously reproduced and "gratuitously damaged" perceptions of the quality of education research. After describing the purpose of the original graph, the author counters assertions that the graph…
ERIC Educational Resources Information Center
Shen, Ji
2009-01-01
In the Walking Out Graphs Lesson described here, students experience several types of representations used to describe motion, including words, sentences, equations, graphs, data tables, and actions. The most important theme of this lesson is that students have to understand the consistency among these representations and form the habit of…
Graphing from Everyday Experience.
ERIC Educational Resources Information Center
Carraher, David; Schliemann, Analucia; Nemirousky, Ricardo
1995-01-01
Discusses the importance of teaching grounded in the everyday experiences and concerns of the learners. Studies how people with limited school experience can understand graphs and concludes that individuals with limited academic education can clarify the role of everyday experiences in learning about graphs. (ASK)
ERIC Educational Resources Information Center
Johnson, Millie
1997-01-01
Graphs from media sources and questions developed from them can be used in the middle school mathematics classroom. Graphs depict storage temperature on a milk carton; air pressure measurements on a package of shock absorbers; sleep-wake patterns of an infant; a dog's breathing patterns; and the angle, velocity, and radius of a leaning bicyclist…
ERIC Educational Resources Information Center
Doto, Julianne; Golbeck, Susan
2007-01-01
Collecting data and analyzing the results of experiments is difficult for children. The authors found a surprising way to help their third graders make graphs and draw conclusions from their data: digital photographs. The pictures bridged the gap between an abstract graph and the plants it represented. With the support of the photos, students…
Evolutionary stability on graphs
Ohtsuki, Hisashi; Nowak, Martin A.
2008-01-01
Evolutionary stability is a fundamental concept in evolutionary game theory. A strategy is called an evolutionarily stable strategy (ESS), if its monomorphic population rejects the invasion of any other mutant strategy. Recent studies have revealed that population structure can considerably affect evolutionary dynamics. Here we derive the conditions of evolutionary stability for games on graphs. We obtain analytical conditions for regular graphs of degree k > 2. Those theoretical predictions are compared with computer simulations for random regular graphs and for lattices. We study three different update rules: birth-death (BD), death-birth (DB), and imitation (IM) updating. Evolutionary stability on sparse graphs does not imply evolutionary stability in a well-mixed population, nor vice versa. We provide a geometrical interpretation of the ESS condition on graphs. PMID:18295801
ERIC Educational Resources Information Center
Vannestal, Maria Estling; Lindquist, Hans
2007-01-01
Corpora have been used for pedagogical purposes for more than two decades but empirical studies are relatively rare, particularly in the context of grammar teaching. The present study focuses on students' attitudes towards grammar and how these attitudes are affected by the introduction of concordancing. The principal aims of the project were to…
ERIC Educational Resources Information Center
Watson, Annabel Mary
2015-01-01
This paper reports on an investigation of L1 English teachers' conceptual and evaluative beliefs about teaching grammar, one strand of a larger Economic and Social Research Council (ESRC)-funded investigation into the impact of contextualised grammar teaching [RES-062-23-0775]. Thirty-one teachers in English secondary schools were interviewed…
The Tower of Babel and the Teaching of Grammar: Writing Instruction for a New Century.
ERIC Educational Resources Information Center
Martinsen, Amy
2000-01-01
Considers the teaching of grammar and its importance in the writing classroom. Examines what grammar is; why writing instruction has moved away from grammar; differing opinions regarding grammar and writing instruction; and grammar's place in the writing classroom of the new century. Argues that grammar must be applied to students' own writing.…
The Effect of Using Graphing Calculators in Complex Function Graphs
ERIC Educational Resources Information Center
Ocak, Mehmet Akif
2008-01-01
This study investigates the role of graphing calculators in multiple representations for knowledge transfer and the omission of oversimplification in complex function graphs. The main aim is to examine whether graphing calculators were used efficiently to see different cases and multiple perspectives among complex function graphs, or whether…
Asymptote Misconception on Graphing Functions: Does Graphing Software Resolve It?
ERIC Educational Resources Information Center
Öçal, Mehmet Fatih
2017-01-01
Graphing function is an important issue in mathematics education due to its use in various areas of mathematics and its potential roles for students to enhance learning mathematics. The use of some graphing software assists students' learning during graphing functions. However, the display of graphs of functions that students sketched by hand may…
A new variant of Petri net controlled grammars
NASA Astrophysics Data System (ADS)
Jan, Nurhidaya Mohamad; Turaev, Sherzod; Fong, Wan Heng; Sarmin, Nor Haniza
2015-10-01
A Petri net controlled grammar is a Petri net with respect to a context-free grammar where the successful derivations of the grammar can be simulated using the occurrence sequences of the net. In this paper, we introduce a new variant of Petri net controlled grammars, called a place-labeled Petri net controlled grammar, which is a context-free grammar equipped with a Petri net and a function which maps places of the net to productions of the grammar. The language consists of all terminal strings that can be obtained by parallelly applying multisets of the rules which are the images of the sets of the input places of transitions in a successful occurrence sequence of the Petri net. We study the effect of the different labeling strategies to the computational power and establish lower and upper bounds for the generative capacity of place-labeled Petri net controlled grammars.
Burioni, Raffaella; Chibbaro, Sergio; Vergni, Davide; Vulpiani, Angelo
2012-11-01
We study reaction-diffusion processes on graphs through an extension of the standard reaction-diffusion equation starting from first principles. We focus on reaction spreading, i.e., on the time evolution of the reaction product M(t). At variance with pure diffusive processes, characterized by the spectral dimension d{s}, the important quantity for reaction spreading is found to be the connectivity dimension d{l}. Numerical data, in agreement with analytical estimates based on the features of n independent random walkers on the graph, show that M(t)∼t{d{l}}. In the case of Erdös-Renyi random graphs, the reaction product is characterized by an exponential growth M(t)e{αt} with α proportional to ln(k), where (k) is the average degree of the graph.
A Semantic Graph Query Language
Kaplan, I L
2006-10-16
Semantic graphs can be used to organize large amounts of information from a number of sources into one unified structure. A semantic query language provides a foundation for extracting information from the semantic graph. The graph query language described here provides a simple, powerful method for querying semantic graphs.
NASA Astrophysics Data System (ADS)
Sui, Xiukai; Wu, Bin; Wang, Long
2015-12-01
The likelihood that a mutant fixates in the wild population, i.e., fixation probability, has been intensively studied in evolutionary game theory, where individuals' fitness is frequency dependent. However, it is of limited interest when it takes long to take over. Thus the speed of evolution becomes an important issue. In general, it is still unclear how fixation times are affected by the population structure, although the fixation times have already been addressed in the well-mixed populations. Here we theoretically address this issue by pair approximation and diffusion approximation on regular graphs. It is shown (i) that under neutral selection, both unconditional and conditional fixation time are shortened by increasing the number of neighbors; (ii) that under weak selection, for the simplified prisoner's dilemma game, if benefit-to-cost ratio exceeds the degree of the graph, then the unconditional fixation time of a single cooperator is slower than that in the neutral case; and (iii) that under weak selection, for the conditional fixation time, limited neighbor size dilutes the counterintuitive stochastic slowdown which was found in well-mixed populations. Interestingly, we find that all of our results can be interpreted as that in the well-mixed population with a transformed payoff matrix. This interpretation is also valid for both death-birth and birth-death processes on graphs. This interpretation bridges the fixation time in the structured population and that in the well-mixed population. Thus it opens the avenue to investigate the challenging fixation time in structured populations by the known results in well-mixed populations.
Assortativity of complementary graphs
NASA Astrophysics Data System (ADS)
Wang, H.; Winterbach, W.; van Mieghem, P.
2011-09-01
Newman's measure for (dis)assortativity, the linear degree correlationρD, is widely studied although analytic insight into the assortativity of an arbitrary network remains far from well understood. In this paper, we derive the general relation (2), (3) and Theorem 1 between the assortativity ρD(G) of a graph G and the assortativityρD(Gc) of its complement Gc. Both ρD(G) and ρD(Gc) are linearly related by the degree distribution in G. When the graph G(N,p) possesses a binomial degree distribution as in the Erdős-Rényi random graphs Gp(N), its complementary graph Gpc(N) = G1-p(N) follows a binomial degree distribution as in the Erdős-Rényi random graphs G1-p(N). We prove that the maximum and minimum assortativity of a class of graphs with a binomial distribution are asymptotically antisymmetric: ρmax(N,p) = -ρmin(N,p) for N → ∞. The general relation (3) nicely leads to (a) the relation (10) and (16) between the assortativity range ρmax(G)-ρmin(G) of a graph with a given degree distribution and the range ρmax(Gc)-ρmin(Gc) of its complementary graph and (b) new bounds (6) and (15) of the assortativity. These results together with our numerical experiments in over 30 real-world complex networks illustrate that the assortativity range ρmax-ρmin is generally large in sparse networks, which underlines the importance of assortativity as a network characterizer.
Experimental Study of Quantum Graphs with Microwave Networks
NASA Astrophysics Data System (ADS)
Fu, Ziyuan; Koch, Trystan; Antonsen, Thomas; Ott, Edward; Anlage, Steven; Wave Chaos Team
An experimental setup consisting of microwave networks is used to simulate quantum graphs. The networks are constructed from coaxial cables connected by T junctions. The networks are built for operation both at room temperature and superconducting versions that operate at cryogenic temperatures. In the experiments, a phase shifter is connected to one of the network bonds to generate an ensemble of quantum graphs by varying the phase delay. The eigenvalue spectrum is found from S-parameter measurements on one-port graphs. With the experimental data, the nearest-neighbor spacing statistics and the impedance statistics of the graphs are examined. It is also demonstrated that time-reversal invariance for microwave propagation in the graphs can be broken without increasing dissipation significantly by making nodes with circulators. Random matrix theory (RMT) successfully describes universal statistical properties of the system. We acknowledge support under contract AFOSR COE Grant FA9550-15-1-0171.
Commuting projections on graphs
Vassilevski, Panayot S.; Zikatanov, Ludmil T.
2013-02-19
For a given (connected) graph, we consider vector spaces of (discrete) functions defined on its vertices and its edges. These two spaces are related by a discrete gradient operator, Grad and its adjoint, ₋Div, referred to as (negative) discrete divergence. We also consider a coarse graph obtained by aggregation of vertices of the original one. Then a coarse vertex space is identified with the subspace of piecewise constant functions over the aggregates. We consider the ℓ_{2}-projection Q_{H} onto the space of these piecewise constants. In the present paper, our main result is the construction of a projection π _{H} from the original edge-space onto a properly constructed coarse edge-space associated with the edges of the coarse graph. The projections π _{H} and Q_{H} commute with the discrete divergence operator, i.e., we have div π _{H} = Q_{H} div. The respective pair of coarse edge-space and coarse vertexspace offer the potential to construct two-level, and by recursion, multilevel methods for the mixed formulation of the graph Laplacian which utilizes the discrete divergence operator. The performance of one two-level method with overlapping Schwarz smoothing and correction based on the constructed coarse spaces for solving such mixed graph Laplacian systems is illustrated on a number of graph examples.
Image Registration Through The Exploitation Of Perspective Invariant Graphs
NASA Astrophysics Data System (ADS)
Gilmore, John F.
1983-10-01
This paper describes two new techniques of image registration as applied to scenes consisting of natural terrain. The first technique is a syntactic pattern recognition approach which combines the spatial relationships of a point pattern with point classifications to accurately perform image registration. In this approach, a preprocessor analyzes each image in order to identify points of interest and to classify these points based on statistical features. A classified graph possessing perspective invariant properties is created and is converted into a classification-based grammar string. A local match analysis is performed and the best global match is con-structed. A probability-of-match metric is computed in order to evaluate match confidence. The second technique described is an isomorphic graph matching approach called Mean Neighbors (MN). A MN graph is constructed from a given point pattern taking into account the elliptical projections of real world scenes onto a two dimensional surface. This approach exploits the spatial relationships of the given points of interest but neglects the point classifications used in syntactic processing. A projective, perspective invariant graph is constructed for both the reference and sensed images and a mapping of the coincidence edges occurs. A probability of match metric is used to evaluate the confidence of the best mapping.
ERIC Educational Resources Information Center
Safford, Kimberly
2016-01-01
The research examined the impact on teachers of the grammar element of a new statutory test in Spelling, Punctuation and Grammar (SPaG) in primary schools in England. The research aimed to evaluate the nature and the extent of changes to the teaching of grammar and to wider literacy teaching since the introduction of the test in 2013. The research…
Web Exclusive--The Case for Not Teaching Grammar
ERIC Educational Resources Information Center
Zwagerman, Sean
2012-01-01
The value of grammar instruction in improving students' writing has been debated for at least 150 years, and is showing no signs of tiring. But would teaching grammar actually improve writing? In fact, study after study has shown that the study of grammar does not translate to improved student writing. Indeed, the basic skills of writing are not…
Foreign-Language Grammar Instruction via the Mother Tongue
ERIC Educational Resources Information Center
Paradowski, Michal B.
2007-01-01
The chapter reports the results of a controlled experiment which suggest that foreign-language grammar instruction that forges explicit connections with the grammar of the students' mother tongue aids learning, at least as far as students' application of discrete-point grammar rules is concerned. (Contains 2 figures and 3 notes.) [This document…
Communicating Grammatically: Evaluating a Learner Strategy Website for Spanish Grammar
ERIC Educational Resources Information Center
Cohen, Andrew D.; Pinilla-Herrera, Angela; Thompson, Jonathan R.; Witzig, Lance E.
2011-01-01
After a brief introduction to language learner strategies and grammar strategies as a subcategory, it is pointed out that research on the use of grammar strategies by learners of a second language (L2) has been limited. The article then describes the construction of a website with strategies for learning and performing Spanish grammar, with a…
Difficulties in Teaching and Learning Grammar in an EFL Context
ERIC Educational Resources Information Center
Al-Mekhlafi, Abdu Mohammed; Nagaratnam, Ramani Perur
2011-01-01
The role of grammar instruction in an ESL/EFL context has been for decades a major issue for students and teachers alike. Researchers have debated whether grammar should be taught in the classroom and students, for their part, have generally looked upon grammar instruction as a necessary evil at best, and an avoidable burden at worst. The paper…
Rhetorical or Functional Grammar and the Teaching of Composition.
ERIC Educational Resources Information Center
Vande Kopple, William J.
Some insights into the nature of functional grammar can be useful for teachers of composition. There are four ways that functional grammar stands in opposition to common linguistics in the United States. First, for functionalists (those practicing functional grammar), the starting point is with kinds of meanings, not with kinds of structures; the…
Grammar as a Programming Language. Artificial Intelligence Memo 391.
ERIC Educational Resources Information Center
Rowe, Neil
Student projects that involve writing generative grammars in the computer language, "LOGO," are described in this paper, which presents a grammar-running control structure that allows students to modify and improve the grammar interpreter itself while learning how a simple kind of computer parser works. Included are procedures for…
Pedagogical Grammar. Interlanguage Studies Bulletin, Vol. 1., No. 1.
ERIC Educational Resources Information Center
Smith, Michael Sharwood
Pedagogical grammar is the presentation of grammatical information for teaching purposes. Two important distinctions are relevant here: reference books versus teaching grammars programmed into a course, and generalized versus specialized grammars, (depending on the extent to which they have been designed to meet specific teaching/learning…
Spoken Grammar and Its Role in the English Language Classroom
ERIC Educational Resources Information Center
Hilliard, Amanda
2014-01-01
This article addresses key issues and considerations for teachers wanting to incorporate spoken grammar activities into their own teaching and also focuses on six common features of spoken grammar, with practical activities and suggestions for teaching them in the language classroom. The hope is that this discussion of spoken grammar and its place…
Clique graphs and overlapping communities
NASA Astrophysics Data System (ADS)
Evans, T. S.
2010-12-01
It is shown how to construct a clique graph in which properties of cliques of a fixed order in a given graph are represented by vertices in a weighted graph. Various definitions and motivations for these weights are given. The detection of communities or clusters is used to illustrate how a clique graph may be exploited. In particular a benchmark network is shown where clique graphs find the overlapping communities accurately while vertex partition methods fail.
Do Amaral Marcio, B; Satomura, Y
1995-01-01
We describe one approach for natural language processing of medical texts that associates a semantic grammar with the SNOMED (Systematized Nomenclature of Medicine). Our research hypothesis is that the combination of the nomenclature's declarative knowledge with a formal grammar would create a scientific sublanguage embedded with medical knowledge that could be used for analyzing and formatting medical texts. This combination permitted the abstraction of templates we call "semantic patterns." These patterns represent both linguistic and medical knowledge, packed into a hybrid information format. We analyzed manually case reports described in the New England Journal of Medicine (NEJM) from 1985 to 1988 and extracted empirically a semantic grammar. Over 2,000 sentences were analyzed. About 160 structural semantic patterns were abstracted and included in the database of one parser. We tested the parser using reports from 1989 to 1990. Results show that this approach is efficient for processing, indexing, and structuring diverse parts of case reports narrative. The analyzed medical sentences are structured into a language-independent semantic frame format. We conclude that the association of semantic grammars with the SNOMED enabled the construction of a formal system for analysis and representation of clinical facts. The transformation of the structured information from its frame format into other representational schemes, like conceptual graphs, is straightforward. Another application includes the use of the formatted language-independent frame for telegraphic English-Japanese translations of medical sentences.
Universality in spectral statistics of open quantum graphs
NASA Astrophysics Data System (ADS)
Gutkin, B.; Osipov, V. Al.
2015-06-01
The quantum evolution maps of closed chaotic quantum graphs are unitary and known to have universal spectral correlations matching predictions of random matrix theory. In chaotic graphs with absorption the quantum maps become nonunitary. We show that their spectral statistics exhibit universality at the soft edges of the spectrum. The same spectral behavior is observed in many classical nonunitary ensembles of random matrices with rotationally invariant measures.
Proxy Graph: Visual Quality Metrics of Big Graph Sampling.
Nguyen, Quan-Hoang; Hong, Seok-Hee; Eades, Peter; Meidiana, Amyra
2017-02-24
Data sampling has been extensively studied for large scale graph mining. Many analyses and tasks become more efficient when performed on graph samples of much smaller size. The use of proxy objects is common in software engineering for analysis and interaction with heavy objects or systems. In this paper, we coin the term 'proxy graph' and empirically investigate how well a proxy graph visualization can represent a big graph. Our investigation focuses on proxy graphs obtained by sampling; this is one of the most common proxy approaches. Despite the plethora of data sampling studies, this is the first evaluation of sampling in the context of graph visualization. For an objective evaluation, we propose a new family of quality metrics for visual quality of proxy graphs. Our experiments cover popular sampling techniques. Our experimental results lead to guidelines for using sampling-based proxy graphs in visualization.
Higher-order graph wavelets and sparsity on circulant graphs
NASA Astrophysics Data System (ADS)
Kotzagiannidis, Madeleine S.; Dragotti, Pier Luigi
2015-08-01
The notion of a graph wavelet gives rise to more advanced processing of data on graphs due to its ability to operate in a localized manner, across newly arising data-dependency structures, with respect to the graph signal and underlying graph structure, thereby taking into consideration the inherent geometry of the data. In this work, we tackle the problem of creating graph wavelet filterbanks on circulant graphs for a sparse representation of certain classes of graph signals. The underlying graph can hereby be data-driven as well as fixed, for applications including image processing and social network theory, whereby clusters can be modelled as circulant graphs, respectively. We present a set of novel graph wavelet filter-bank constructions, which annihilate higher-order polynomial graph signals (up to a border effect) defined on the vertices of undirected, circulant graphs, and are localised in the vertex domain. We give preliminary results on their performance for non-linear graph signal approximation and denoising. Furthermore, we provide extensions to our previously developed segmentation-inspired graph wavelet framework for non-linear image approximation, by incorporating notions of smoothness and vanishing moments, which further improve performance compared to traditional methods.
Spectral properties of the hierarchical product of graphs
NASA Astrophysics Data System (ADS)
Skardal, Per Sebastian; Wash, Kirsti
2016-11-01
The hierarchical product of two graphs represents a natural way to build a larger graph out of two smaller graphs with less regular and therefore more heterogeneous structure than the Cartesian product. Here we study the eigenvalue spectrum of the adjacency matrix of the hierarchical product of two graphs. Introducing a coupling parameter describing the relative contribution of each of the two smaller graphs, we perform an asymptotic analysis for the full spectrum of eigenvalues of the adjacency matrix of the hierarchical product. Specifically, we derive the exact limit points for each eigenvalue in the limits of small and large coupling, as well as the leading-order relaxation to these values in terms of the eigenvalues and eigenvectors of the two smaller graphs. Given its central roll in the structural and dynamical properties of networks, we study in detail the Perron-Frobenius, or largest, eigenvalue. Finally, as an example application we use our theory to predict the epidemic threshold of the susceptible-infected-susceptible model on a hierarchical product of two graphs.
Spectral properties of the hierarchical product of graphs.
Skardal, Per Sebastian; Wash, Kirsti
2016-11-01
The hierarchical product of two graphs represents a natural way to build a larger graph out of two smaller graphs with less regular and therefore more heterogeneous structure than the Cartesian product. Here we study the eigenvalue spectrum of the adjacency matrix of the hierarchical product of two graphs. Introducing a coupling parameter describing the relative contribution of each of the two smaller graphs, we perform an asymptotic analysis for the full spectrum of eigenvalues of the adjacency matrix of the hierarchical product. Specifically, we derive the exact limit points for each eigenvalue in the limits of small and large coupling, as well as the leading-order relaxation to these values in terms of the eigenvalues and eigenvectors of the two smaller graphs. Given its central roll in the structural and dynamical properties of networks, we study in detail the Perron-Frobenius, or largest, eigenvalue. Finally, as an example application we use our theory to predict the epidemic threshold of the susceptible-infected-susceptible model on a hierarchical product of two graphs.
The Graph Laplacian and the Dynamics of Complex Networks
Thulasidasan, Sunil
2012-06-11
In this talk, we explore the structure of networks from a spectral graph-theoretic perspective by analyzing the properties of the Laplacian matrix associated with the graph induced by a network. We will see how the eigenvalues of the graph Laplacian relate to the underlying network structure and dynamics and provides insight into a phenomenon frequently observed in real world networks - the emergence of collective behavior from purely local interactions seen in the coordinated motion of animals and phase transitions in biological networks, to name a few.
Some results on the spectra of strongly regular graphs
NASA Astrophysics Data System (ADS)
Vieira, Luís António de Almeida; Mano, Vasco Moço
2016-06-01
Let G be a strongly regular graph whose adjacency matrix is A. We associate a real finite dimensional Euclidean Jordan algebra 𝒱, of rank three to the strongly regular graph G, spanned by I and the natural powers of A, endowed with the Jordan product of matrices and with the inner product as being the usual trace of matrices. Finally, by the analysis of the binomial Hadamard series of an element of 𝒱, we establish some inequalities on the parameters and on the spectrum of a strongly regular graph like those established in theorems 3 and 4.
Continuous-time quantum walks on directed bipartite graphs
NASA Astrophysics Data System (ADS)
Tödtli, Beat; Laner, Monika; Semenov, Jouri; Paoli, Beatrice; Blattner, Marcel; Kunegis, Jérôme
2016-11-01
This paper investigates continuous-time quantum walks on directed bipartite graphs based on a graph's adjacency matrix. We prove that on bipartite graphs, probability transport between the two node partitions can be completely suppressed by tuning a model parameter α . We provide analytic solutions to the quantum walks for the star and circulant graph classes that are valid for an arbitrary value of the number of nodes N , time t , and the model parameter α . We discuss quantitative and qualitative aspects of quantum walks based on directed graphs and their undirected counterparts. Numerical simulations of quantum walks on circulant graphs show complex interference phenomena and how complete suppression of transport is achieved near α =π /2 . By proving two mirror symmetries around α =0 and π /2 we show that these quantum walks have a period of π in α . We show that undirected edges lose their effect on the quantum walk at α =π /2 and present non-bipartite graphs that exhibit suppression of transport. Finally, we analytically compute the Hamiltonians of quantum walks on the directed ring graph.
Clifford Algebras, Random Graphs, and Quantum Random Variables
NASA Astrophysics Data System (ADS)
Schott, René; Staples, G. Stacey
2008-08-01
For fixed n > 0, the space of finite graphs on n vertices is canonically associated with an abelian, nilpotent-generated subalgebra of the Clifford algebra {C}l2n,2n which is canonically isomorphic to the 2n-particle fermion algebra. Using the generators of the subalgebra, an algebraic probability space of "Clifford adjacency matrices" associated with finite graphs is defined. Each Clifford adjacency matrix is a quantum random variable whose mth moment corresponds to the number of m-cycles in the graph G. Each matrix admits a canonical "quantum decomposition" into a sum of three algebraic random variables: a = aΔ + aΥ + aΛ, where aΔ is classical while aΥ and aΛ are quantum. Moreover, within the Clifford algebra context the NP problem of cycle enumeration is reduced to matrix multiplication, requiring no more than n4 Clifford (geo-metric) multiplications within the algebra.
Optimized Graph Search Using Multi-Level Graph Clustering
NASA Astrophysics Data System (ADS)
Kala, Rahul; Shukla, Anupam; Tiwari, Ritu
Graphs find a variety of use in numerous domains especially because of their capability to model common problems. The social networking graphs that are used for social networking analysis, a feature given by various social networking sites are an example of this. Graphs can also be visualized in the search engines to carry search operations and provide results. Various searching algorithms have been developed for searching in graphs. In this paper we propose that the entire network graph be clustered. The larger graphs are clustered to make smaller graphs. These smaller graphs can again be clustered to further reduce the size of graph. The search is performed on the smallest graph to identify the general path, which may be further build up to actual nodes by working on the individual clusters involved. Since many searches are carried out on the same graph, clustering may be done once and the data may be used for multiple searches over the time. If the graph changes considerably, only then we may re-cluster the graph.
Efficient Grammar Induction Algorithm with Parse Forests from Real Corpora
NASA Astrophysics Data System (ADS)
Kurihara, Kenichi; Kameya, Yoshitaka; Sato, Taisuke
The task of inducing grammar structures has received a great deal of attention. The reasons why researchers have studied are different; to use grammar induction as the first stage in building large treebanks or to make up better language models. However, grammar induction has inherent computational complexity. To overcome it, some grammar induction algorithms add new production rules incrementally. They refine the grammar while keeping their computational complexity low. In this paper, we propose a new efficient grammar induction algorithm. Although our algorithm is similar to algorithms which learn a grammar incrementally, our algorithm uses the graphical EM algorithm instead of the Inside-Outside algorithm. We report results of learning experiments in terms of learning speeds. The results show that our algorithm learns a grammar in constant time regardless of the size of the grammar. Since our algorithm decreases syntactic ambiguities in each step, our algorithm reduces required time for learning. This constant-time learning considerably affects learning time for larger grammars. We also reports results of evaluation of criteria to choose nonterminals. Our algorithm refines a grammar based on a nonterminal in each step. Since there can be several criteria to decide which nonterminal is the best, we evaluate them by learning experiments.
Subdominant pseudoultrametric on graphs
Dovgoshei, A A; Petrov, E A
2013-08-31
Let (G,w) be a weighted graph. We find necessary and sufficient conditions under which the weight w:E(G)→R{sup +} can be extended to a pseudoultrametric on V(G), and establish a criterion for the uniqueness of such an extension. We demonstrate that (G,w) is a complete k-partite graph, for k≥2, if and only if for any weight that can be extended to a pseudoultrametric, among all such extensions one can find the least pseudoultrametric consistent with w. We give a structural characterization of graphs for which the subdominant pseudoultrametric is an ultrametric for any strictly positive weight that can be extended to a pseudoultrametric. Bibliography: 14 titles.
Chen, J.; Safro, I.
2011-01-01
Measuring the connection strength between a pair of vertices in a graph is one of the most important concerns in many graph applications. Simple measures such as edge weights may not be sufficient for capturing the effects associated with short paths of lengths greater than one. In this paper, we consider an iterative process that smooths an associated value for nearby vertices, and we present a measure of the local connection strength (called the algebraic distance; see [D. Ron, I. Safro, and A. Brandt, Multiscale Model. Simul., 9 (2011), pp. 407-423]) based on this process. The proposed measure is attractive in that the process is simple, linear, and easily parallelized. An analysis of the convergence property of the process reveals that the local neighborhoods play an important role in determining the connectivity between vertices. We demonstrate the practical effectiveness of the proposed measure through several combinatorial optimization problems on graphs and hypergraphs.
Probabilistic Grammars for Natural Languages. Psychology Series.
ERIC Educational Resources Information Center
Suppes, Patrick
The purpose of this paper is to define the framework within which empirical investigations of probabilistic grammars can take place and to sketch how this attack can be made. The full presentation of empirical results will be left to other papers. In the detailed empirical work, the author has depended on the collaboration of E. Gammon and A.…
IN GRAMMAR'S FALL, WE SINNED ALL.
ERIC Educational Resources Information Center
TIBBETTS, A.M.
THROUGH THEIR LOSS OF FAITH IN TRADITIONAL GRAMMAR, MEN HAVE "SINNED" AND CONTRIBUTED SLIGHTLY BUT IMPORTANTLY TO THE CREATION OF AN AMORAL AND RELATIVISTIC SOCIETY. PROMPTED BY THE SIN OF INTELLECTUAL PRIDE, SOME LINGUISTS SEEM TO ASSUME THAT GRAMMATICAL PROBLEMS CAN BE SOLVED BY RATIOCINATION ALONE. IGNORANCE OF THE PAST--ANOTHER SIN--AND…
A Reference Grammar of Spoken Kannada.
ERIC Educational Resources Information Center
Schiffman, Harold
This reference grammar is a description of the speech of educated people of the Bangalore/Mysore area of Karnataka State in South India. This particular dialect is used in films and, to some extent, on the radio. The four sections of the book deal with: (1) phonology, (2) the noun phrase, (3) the verb phrase, and (4) syntax. Each item that is…
A Grammar Library for Information Structure
ERIC Educational Resources Information Center
Song, Sanghoun
2014-01-01
This dissertation makes substantial contributions to both the theoretical and computational treatment of information structure, with an eye toward creating natural language processing applications such as multilingual machine translation systems. The aim of the present dissertation is to create a grammar library of information structure for the…
A DESCRIPTIVE INDONESIAN GRAMMAR--PRELIMINARY EDITION.
ERIC Educational Resources Information Center
DYEN, ISIDORE
THIS PRELIMINARY EDITION COMPRISES A DESCRIPTIVE GRAMMAR OF INDONESIAN (BAHASA INDONESIA), THE OFFICIAL LANGUAGE OF THE REPUBLIC OF INDONESIA. THE THREE SECTIONS--PHONOLOGY, SYNTAX, AND MORPHOLOGY--PRESENT A COMPREHENSIVE LINGUISTIC ANALYSIS OF INDONESIAN, WITH OCCASIONAL CONTRASTIVE REFERENCE TO MALAY, JAVANESE, SUNDANESE, AND SUMATRAN. THIS…
Grammar and Syntax: The Student's Perspective.
ERIC Educational Resources Information Center
Vavra, Ed
1987-01-01
Argues that problems in teaching grammar stem from failure to help students develop, as opposed to memorize, grammatical concepts. Recommends discussion of style and vocabulary, student stylistic analysis of their own writing, and deciphering syntactic use, not just definition, of parts of speech. Suggests that such training should begin in…
Epilogue: Dynamic Morphosyntax in Functional Discourse Grammar
ERIC Educational Resources Information Center
Velasco, Daniel Garcia; Hengeveld, Kees; Mackenzie, J. Lachlan
2012-01-01
This epilogue addresses the most important topics and challenges for the Morphosyntactic Level in Functional Discourse Grammar that have been raised in the articles in this Special Issue. We begin by exploring the differences between the Morphosyntactic Level in FDG and the treatment of morphosyntactic phenomena in other linguistic frameworks. We…
Grammar Schools: Brief Flowering of Social Mobility?
ERIC Educational Resources Information Center
Barker, Bernard
2012-01-01
Grammar schools are increasingly remembered, especially by right-wing ideologues, as the agents of a "brief flowering" of post-war social mobility. This article presents statistical, documentary and interview evidence of secondary education in the eleven plus era, and finds nothing to justify the claim that selective schools produced a general…
Grammar Schools: Where Are We Now?
ERIC Educational Resources Information Center
Tulloch, Margaret
2015-01-01
Apart from one amalgamation there are as many grammar schools in England as when Labour took office in 1997. Selection at age 11 still influences English education and unless there are changes its effect is likely to increase. Legislation introduced in 1998 which could have ended selection had no effect. The pressure from the right-wing minority…
Yes, We Still Need Universal Grammar
ERIC Educational Resources Information Center
Lidz, Jeffrey; Gleitman, Lila R.
2004-01-01
In a recent paper [Lidz, J., Gleitman, H., & Gleitman, L. (2003). Understanding how input matters: Verb learning and the footprint of universal grammar. "Cognition," 87, 151-178], we provided cross-linguistic evidence in favor of the following linked assertions: (i) Verb argument structure is a correlate of verb meaning; (ii) However, argument…
Using Technology for Teaching Arabic Language Grammar
ERIC Educational Resources Information Center
Arrabtah, Adel; Nusour, Tayseer
2012-01-01
This study investigates the effect of using technology such as CD-ROM, computers, and internet to teach Arabic language grammar to students at Princess Alia University College at Al-Balqa University. The sample of the study consisted of 122 third year female students; (64) for the experimental group and (58) for the control group. The subjects of…
Teaching Grammar as a Humanities Course.
ERIC Educational Resources Information Center
Kliman, Bernice W.
Nassau Community College (NCC) offers a grammar course as a humanities option that may be taken instead of a literature course. The approach to the course incorporates reader-response theory, feminist criticism, new historicism, and journal writing as the key means for enabling students to learn. Each student has a notebook divided into sections…
Multiple Grammars: Old Wine in Old Bottles
ERIC Educational Resources Information Center
Sorace, Antonella
2014-01-01
Amaral and Roeper (this issue; henceforth A&R) argue that all speakers -- regardless of whether monolingual or bilingual -- have multiple grammars in their mental language representations. They further claim that this simple assumption can explain many things: optionality in second language (L2) language behaviour, multilingualism, language…
Visual Feature Learning in Artificial Grammar Classification
ERIC Educational Resources Information Center
Chang, Grace Y.; Knowlton, Barbara J.
2004-01-01
The Artificial Grammar Learning task has been used extensively to assess individuals' implicit learning capabilities. Previous work suggests that participants implicitly acquire rule-based knowledge as well as exemplar-specific knowledge in this task. This study investigated whether exemplar-specific knowledge acquired in this task is based on the…
A BRIEF HINDI REFERENCE GRAMMAR. PRELIMINARY VERSION.
ERIC Educational Resources Information Center
GUMPERZ, JOHN J.; MISRA, VIDYA NIWAS
THIS BRIEF OUTLINE OF HINDI PHONOLOGY AND GRAMMAR IS INTENDED FOR FIRST AND SECOND YEAR STUDENTS OF HINDI WHO HAVE SOME PREVIOUS KNOWLEDGE OF THE ORAL AND WRITTEN LANGUAGE BUT WHO MAY HAVE HAD NO PREVIOUS TRAINING IN LINGUISTIC TERMINOLOGY. THE AUTHORS HAVE THEREFORE EMPHASIZED SIMPLICITY AND READABILITY RATHER THAN EXHAUSTIVENESS OR ORIGINALITY…
English Grammar Made Difficult! Volume 1.
ERIC Educational Resources Information Center
Taylor, Lee Roger, Jr.
This volume contains the first 13 of 28 individualized programmed units on basic English grammar, intended for use in developmental or guided studies for students with deficiences in English. The units may be used separately or in sequence as a comprehensive course. The approach taken is neither wholly traditional (prescriptive) or…
A Progressive Grammar of the Tamil Language.
ERIC Educational Resources Information Center
Arden, A. H.; Clayton, A. C.
The first chapter of this grammar of prose Tamil introduces the alphabet and orthography. Following chapters deal with parts of speech and verb constructions. A final chapter deals with colloquialisms and foreign words. Appended are lists of abbreviations, grammatical and temporal terms, and other information useful to the student, as well as a…
Multiple Grammars and Second Language Representation
ERIC Educational Resources Information Center
Amaral, Luiz; Roeper, Tom
2014-01-01
This paper presents an extension of the Multiple Grammars Theory (Roeper, 1999) to provide a formal mechanism that can serve as a generative-based alternative to current descriptive models of interlanguage. The theory extends historical work by Kroch and Taylor (1997), and has been taken into a computational direction by Yang (2003). The proposal…
Education and the Grammar of Assent
ERIC Educational Resources Information Center
Harris, Suzy
2015-01-01
John Henry Newman is probably known best for "The Idea of a University." In his most philosophical work, "An Essay in Aid of a Grammar of Assent," however, he undertakes a detailed investigation of different ways of knowing and understanding in a manner that is of clear pertinence for philosophical enquiry into education. He…
Auditory and Articulatory Aspects of Grammar.
ERIC Educational Resources Information Center
Gruber, Frederic A.
The author addresses the need for a new acoustic recognition strategy, extending the position that any adequate grammar of a language must distinguish between auditory and articulatory knowledge. Reviewing the existing literature and theories of language and its acquisition, the author discusses their limitations and inadequacies in accounting for…
ERIC Educational Resources Information Center
Lardiere, Donna
2014-01-01
This article offers commentary on the Multiple Grammars (MG) language acquisition theory proposed by Luiz Amaral and Tom Roeper in this issue. It argues that more precise definitions are needed for the terms "rule," "simple," and "productive." Topics discussed include Amaral and Roeper's verb second (V2) rule,…
A SHORT SKETCH OF TAJIK GRAMMAR.
ERIC Educational Resources Information Center
RASTORGUEVA, V.S.
PART OF A SERIES OF FOUR RUSSIAN-ENGLISH TRANSLATIONS OF GRAMMARS OF IRANIAN LANGUAGES, THIS BOOKLET DESCRIBES THE TAJIK LANGUAGE OF THE INHABITANTS OF TAJIK SSR, AND IS THE FIRST TO APPEAR IN ENGLISH. (THE ORIGINAL TEXT WAS A SUPPLEMENT TO THE RAHIMI-USPENSKAYA "TAJIK-RUSSIAN DICTIONARY," MOSCOW, 1954.) ALL TAJIK FORMS ARE GIVEN IN…
2002-04-15
path from a to (3 together with an edge (3 -+ a is called a (fully) directed cycle . An anterior path from a to f3 together with an edge (3 -+ a is...called a partially directed cycle . A directed acyclic graph (DA G) is a mixed graph in which all edges are directed, and there are no directed cycles . 3...regardless of whether a and "’f are adjacent). There are no directed cycles or pa’ltially directed cycles . 9 to Proof: follows because condition rules
1990-03-01
returns from a frequency swept microwave signal centred on the ship being measured. Each data set consists of 255 equally spaced points which represent...overlaid one over the other, or split into three windows where the hard black-lined top graph is the back chart and the thinner-lined lower graph is the...Borland’s Turbo Pascal Version 1.0 (Borland 1986) to edit and compile the main source code. Menu details, window specification, dialogue box and item
Graphing Calculator Mini Course
NASA Technical Reports Server (NTRS)
Karnawat, Sunil R.
1996-01-01
The "Graphing Calculator Mini Course" project provided a mathematically-intensive technologically-based summer enrichment workshop for teachers of American Indian students on the Turtle Mountain Indian Reservation. Eleven such teachers participated in the six-day workshop in summer of 1996 and three Sunday workshops in the academic year. The project aimed to improve science and mathematics education on the reservation by showing teachers effective ways to use high-end graphing calculators as teaching and learning tools in science and mathematics courses at all levels. In particular, the workshop concentrated on applying TI-82's user-friendly features to understand the various mathematical and scientific concepts.
Graph ensemble boosting for imbalanced noisy graph stream classification.
Pan, Shirui; Wu, Jia; Zhu, Xingquan; Zhang, Chengqi
2015-05-01
Many applications involve stream data with structural dependency, graph representations, and continuously increasing volumes. For these applications, it is very common that their class distributions are imbalanced with minority (or positive) samples being only a small portion of the population, which imposes significant challenges for learning models to accurately identify minority samples. This problem is further complicated with the presence of noise, because they are similar to minority samples and any treatment for the class imbalance may falsely focus on the noise and result in deterioration of accuracy. In this paper, we propose a classification model to tackle imbalanced graph streams with noise. Our method, graph ensemble boosting, employs an ensemble-based framework to partition graph stream into chunks each containing a number of noisy graphs with imbalanced class distributions. For each individual chunk, we propose a boosting algorithm to combine discriminative subgraph pattern selection and model learning as a unified framework for graph classification. To tackle concept drifting in graph streams, an instance level weighting mechanism is used to dynamically adjust the instance weight, through which the boosting framework can emphasize on difficult graph samples. The classifiers built from different graph chunks form an ensemble for graph stream classification. Experiments on real-life imbalanced graph streams demonstrate clear benefits of our boosting design for handling imbalanced noisy graph stream.
ERIC Educational Resources Information Center
Sokol, William
In this autoinstructional packet, the student is given an experimental situation which introduces him to the process of graphing. The lesson is presented for secondary school students in chemistry. Algebra I and a Del Mod System program (indicated as SE 018 020) are suggested prerequisites for the use of this program. Behavioral objectives are…
ERIC Educational Resources Information Center
Pitts Bannister, Vanessa R.; Jamar, Idorenyin; Mutegi, Jomo W.
2007-01-01
In this article, the learning progress of one fifth-grade student is examined with regard to the development of her graph interpretation skills as she participated in the Junior Science Institute (JSI), a two-week, science intensive summer camp in which participants engaged in microbiology research and application. By showcasing the student's…
Simmons, G.J.
1985-01-01
Given a graph G and an ordering phi of the vertices, V(G), we define a parsimonious proper coloring (PPC) of V(G) under phi to be a proper coloring of V(G) in the order phi, where a new color is introduced only when a vertex cannot be properly colored in its order with any of the colors already used.
2013-02-19
This library is used in several LLNL projects, including STAT (the Stack Trace Analysis Tool for scalable debugging) and some modules in P^nMPI (a tool MPI tool infrastructure). It can also be used standalone for creating and manipulationg graphs, but its API is primarily tuned to support these other projects
Coloring geographical threshold graphs
Bradonjic, Milan; Percus, Allon; Muller, Tobias
2008-01-01
We propose a coloring algorithm for sparse random graphs generated by the geographical threshold graph (GTG) model, a generalization of random geometric graphs (RGG). In a GTG, nodes are distributed in a Euclidean space, and edges are assigned according to a threshold function involving the distance between nodes as well as randomly chosen node weights. The motivation for analyzing this model is that many real networks (e.g., wireless networks, the Internet, etc.) need to be studied by using a 'richer' stochastic model (which in this case includes both a distance between nodes and weights on the nodes). Here, we analyze the GTG coloring algorithm together with the graph's clique number, showing formally that in spite of the differences in structure between GTG and RGG, the asymptotic behavior of the chromatic number is identical: {chi}1n 1n n / 1n n (1 + {omicron}(1)). Finally, we consider the leading corrections to this expression, again using the coloring algorithm and clique number to provide bounds on the chromatic number. We show that the gap between the lower and upper bound is within C 1n n / (1n 1n n){sup 2}, and specify the constant C.
ERIC Educational Resources Information Center
Nemirovsky, Ricardo; Tierney, Cornelia; Wright, Tracy
1998-01-01
Analyzed two children's use of a computer-based motion detector to make sense of symbolic expressions (Cartesian graphs). Found three themes: (1) tool perspectives, efforts to understand graphical responses to body motion; (2) fusion, emergent ways of talking and behaving that merge symbols and referents; and (3) graphical spaces, when changing…
ERIC Educational Resources Information Center
Donley, H. Edward; George, Elizabeth Ann
1993-01-01
Demonstrates how to construct rational, exponential, and sinusoidal functions that appear normal on one scale but exhibit interesting hidden behavior when viewed on another scale. By exploring these examples, students learn the importance of scale, window size, and resolution effects in computer and calculator graphing. (MAZ)
ERIC Educational Resources Information Center
Krueger, Tom
2010-01-01
In this article, the author shares one effective lesson idea on straight line graphs that he applied in his lower ability Y9 class. The author wanted something interesting for his class to do, something that was fun and engaging with direct feedback, and something that worked because someone else had tried it before. In a word, the author admits…
Temporal Representation in Semantic Graphs
Levandoski, J J; Abdulla, G M
2007-08-07
A wide range of knowledge discovery and analysis applications, ranging from business to biological, make use of semantic graphs when modeling relationships and concepts. Most of the semantic graphs used in these applications are assumed to be static pieces of information, meaning temporal evolution of concepts and relationships are not taken into account. Guided by the need for more advanced semantic graph queries involving temporal concepts, this paper surveys the existing work involving temporal representations in semantic graphs.
Quantum walks on quotient graphs
Krovi, Hari; Brun, Todd A.
2007-06-15
A discrete-time quantum walk on a graph {gamma} is the repeated application of a unitary evolution operator to a Hilbert space corresponding to the graph. If this unitary evolution operator has an associated group of symmetries, then for certain initial states the walk will be confined to a subspace of the original Hilbert space. Symmetries of the original graph, given by its automorphism group, can be inherited by the evolution operator. We show that a quantum walk confined to the subspace corresponding to this symmetry group can be seen as a different quantum walk on a smaller quotient graph. We give an explicit construction of the quotient graph for any subgroup H of the automorphism group and illustrate it with examples. The automorphisms of the quotient graph which are inherited from the original graph are the original automorphism group modulo the subgroup H used to construct it. The quotient graph is constructed by removing the symmetries of the subgroup H from the original graph. We then analyze the behavior of hitting times on quotient graphs. Hitting time is the average time it takes a walk to reach a given final vertex from a given initial vertex. It has been shown in earlier work [Phys. Rev. A 74, 042334 (2006)] that the hitting time for certain initial states of a quantum walks can be infinite, in contrast to classical random walks. We give a condition which determines whether the quotient graph has infinite hitting times given that they exist in the original graph. We apply this condition for the examples discussed and determine which quotient graphs have infinite hitting times. All known examples of quantum walks with hitting times which are short compared to classical random walks correspond to systems with quotient graphs much smaller than the original graph; we conjecture that the existence of a small quotient graph with finite hitting times is necessary for a walk to exhibit a quantum speedup.
Reproducibility of graph metrics of human brain structural networks.
Duda, Jeffrey T; Cook, Philip A; Gee, James C
2014-01-01
Recent interest in human brain connectivity has led to the application of graph theoretical analysis to human brain structural networks, in particular white matter connectivity inferred from diffusion imaging and fiber tractography. While these methods have been used to study a variety of patient populations, there has been less examination of the reproducibility of these methods. A number of tractography algorithms exist and many of these are known to be sensitive to user-selected parameters. The methods used to derive a connectivity matrix from fiber tractography output may also influence the resulting graph metrics. Here we examine how these algorithm and parameter choices influence the reproducibility of proposed graph metrics on a publicly available test-retest dataset consisting of 21 healthy adults. The dice coefficient is used to examine topological similarity of constant density subgraphs both within and between subjects. Seven graph metrics are examined here: mean clustering coefficient, characteristic path length, largest connected component size, assortativity, global efficiency, local efficiency, and rich club coefficient. The reproducibility of these network summary measures is examined using the intraclass correlation coefficient (ICC). Graph curves are created by treating the graph metrics as functions of a parameter such as graph density. Functional data analysis techniques are used to examine differences in graph measures that result from the choice of fiber tracking algorithm. The graph metrics consistently showed good levels of reproducibility as measured with ICC, with the exception of some instability at low graph density levels. The global and local efficiency measures were the most robust to the choice of fiber tracking algorithm.
Recursive Feature Extraction in Graphs
2014-08-14
ReFeX extracts recursive topological features from graph data. The input is a graph as a csv file and the output is a csv file containing feature values for each node in the graph. The features are based on topological counts in the neighborhoods of each nodes, as well as recursive summaries of neighbors' features.
Xuan, Junyu; Lu, Jie; Zhang, Guangquan; Luo, Xiangfeng
2015-12-01
Graph mining has been a popular research area because of its numerous application scenarios. Many unstructured and structured data can be represented as graphs, such as, documents, chemical molecular structures, and images. However, an issue in relation to current research on graphs is that they cannot adequately discover the topics hidden in graph-structured data which can be beneficial for both the unsupervised learning and supervised learning of the graphs. Although topic models have proved to be very successful in discovering latent topics, the standard topic models cannot be directly applied to graph-structured data due to the "bag-of-word" assumption. In this paper, an innovative graph topic model (GTM) is proposed to address this issue, which uses Bernoulli distributions to model the edges between nodes in a graph. It can, therefore, make the edges in a graph contribute to latent topic discovery and further improve the accuracy of the supervised and unsupervised learning of graphs. The experimental results on two different types of graph datasets show that the proposed GTM outperforms the latent Dirichlet allocation on classification by using the unveiled topics of these two models to represent graphs.
Mining and Indexing Graph Databases
ERIC Educational Resources Information Center
Yuan, Dayu
2013-01-01
Graphs are widely used to model structures and relationships of objects in various scientific and commercial fields. Chemical molecules, proteins, malware system-call dependencies and three-dimensional mechanical parts are all modeled as graphs. In this dissertation, we propose to mine and index those graph data to enable fast and scalable search.…
ERIC Educational Resources Information Center
Hopkins, Brian
2004-01-01
The interconnected world of actors and movies is a familiar, rich example for graph theory. This paper gives the history of the "Kevin Bacon Game" and makes extensive use of a Web site to analyze the underlying graph. The main content is the classroom development of the weighted average to determine the best choice of "center" for the graph. The…
ERIC Educational Resources Information Center
Skurnick, Ronald; Davi, Charles; Skurnick, Mia
2005-01-01
Since 1952, several well-known graph theorists have proven numerous results regarding Hamiltonian graphs. In fact, many elementary graph theory textbooks contain the theorems of Ore, Bondy and Chvatal, Chvatal and Erdos, Posa, and Dirac, to name a few. In this note, the authors state and prove some propositions of their own concerning Hamiltonian…
Winlaw, Manda; De Sterck, Hans; Sanders, Geoffrey
2015-10-26
In very simple terms a network can be de ned as a collection of points joined together by lines. Thus, networks can be used to represent connections between entities in a wide variety of elds including engi- neering, science, medicine, and sociology. Many large real-world networks share a surprising number of properties, leading to a strong interest in model development research and techniques for building synthetic networks have been developed, that capture these similarities and replicate real-world graphs. Modeling these real-world networks serves two purposes. First, building models that mimic the patterns and prop- erties of real networks helps to understand the implications of these patterns and helps determine which patterns are important. If we develop a generative process to synthesize real networks we can also examine which growth processes are plausible and which are not. Secondly, high-quality, large-scale network data is often not available, because of economic, legal, technological, or other obstacles [7]. Thus, there are many instances where the systems of interest cannot be represented by a single exemplar network. As one example, consider the eld of cybersecurity, where systems require testing across diverse threat scenarios and validation across diverse network structures. In these cases, where there is no single exemplar network, the systems must instead be modeled as a collection of networks in which the variation among them may be just as important as their common features. By developing processes to build synthetic models, so-called graph generators, we can build synthetic networks that capture both the essential features of a system and realistic variability. Then we can use such synthetic graphs to perform tasks such as simulations, analysis, and decision making. We can also use synthetic graphs to performance test graph analysis algorithms, including clustering algorithms and anomaly detection algorithms.
Bounds for percolation thresholds on directed and undirected graphs
NASA Astrophysics Data System (ADS)
Hamilton, Kathleen; Pryadko, Leonid
2015-03-01
Percolation theory is an efficient approach to problems with strong disorder, e.g., in quantum or classical transport, composite materials, and diluted magnets. Recently, the growing role of big data in scientific and industrial applications has led to a renewed interest in graph theory as a tool for describing complex connections in various kinds of networks: social, biological, technological, etc. In particular, percolation on graphs has been used to describe internet stability, spread of contagious diseases and computer viruses; related models describe market crashes and viral spread in social networks. We consider site-dependent percolation on directed and undirected graphs, and present several exact bounds for location of the percolation transition in terms of the eigenvalues of matrices associated with graphs, including the adjacency matrix and the Hashimoto matrix used to enumerate non-backtracking walks. These bounds correspond t0 a mean field approximation and become asymptotically exact for graphs with no short cycles. We illustrate this convergence numerically by simulating percolation on several families of graphs with different cycle lengths. This research was supported in part by the NSF Grant PHY-1416578 and by the ARO Grant W911NF-11-1-0027.
Cell-graph mining for breast tissue modeling and classification.
Bilgin, Cagatay; Demir, Cigdem; Nagi, Chandandeep; Yener, Bulent
2007-01-01
We consider the problem of automated cancer diagnosis in the context of breast tissues. We present graph theoretical techniques that identify and compute quantitative metrics for tissue characterization and classification. We segment digital images of histopatological tissue samples using k-means algorithm. For each segmented image we generate different cell-graphs using positional coordinates of cells and surrounding matrix components. These cell-graphs have 500-2000 cells(nodes) with 1000-10000 links depending on the tissue and the type of cell-graph being used. We calculate a set of global metrics from cell-graphs and use them as the feature set for learning. We compare our technique, hierarchical cell graphs, with other techniques based on intensity values of images, Delaunay triangulation of the cells, the previous technique we proposed for brain tissue images and with the hybrid approach that we introduce in this paper. Among the compared techniques, hierarchical-graph approach gives 81.8% accuracy whereas we obtain 61.0%, 54.1% and 75.9% accuracy with intensity-based features, Delaunay triangulation and our previous technique, respectively.
ERIC Educational Resources Information Center
Lehmann, Volkmar
1979-01-01
Defines the practical functions of various types of grammars, and theoretical functions of linguistic grammars. Points out some differences between the two (stressing contrast between native and foreign languages), as well as differences in defining, finality, or variation of categories, and in psycho- and sociolinguistic components. (IFS/WGA)
Orthocomplemented complete lattices and graphs
NASA Astrophysics Data System (ADS)
Ollech, Astrid
1995-08-01
The problem I consider originates from Dörfler, who found a construction to assign an Orthocomplemented lattice H(G) to a graph G. By Dörfler it is known that for every finite Orthocomplemented lattice L there exists a graph G such that H(G)=L. Unfortunately, we can find more than one graph G with this property, i.e., orthocomplemented lattices which belong to different graphs can be isomorphic. I show some conditions under which two graphs have the same orthocomplemented lattice.
Role of selective attention in artificial grammar learning.
Tanaka, Daisuke; Kiyokawa, Sachiko; Yamada, Ayumi; Dienes, Zoltán; Shigemasu, Kazuo
2008-12-01
To investigate the role of selective attention in artificial grammar (AG) learning, participants were presented with "GLOCAL" strings-that is, chains of compound global and local letters. The global and local levels instantiated different grammars. The results of this experiment revealed that participants learned only the grammar for the level to which they attended. The participants were not even able to choose presented but unattended strings themselves. These results show that selective attention plays a critical role in AG learning.
Visual grammars and their neural networks
NASA Astrophysics Data System (ADS)
Mjolsness, Eric
1992-07-01
We exhibit a systematic way to derive neural nets for vision problems. It involves formulating a vision problem as Bayesian inference or decision on a comprehensive model of the visual domain given by a probabilistic grammar. A key feature of this grammar is the way in which it eliminates model information, such as object labels, as it produces an image; correspondence problems and other noise removal tasks result. The neural nets that arise most directly are generalized assignment networks. Also there are transformations which naturally yield improved algorithms such as correlation matching in scale space and the Frameville neural nets for high-level vision. Networks derived this way generally have objective functions with spurious local minima; such minima may commonly be avoided by dynamics that include deterministic annealing, for example recent improvements to Mean Field Theory dynamics. The grammatical method of neural net design allows domain knowledge to enter from all levels of the grammar, including `abstract' levels remote from the final image data, and may permit new kinds of learning as well.
2010-12-02
evaluating the function ΘP (A) for any fixed A,P is equivalent to solving the so-called Quadratic Assignment Problem ( QAP ), and thus we can employ various...tractable linear programming, spectral, and SDP relaxations of QAP [40, 11, 33]. In particular we discuss recent work [14] on exploiting group...symmetry in SDP relaxations of QAP , which is useful for approximately computing elementary convex graph invariants in many interesting cases. Finally in
ERIC Educational Resources Information Center
Syed, M. Qasim; Lovatt, Ian
2014-01-01
This paper is an addition to the series of papers on the exponential function begun by Albert Bartlett. In particular, we ask how the graph of the exponential function y = e[superscript -t/t] would appear if y were plotted versus ln t rather than the normal practice of plotting ln y versus t. In answering this question, we find a new way to…
An incremental interactive algorithm for regular grammar inference
Parekh, R.; Honavar, V.
1996-12-31
Grammar inference, a problem with many applications in pattern recognition and language learning, is defined as follows: For an unknown grammar G, given a finite set of positive examples S{sup +} that belong to L(G), and possibly a finite set of negative examples S{sup -}, infer a grammar G* equivalent to G. Different restrictions on S{sup +} and S{sup -} and the interaction of the learner with the teacher or the environment give rise to different variants of this task. We present an interactive incremental algorithm for inference of a finite state automaton (FSA) corresponding to an unknown regular grammar.
Lung segmentation with graph cuts: Graph size versus performance
NASA Astrophysics Data System (ADS)
Pazokifard, Banafsheh; Sowmya, Arcot
2013-10-01
The effect of graph size on segmentation performance and speed is investigated, where segmentation is based on the graph cuts algorithm. The study is performed on lung extraction in 50 complete multi detector computed tomography (MDCT) datasets, and a fully automatic procedure. The experiments were performed on different graph sizes for both 2-D (4 and 8 neighbours) and 3-D (6 and 26 neighbours) graphs. Five slices from each segmented dataset were compared to the reference delineation provided by a radiologist. Our evaluations highlight the fact that when medical image segmentation is performed using graph cuts, increasing graph and neighbourhood connection size does not necessarily improve the segmentation performance, but also increase the running time dramatically.
Evaluation of Graph Pattern Matching Workloads in Graph Analysis Systems
Hong, Seokyong; Lee, Sangkeun; Lim, Seung-Hwan; Sukumar, Sreenivas Rangan; Vatsavai, Raju
2016-01-01
Graph analysis has emerged as a powerful method for data scientists to represent, integrate, query, and explore heterogeneous data sources. As a result, graph data management and mining became a popular area of research, and led to the development of plethora of systems in recent years. Unfortunately, the number of emerging graph analysis systems and the wide range of applications, coupled with a lack of apples-to-apples comparisons, make it difficult to understand the trade-offs between different systems and the graph operations for which they are designed. A fair comparison of these systems is a challenging task for the following reasons: multiple data models, non-standardized serialization formats, various query interfaces to users, and diverse environments they operate in. To address these key challenges, in this paper we present a new benchmark suite by extending the Lehigh University Benchmark (LUBM) to cover the most common capabilities of various graph analysis systems. We provide the design process of the benchmark, which generalizes the workflow for data scientists to conduct the desired graph analysis on different graph analysis systems. Equipped with this extended benchmark suite, we present performance comparison for nine subgraph pattern retrieval operations over six graph analysis systems, namely NetworkX, Neo4j, Jena, Titan, GraphX, and uRiKA. Through the proposed benchmark suite, this study reveals both quantitative and qualitative findings in (1) implications in loading data into each system; (2) challenges in describing graph patterns for each query interface; and (3) different sensitivity of each system to query selectivity. We envision that this study will pave the road for: (i) data scientists to select the suitable graph analysis systems, and (ii) data management system designers to advance graph analysis systems.
Classification of group behaviors in social media via social behavior grammars
NASA Astrophysics Data System (ADS)
Levchuk, Georgiy; Getoor, Lise; Smith, Marc
2014-06-01
The increasing use of online collaboration and information sharing in the last decade has resulted in explosion of criminal and anti-social activities in online communities. Detection of such behaviors are of interest to commercial enterprises who want to guard themselves from cyber criminals, and the military intelligence analysts who desire to detect and counteract cyberwars waged by adversarial states and organizations. The most challenging behaviors to detect are those involving multiple individuals who share actions and roles in the hostile activities and individually appear benign. To detect these behaviors, the theories of group behaviors and interactions must be developed. In this paper we describe our exploration of the data from collaborative social platform to categorize the behaviors of multiple individuals. We applied graph matching algorithms to explore consistent social interactions. Our research led us to a conclusion that complex collaborative behaviors can be modeled and detected using a concept of group behavior grammars, in a manner analogous to natural language processing. These grammars capture constraints on how people take on roles in virtual environments, form groups, and interact over time, providing the building blocks for scalable and accurate multi-entity interaction analysis and social behavior hypothesis testing.
NASA Astrophysics Data System (ADS)
Shahid, Nauman; Perraudin, Nathanael; Kalofolias, Vassilis; Puy, Gilles; Vandergheynst, Pierre
2016-06-01
Mining useful clusters from high dimensional data has received significant attention of the computer vision and pattern recognition community in the recent years. Linear and non-linear dimensionality reduction has played an important role to overcome the curse of dimensionality. However, often such methods are accompanied with three different problems: high computational complexity (usually associated with the nuclear norm minimization), non-convexity (for matrix factorization methods) and susceptibility to gross corruptions in the data. In this paper we propose a principal component analysis (PCA) based solution that overcomes these three issues and approximates a low-rank recovery method for high dimensional datasets. We target the low-rank recovery by enforcing two types of graph smoothness assumptions, one on the data samples and the other on the features by designing a convex optimization problem. The resulting algorithm is fast, efficient and scalable for huge datasets with O(nlog(n)) computational complexity in the number of data samples. It is also robust to gross corruptions in the dataset as well as to the model parameters. Clustering experiments on 7 benchmark datasets with different types of corruptions and background separation experiments on 3 video datasets show that our proposed model outperforms 10 state-of-the-art dimensionality reduction models. Our theoretical analysis proves that the proposed model is able to recover approximate low-rank representations with a bounded error for clusterable data.
Battaglia, Francesco P.; Pennartz, Cyriel M. A.
2011-01-01
After acquisition, memories underlie a process of consolidation, making them more resistant to interference and brain injury. Memory consolidation involves systems-level interactions, most importantly between the hippocampus and associated structures, which takes part in the initial encoding of memory, and the neocortex, which supports long-term storage. This dichotomy parallels the contrast between episodic memory (tied to the hippocampal formation), collecting an autobiographical stream of experiences, and semantic memory, a repertoire of facts and statistical regularities about the world, involving the neocortex at large. Experimental evidence points to a gradual transformation of memories, following encoding, from an episodic to a semantic character. This may require an exchange of information between different memory modules during inactive periods. We propose a theory for such interactions and for the formation of semantic memory, in which episodic memory is encoded as relational data. Semantic memory is modeled as a modified stochastic grammar, which learns to parse episodic configurations expressed as an association matrix. The grammar produces tree-like representations of episodes, describing the relationships between its main constituents at multiple levels of categorization, based on its current knowledge of world regularities. These regularities are learned by the grammar from episodic memory information, through an expectation-maximization procedure, analogous to the inside–outside algorithm for stochastic context-free grammars. We propose that a Monte-Carlo sampling version of this algorithm can be mapped on the dynamics of “sleep replay” of previously acquired information in the hippocampus and neocortex. We propose that the model can reproduce several properties of semantic memory such as decontextualization, top-down processing, and creation of schemata. PMID:21887143
Index statistical properties of sparse random graphs
NASA Astrophysics Data System (ADS)
Metz, F. L.; Stariolo, Daniel A.
2015-10-01
Using the replica method, we develop an analytical approach to compute the characteristic function for the probability PN(K ,λ ) that a large N ×N adjacency matrix of sparse random graphs has K eigenvalues below a threshold λ . The method allows to determine, in principle, all moments of PN(K ,λ ) , from which the typical sample-to-sample fluctuations can be fully characterized. For random graph models with localized eigenvectors, we show that the index variance scales linearly with N ≫1 for |λ |>0 , with a model-dependent prefactor that can be exactly calculated. Explicit results are discussed for Erdös-Rényi and regular random graphs, both exhibiting a prefactor with a nonmonotonic behavior as a function of λ . These results contrast with rotationally invariant random matrices, where the index variance scales only as lnN , with an universal prefactor that is independent of λ . Numerical diagonalization results confirm the exactness of our approach and, in addition, strongly support the Gaussian nature of the index fluctuations.
Exact numerical calculation of fixation probability and time on graphs.
Hindersin, Laura; Möller, Marius; Traulsen, Arne; Bauer, Benedikt
2016-12-01
The Moran process on graphs is a popular model to study the dynamics of evolution in a spatially structured population. Exact analytical solutions for the fixation probability and time of a new mutant have been found for only a few classes of graphs so far. Simulations are time-expensive and many realizations are necessary, as the variance of the fixation times is high. We present an algorithm that numerically computes these quantities for arbitrary small graphs by an approach based on the transition matrix. The advantage over simulations is that the calculation has to be executed only once. Building the transition matrix is automated by our algorithm. This enables a fast and interactive study of different graph structures and their effect on fixation probability and time. We provide a fast implementation in C with this note (Hindersin et al., 2016). Our code is very flexible, as it can handle two different update mechanisms (Birth-death or death-Birth), as well as arbitrary directed or undirected graphs.
ERIC Educational Resources Information Center
Plaza-Pust, Carolina
2008-01-01
Research over the last decades has shown that language development in its multiple forms is characterized by a succession of stable and unstable states. However, the variation observed is neither expected nor can it be accounted for on the basis of traditional learning concepts conceived of within the Universal Grammar (UG) paradigm. In this…
The Multiple Grammars Theory and the Nature of L2 Grammars
ERIC Educational Resources Information Center
Liceras, Juana M.
2014-01-01
This article offers the author's commentary on the Multiple Grammar (MG) language acquisition theory proposed by Luiz Amaral and Tom Roeper in the present issue and touches on other second language acquisition research. Topics discussed include the concept of second language (L2) optionality, a hypothesis regarding the acquisition of the…
1973-10-01
The theory of strongly regular graphs was introduced by Bose r7 1 in 1963, in connection with partial geometries and 2 class association schemes. One...non adjacent vertices is constant and equal to ~. We shall denote by ~(p) (reap.r(p)) the set of vertices adjacent (resp.non adjacent) to a vertex p...is the complement of .2’ if the set of vertices of ~ is the set of vertices of .2’ and if two vertices in .2’ are adjacent if and only if they were
Eigensolutions of dodecahedron graphs
NASA Astrophysics Data System (ADS)
Ghosh, Piyali; Karmakar, Somnath; Mandal, Bholanath
2014-02-01
Eigensolutions of 20-vertex cage (i.e. dodecahedron) have been determined with the use of fivefold rotational symmetry. For homo-dodecahedron the eigensolutions become analytical but for the hetero-dodecahedron having two different types of atoms ((C,N),(C,B),(B,N)) the eigensolutions are found to be factored out into five 4-degree polynomials with one corresponding to nondegenerate and other four corresponding to two degenerate eigensolutions. Eigenspectra and total π-electron energies of homo- and hetero-dodecahedron graphs have been calculated.
NASA Technical Reports Server (NTRS)
Burleigh, Scott C.
2011-01-01
Contact Graph Routing (CGR) is a dynamic routing system that computes routes through a time-varying topology of scheduled communication contacts in a network based on the DTN (Delay-Tolerant Networking) architecture. It is designed to enable dynamic selection of data transmission routes in a space network based on DTN. This dynamic responsiveness in route computation should be significantly more effective and less expensive than static routing, increasing total data return while at the same time reducing mission operations cost and risk. The basic strategy of CGR is to take advantage of the fact that, since flight mission communication operations are planned in detail, the communication routes between any pair of bundle agents in a population of nodes that have all been informed of one another's plans can be inferred from those plans rather than discovered via dialogue (which is impractical over long one-way-light-time space links). Messages that convey this planning information are used to construct contact graphs (time-varying models of network connectivity) from which CGR automatically computes efficient routes for bundles. Automatic route selection increases the flexibility and resilience of the space network, simplifying cross-support and reducing mission management costs. Note that there are no routing tables in Contact Graph Routing. The best route for a bundle destined for a given node may routinely be different from the best route for a different bundle destined for the same node, depending on bundle priority, bundle expiration time, and changes in the current lengths of transmission queues for neighboring nodes; routes must be computed individually for each bundle, from the Bundle Protocol agent's current network connectivity model for the bundle s destination node (the contact graph). Clearly this places a premium on optimizing the implementation of the route computation algorithm. The scalability of CGR to very large networks remains a research topic
Noncommutative Riemannian geometry on graphs
NASA Astrophysics Data System (ADS)
Majid, Shahn
2013-07-01
We show that arising out of noncommutative geometry is a natural family of edge Laplacians on the edges of a graph. The family includes a canonical edge Laplacian associated to the graph, extending the usual graph Laplacian on vertices, and we find its spectrum. We show that for a connected graph its eigenvalues are strictly positive aside from one mandatory zero mode, and include all the vertex degrees. Our edge Laplacian is not the graph Laplacian on the line graph but rather it arises as the noncommutative Laplace-Beltrami operator on differential 1-forms, where we use the language of differential algebras to functorially interpret a graph as providing a 'finite manifold structure' on the set of vertices. We equip any graph with a canonical 'Euclidean metric' and a canonical bimodule connection, and in the case of a Cayley graph we construct a metric compatible connection for the Euclidean metric. We make use of results on bimodule connections on inner calculi on algebras, which we prove, including a general relation between zero curvature and the braid relations.
Hinz, Andreas M.
2012-01-01
The appropriate mathematical model for the problem space of tower transformation tasks is the state graph representing positions of discs or balls and their moves. Graph theoretical quantities like distance, eccentricities or degrees of vertices and symmetries of graphs support the choice of problems, the selection of tasks and the analysis of performance of subjects whose solution paths can be projected onto the graph. The mathematical model is also at the base of a computerized test tool to administer various types of tower tasks. PMID:22207419
Graph Representation for Configurational Properties of Crystalline Solids
NASA Astrophysics Data System (ADS)
Yuge, Koretaka
2017-02-01
We propose representation of configurational physical quantities and microscopic structures for multicomponent system on lattice, by extending a concept of generalized Ising model (GIM) to graph theory. We construct graph Laplacian (and adjacency matrix) composed of symmetry-equivalent neighboring edges, whose landscape of spectrum explicitly represents GIM description of structures as well as low-dimensional topological information in terms of graph. The proposed representation indicates the importance of linear combination of graph to further investigate the role of spatial constraint on equilibrium properties in classical systems. We demonstrate that spectrum for such linear combination of graph can find out additional characteristic microscopic structures compared with GIM-based descriptions for given set of figures on the same low-dimensional configuration space, coming from the proposed representation explicitly having more structural information for, e.g., higher-order closed links of selected element. Statistical interdependence for density of microscopic states including graph representation for structures is also examined, which exhibits similar behavior that has been seen for GIM description of the microscopic structures.
Generating graphs for visual analytics through interactive sketching.
Wong, Pak Chung; Foote, Harlan; Mackey, Patrick; Perrine, Ken; Chin, George
2006-01-01
We introduce an interactive graph generator, GreenSketch, designed to facilitate the creation of descriptive graphs required for different visual analytics tasks. The human-centric design approach of GreenSketch enables users to master the creation process without specific training or prior knowledge of graph model theory. The customized user interface encourages users to gain insight into the connection between the compact matrix representation and the topology of a graph layout when they sketch their graphs. Both the human-enforced and machine-generated randomnesses supported by GreenSketch provide the flexibility needed to address the uncertainty factor in many analytical tasks. This paper describes more than two dozen examples that cover a wide variety of graph creations from a single line of nodes to a real-life small-world network that describes a snapshot of telephone connections. While the discussion focuses mainly on the design of GreenSketch, we include a case study that applies the technology in a visual analytics environment and a usability study that evaluates the strengths and weaknesses of our design approach.
Second Language Acquisition and Universal Grammar. Cambridge Textbooks in Linguistics.
ERIC Educational Resources Information Center
White, Lydia
This book examines how the underlying linguistic competence of second language (L2) learners is constrained by the same universal principals governing natural language. It is assumed that there is an innately given universal grammar (UG) which constrains L1 grammars, limiting the kinds of hypotheses that L1 acquirers entertain about the nature of…
Where Is She? Gender Occurrences in Online Grammar Guides
ERIC Educational Resources Information Center
Amare, Nicole
2007-01-01
This article examines seven online grammar guides for instances of linguistic sexism. The grammar sentences from .edu Websites were analyzed based on NCTE's "Guidelines for Gender-Fair Use of Language" (2002) using the criteria of generic he and man; titles, labels, and names; gender stereotypes; order of mention (firstness); and ratio of male to…
Functional Grammar and Its Implications for English Teaching and Learning
ERIC Educational Resources Information Center
Feng, Zhiwen
2013-01-01
Functional grammar has received more and more attention from domestic scholars in the world of linguistics since 1970s, but it is still new to most EFL teachers. In spite of controversies about its applications into classroom teaching, this new grammar model has its own advantages and can facilitate EFL students to achieve academic success. This…
Effectiveness of Inductive and Deductive Methods in Teaching Grammar
ERIC Educational Resources Information Center
Alzu'bi, Mohammad Akram
2015-01-01
The study investigates the comparative effectiveness of teaching English grammar by using deductive and inductive teaching models. The study also attempts to see which of these two methods has a positive effect on the grammar academic achievement of the university students and elementary school students in Jordan so it answers the following…
Albanian Basic Course: Workbook for Exercises in Grammar.
ERIC Educational Resources Information Center
Defense Language Inst., Washington, DC.
This workbook in Albanian grammar requires students to fill in missing words following a particular grammatical pattern, selected from Exercises in Grammar used in the "Albanian Basic Course," prepared by the Defense Language Institute. Drills include: (1) interrogative pronouns, (2) demonstrative adjectives; (3) declension of nouns, possessive…
GRAMMAR--THE PROTEUS OF THE ENGLISH CURRICULUM.
ERIC Educational Resources Information Center
ASTON, KATHARINE O.
THE ENGLISH CURRICULUM CAN BE MADE MORE EFFECTIVE BY CONSIDERING THE SIGNIFICANT PART PLAYED BY THE COMPONENT OF GRAMMAR. THE NATIVE SPEAKER OF ENGLISH POSSESSES AN INTUITIVE KNOWLEDGE OF THE RULES OF GRAMMAR AND YET CANNOT EXPLAIN WHAT HIS INTUITION KNOWS. THEREFORE, A PRECISE, ECONOMICAL DESCRIPTION OF THE LANGUAGE MECHANISM AND HOW IT FUNCTIONS…
Grammar for College Writing: A Sentence-Composing Approach
ERIC Educational Resources Information Center
Killgallon, Don; Killgallon, Jenny
2010-01-01
Across America, in thousands of classrooms, from elementary school to high school, the time-tested sentence-composing approach has given students tools to become better writers. Now the authors present a much anticipated sentence-composing grammar worktext for college writing. This book presents a new and easier way to understand grammar: (1) Noun…
Towards More Context and Discourse in Grammar Instruction
ERIC Educational Resources Information Center
Celce-Murcia, Marianne
2007-01-01
This paper first discusses why the sentence-level drills still being used extensively in the teaching of grammar to second language learners have not been successful. What follows is a presentation of an innovative approach; namely, using context and discourse to present and practice grammar in more authentic and effective ways.
Effect of Direct Grammar Instruction on Student Writing Skills
ERIC Educational Resources Information Center
Robinson, Lisa; Feng, Jay
2016-01-01
Grammar Instruction has an important role to play in helping students to speak and write more effectively. The purpose of this study was to examine the effects of direct grammar instruction on the quality of student's writing skills. The participants in this study included 18 fifth grade students and two fifth grade teachers. Based on the results…
A Grammar of Northern Mao (Mawes Aas'e)
ERIC Educational Resources Information Center
Ahland, Michael Bryan
2012-01-01
Northern Mao is an endangered Afroasiatic-Omotic language of western Ethiopia with fewer than 5,000 speakers. This study is a comprehensive grammar of the language, written from a functional/typological perspective which embraces historical change as an explanation for synchronic structure. The grammar introduces the Northern Mao people, aspects…
On the Equivalence of Formal Grammars and Machines.
ERIC Educational Resources Information Center
Lund, Bruce
1991-01-01
Explores concepts of formal language and automata theory underlying computational linguistics. A computational formalism is described known as a "logic grammar," with which computational systems process linguistic data, with examples in declarative and procedural semantics and definite clause grammars. (13 references) (CB)
Investigating Effects of Computer-Based Grammar Tutorials
ERIC Educational Resources Information Center
Kolesnikova, Anna
2011-01-01
This dissertation study examined a broad question of whether computer-based grammar tutorials are effective and welcome tools to review grammar for language learners by investigating effects of three different modes of such tutorials on learners' knowledge and satisfaction. For this study, I developed experimental tutorials in three different…
Strategic Processing in Grammar Learning: Do Multilinguals Use More Strategies?
ERIC Educational Resources Information Center
Kemp, Charlotte
2007-01-01
Multilinguals appear to become better at learning additional languages the more languages they know, and in particular, to be faster at learning grammar. This study investigates the use of grammar learning strategies in 144 participants who knew between 2 and 12 languages each, using a language background questionnaire, a set of 40 grammar…
Yemeni Teachers' Beliefs of Grammar Teaching and Classroom Practices
ERIC Educational Resources Information Center
Ezzi, Nemah Abdullah Ayash
2012-01-01
Beliefs of in-service English teachers about grammar learning/teaching and the influence of such beliefs on their classroom practices remain relatively unexplored. More precisely, this study explores English teachers' beliefs about grammar learning and teaching. It throws light on the teachers' actual practices in the classrooms of 7th -12th…
The Effectiveness of Incidental Teaching of Grammar to Iranian Students
ERIC Educational Resources Information Center
Ghabanchi, Z.
2010-01-01
This article reports the results of a study and a pilot study. The "study" considers the effectiveness of incidental teaching of grammar in a learning class of English As A Second Language by Persian speaking students. The "pilot study" examines the students' attitudes toward the incidental learning of grammar from the…
Second Language Learners' Beliefs about Grammar Instruction and Error Correction
ERIC Educational Resources Information Center
Loewen, Shawn; Li, Shaofeng; Fei, Fei; Thompson, Amy; Nakatsukasa, Kimi; Ahn, Seongmee; Chen, Xiaoqing
2009-01-01
Learner beliefs are an important individual difference in second language (L2) learning. Furthermore, an ongoing debate surrounds the role of grammar instruction and error correction in the L2 classroom. Therefore, this study investigated the beliefs of L2 learners regarding the controversial role of grammar instruction and error correction. A…
Spoken Grammar: An Urgent Necessity in the EFL Context
ERIC Educational Resources Information Center
Al-wossabi, Sami A.
2014-01-01
Recent studies in corpus linguistics have revealed apparent inconsistencies between the prescriptive grammar presented in EFL textbooks and the type of grammar used in the speech of native speakers. Such variations and learning gaps deprive EFL learners of the actual use of English and delay their oral/aural developmental processes. The focus of…
ncRNA consensus secondary structure derivation using grammar strings.
Achawanantakun, Rujira; Sun, Yanni; Takyar, Seyedeh Shohreh
2011-04-01
Many noncoding RNAs (ncRNAs) function through both their sequences and secondary structures. Thus, secondary structure derivation is an important issue in today's RNA research. The state-of-the-art structure annotation tools are based on comparative analysis, which derives consensus structure of homologous ncRNAs. Despite promising results from existing ncRNA aligning and consensus structure derivation tools, there is a need for more efficient and accurate ncRNA secondary structure modeling and alignment methods. In this work, we introduce a consensus structure derivation approach based on grammar string, a novel ncRNA secondary structure representation that encodes an ncRNA's sequence and secondary structure in the parameter space of a context-free grammar (CFG) and a full RNA grammar including pseudoknots. Being a string defined on a special alphabet constructed from a grammar, grammar string converts ncRNA alignment into sequence alignment. We derive consensus secondary structures from hundreds of ncRNA families from BraliBase 2.1 and 25 families containing pseudoknots using grammar string alignment. Our experiments have shown that grammar string-based structure derivation competes favorably in consensus structure quality with Murlet and RNASampler. Source code and experimental data are available at http://www.cse.msu.edu/~yannisun/grammar-string.
The Effects of Using Online Concordancers on Teaching Grammar
ERIC Educational Resources Information Center
Türkmen, Yasemin; Aydin, Selami
2016-01-01
Studies conducted so far have mainly focused on the effects of online concordancers on teaching vocabulary, while there is a lack of research focusing on the effects of online concordancers on teaching and learning grammar. Thus, this study aims to review the studies on the effects of online concordancers on teaching and learning grammar and how…
The Polylectal Grammar Stops Here. CLCS Occasional Paper No. 13.
ERIC Educational Resources Information Center
Harris, John
An examination of the extent to which the polylectal grammar, a unified grammar constructed by a listener that subsumes the dialect differences that he has to cope with in a multidialectal situation, is an appropriate means of modelling listeners' receptive command of dialects other than their native one presents evidence that cross-dialectal…
Environmental Peace Education in Foreign Language Learners' English Grammar Lessons
ERIC Educational Resources Information Center
Arikan, Arda
2009-01-01
English language teachers create contexts to teach grammar so that meaningful learning occurs. In this study, English grammar is contextualized through environmental peace education activities to raise students' awareness of global issues. Two sources provided data to evaluate the success of this instructional process. Fourth-year pre-service…
Construction Morphology and the Parallel Architecture of Grammar.
Booij, Geert; Audring, Jenny
2015-11-24
This article presents a systematic exposition of how the basic ideas of Construction Grammar (CxG) (Goldberg, ) and the Parallel Architecture (PA) of grammar (Jackendoff, ) provide the framework for a proper account of morphological phenomena, in particular word formation. This framework is referred to as Construction Morphology (CxM). As to the implications of CxM for the architecture of grammar, the article provides evidence against a split between lexicon and grammar, in line with CxG. In addition, it shows that the PA approach makes it possible to be explicit about what happens on which level of the grammar, and thus to give an insightful account of interface phenomena. These interface phenomena appear to require that various types of information are accessible simultaneously, and it is argued that constructional schemas have the right format for expressing these mutual dependencies between different types of information.
Graph Visualization for RDF Graphs with SPARQL-EndPoints
Sukumar, Sreenivas R; Bond, Nathaniel
2014-07-11
RDF graphs are hard to visualize as triples. This software module is a web interface that connects to a SPARQL endpoint and retrieves graph data that the user can explore interactively and seamlessly. The software written in python and JavaScript has been tested to work on screens as little as the smart phones to large screens such as EVEREST.
Matrix computations on mesh arrays
Moreno, J.H.
1989-01-01
This dissertation addresses the systematic derivation of mesh arrays for matrix computations, in particular realizing the algorithm-specific arrays and mapping algorithms onto class-specific arrays. A data-dependency graph-based transformational method is proposed in a design frame work consisting of two stages, namely algorithm regularization and derivation of arrays. The first stage derives the fully-parallel data-dependency graph (FPG) of an algorithm and transforms this graph into a three-dimensional one with unidirectional nearest-neighbor dependencies (a multi-mesh graph MMG). The second stage transforms the MMG into a two-dimensional G-graph, which is realized as an algorithm-specific array or mapped onto a class-specific array. This stage allows the incorporation of implementation restrictions and the evaluation of tradeoffs in properties of cells, as well as the derivation of arrays for fixed-size data and partitioned problems, while performing optimization of specific performance/cost measures. The proposed method is formalized by presenting a sufficient set of transformations and demonstrating the equivalence of graphs obtained from those transformations. Moreover, it is demonstrated that the MMG representation is always possible, due to the characteristics of the operators. The method has been applied to a collection of matrix algorithms, including matrix multiplication, convolution, matrix decompositions, transitive closure, the Faddeev algorithm, and BBA{sup {minus}1}. The examples show that, in addition to the features listed earlier, this method is easy to apply. Moreover, the method is compared with other techniques, concluding that it is advantageous because it meets evaluation criteria and produces more efficient arrays.
Kirkpatrick, Bonnie; Reshef, Yakir; Finucane, Hilary; Jiang, Haitao; Zhu, Binhai; Karp, Richard M
2012-09-01
Pedigree graphs, or family trees, are typically constructed by an expensive process of examining genealogical records to determine which pairs of individuals are parent and child. New methods to automate this process take as input genetic data from a set of extant individuals and reconstruct ancestral individuals. There is a great need to evaluate the quality of these methods by comparing the estimated pedigree to the true pedigree. In this article, we consider two main pedigree comparison problems. The first is the pedigree isomorphism problem, for which we present a linear-time algorithm for leaf-labeled pedigrees. The second is the pedigree edit distance problem, for which we present (1) several algorithms that are fast and exact in various special cases, and (2) a general, randomized heuristic algorithm. In the negative direction, we first prove that the pedigree isomorphism problem is as hard as the general graph isomorphism problem, and that the sub-pedigree isomorphism problem is NP-hard. We then show that the pedigree edit distance problem is APX-hard in general and NP-hard on leaf-labeled pedigrees. We use simulated pedigrees to compare our edit-distance algorithms to each other as well as to a branch-and-bound algorithm that always finds an optimal solution.
Maunz, Peter Lukas Wilhelm; Sterk, Jonathan David; Lobser, Daniel; Parekh, Ojas D.; Ryan-Anderson, Ciaran
2016-01-01
In recent years, advanced network analytics have become increasingly important to na- tional security with applications ranging from cyber security to detection and disruption of ter- rorist networks. While classical computing solutions have received considerable investment, the development of quantum algorithms to address problems, such as data mining of attributed relational graphs, is a largely unexplored space. Recent theoretical work has shown that quan- tum algorithms for graph analysis can be more efficient than their classical counterparts. Here, we have implemented a trapped-ion-based two-qubit quantum information proces- sor to address these goals. Building on Sandia's microfabricated silicon surface ion traps, we have designed, realized and characterized a quantum information processor using the hyperfine qubits encoded in two 171 Yb + ions. We have implemented single qubit gates using resonant microwave radiation and have employed Gate set tomography (GST) to characterize the quan- tum process. For the first time, we were able to prove that the quantum process surpasses the fault tolerance thresholds of some quantum codes by demonstrating a diamond norm distance of less than 1 . 9 x 10 [?] 4 . We used Raman transitions in order to manipulate the trapped ions' motion and realize two-qubit gates. We characterized the implemented motion sensitive and insensitive single qubit processes and achieved a maximal process infidelity of 6 . 5 x 10 [?] 5 . We implemented the two-qubit gate proposed by Molmer and Sorensen and achieved a fidelity of more than 97 . 7%.
Lung vessel segmentation in CT images using graph-cuts
NASA Astrophysics Data System (ADS)
Zhai, Zhiwei; Staring, Marius; Stoel, Berend C.
2016-03-01
Accurate lung vessel segmentation is an important operation for lung CT analysis. Filters that are based on analyzing the eigenvalues of the Hessian matrix are popular for pulmonary vessel enhancement. However, due to their low response at vessel bifurcations and vessel boundaries, extracting lung vessels by thresholding the vesselness is not sufficiently accurate. Some methods turn to graph-cuts for more accurate segmentation, as it incorporates neighbourhood information. In this work, we propose a new graph-cuts cost function combining appearance and shape, where CT intensity represents appearance and vesselness from a Hessian-based filter represents shape. Due to the amount of voxels in high resolution CT scans, the memory requirement and time consumption for building a graph structure is very high. In order to make the graph representation computationally tractable, those voxels that are considered clearly background are removed from the graph nodes, using a threshold on the vesselness map. The graph structure is then established based on the remaining voxel nodes, source/sink nodes and the neighbourhood relationship of the remaining voxels. Vessels are segmented by minimizing the energy cost function with the graph-cuts optimization framework. We optimized the parameters used in the graph-cuts cost function and evaluated the proposed method with two manually labeled sub-volumes. For independent evaluation, we used 20 CT scans of the VESSEL12 challenge. The evaluation results of the sub-volume data show that the proposed method produced a more accurate vessel segmentation compared to the previous methods, with F1 score 0.76 and 0.69. In the VESSEL12 data-set, our method obtained a competitive performance with an area under the ROC curve of 0.975, especially among the binary submissions.
Quantization of gauge fields, graph polynomials and graph homology
Kreimer, Dirk; Sars, Matthias; Suijlekom, Walter D. van
2013-09-15
We review quantization of gauge fields using algebraic properties of 3-regular graphs. We derive the Feynman integrand at n loops for a non-abelian gauge theory quantized in a covariant gauge from scalar integrands for connected 3-regular graphs, obtained from the two Symanzik polynomials. The transition to the full gauge theory amplitude is obtained by the use of a third, new, graph polynomial, the corolla polynomial. This implies effectively a covariant quantization without ghosts, where all the relevant signs of the ghost sector are incorporated in a double complex furnished by the corolla polynomial–we call it cycle homology–and by graph homology. -- Highlights: •We derive gauge theory Feynman from scalar field theory with 3-valent vertices. •We clarify the role of graph homology and cycle homology. •We use parametric renormalization and the new corolla polynomial.
ERIC Educational Resources Information Center
Tran, Tammie M.
2010-01-01
The problem. This research study explores an important issue in the field of TESOL (Teaching English to Speakers of Other Languages) and second language acquisition (SLA). Its purpose is to examine the relationship between Vietnamese students' L1 grammar knowledge and their English grammar proficiency. Furthermore, it investigates the extent to…
ERIC Educational Resources Information Center
Hegelheimer, Volker; Fisher, David
2006-01-01
English language learners are frequently unable to benefit from the prevailing process-writing approaches due to a lack of grammar and vocabulary knowledge relevant to academic writing. This paper describes how the need for explicit grammar instruction as part of preparing students to write can be addressed by using a collection of learner texts…
ERIC Educational Resources Information Center
Liu, Dilin
2011-01-01
Despite a long debate and the accompanying call for changes in the past few decades, grammar instruction in college English classes, according to some scholars, has remained largely "disempowering,""decontextualized," and "remedial" (Micciche, 2004, p. 718). To search for more effective and empowering grammar teaching, this study explores the use…
Interactive image segmentation by constrained spectral graph partitioning
NASA Astrophysics Data System (ADS)
Zhang, Hao; He, Jin; Zhang, Hong; Huang, Zhanhua
2010-11-01
This paper proposed an interactive image segmentation algorithm that can tolerate slightly incorrect user constraints. Interactive image segmentation was formulated as a constrained spectral graph partitioning problem. Furthermore, it was proven to equal to a supervised classification problem, where the feature space was formed by rows of the eigenvector matrix that was computed by spectral graph analysis. ν-SVM (support vector machine) was preferred as the classifier. Some incorrect labels in user constraints were tolerated by being identified as margin errors in ν-SVM. Comparison with other algorithms on real color images was reported.
Thermodynamic characterization of networks using graph polynomials
NASA Astrophysics Data System (ADS)
Ye, Cheng; Comin, César H.; Peron, Thomas K. DM.; Silva, Filipi N.; Rodrigues, Francisco A.; Costa, Luciano da F.; Torsello, Andrea; Hancock, Edwin R.
2015-09-01
In this paper, we present a method for characterizing the evolution of time-varying complex networks by adopting a thermodynamic representation of network structure computed from a polynomial (or algebraic) characterization of graph structure. Commencing from a representation of graph structure based on a characteristic polynomial computed from the normalized Laplacian matrix, we show how the polynomial is linked to the Boltzmann partition function of a network. This allows us to compute a number of thermodynamic quantities for the network, including the average energy and entropy. Assuming that the system does not change volume, we can also compute the temperature, defined as the rate of change of entropy with energy. All three thermodynamic variables can be approximated using low-order Taylor series that can be computed using the traces of powers of the Laplacian matrix, avoiding explicit computation of the normalized Laplacian spectrum. These polynomial approximations allow a smoothed representation of the evolution of networks to be constructed in the thermodynamic space spanned by entropy, energy, and temperature. We show how these thermodynamic variables can be computed in terms of simple network characteristics, e.g., the total number of nodes and node degree statistics for nodes connected by edges. We apply the resulting thermodynamic characterization to real-world time-varying networks representing complex systems in the financial and biological domains. The study demonstrates that the method provides an efficient tool for detecting abrupt changes and characterizing different stages in network evolution.
Weighted graph based ordering techniques for preconditioned conjugate gradient methods
NASA Technical Reports Server (NTRS)
Clift, Simon S.; Tang, Wei-Pai
1994-01-01
We describe the basis of a matrix ordering heuristic for improving the incomplete factorization used in preconditioned conjugate gradient techniques applied to anisotropic PDE's. Several new matrix ordering techniques, derived from well-known algorithms in combinatorial graph theory, which attempt to implement this heuristic, are described. These ordering techniques are tested against a number of matrices arising from linear anisotropic PDE's, and compared with other matrix ordering techniques. A variation of RCM is shown to generally improve the quality of incomplete factorization preconditioners.
ERIC Educational Resources Information Center
Ho, Pham Vu Phi; The Binh, Nguyen
2014-01-01
So far the students of Le Hong Phong Junior High School have been taught grammar with GTM (Grammar-Translation Method), which just prepares learners for conventional grammar-paper tests. Despite their considerable knowledge of grammar, the students fail to use the language they have learnt to communicate in real-life situations. The purpose of…
Understanding the Complex Processes in Developing Student Teachers' Knowledge about Grammar
ERIC Educational Resources Information Center
Svalberg, Agneta M.-L.
2015-01-01
This article takes the view that grammar is driven by user choices and is therefore complex and dynamic. This has implications for the teaching of grammar in language teacher education and how teachers' cognitions about grammar, and hence their own grammar teaching, might change. In this small, interpretative study, the participants--students on…
The Role of Grammar Teaching in Writing in Second Language Acquisition
ERIC Educational Resources Information Center
Lin, Li-Li
2008-01-01
"Grammar is the sound, structure, and meaning system of language. All languages have grammar, and each language has its own grammar" (Beverly, 2007, p.1). People who speak the same language are able to communicate with each other because they all know the grammar system and structure of that language, that is, the meaningful rules of…
NASA Technical Reports Server (NTRS)
Butler, Ricky W.; Sjogren, Jon A.
1998-01-01
This paper documents the NASA Langley PVS graph theory library. The library provides fundamental definitions for graphs, subgraphs, walks, paths, subgraphs generated by walks, trees, cycles, degree, separating sets, and four notions of connectedness. Theorems provided include Ramsey's and Menger's and the equivalence of all four notions of connectedness.
Network reconstruction via graph blending
NASA Astrophysics Data System (ADS)
Estrada, Rolando
2016-05-01
Graphs estimated from empirical data are often noisy and incomplete due to the difficulty of faithfully observing all the components (nodes and edges) of the true graph. This problem is particularly acute for large networks where the number of components may far exceed available surveillance capabilities. Errors in the observed graph can render subsequent analyses invalid, so it is vital to develop robust methods that can minimize these observational errors. Errors in the observed graph may include missing and spurious components, as well fused (multiple nodes are merged into one) and split (a single node is misinterpreted as many) nodes. Traditional graph reconstruction methods are only able to identify missing or spurious components (primarily edges, and to a lesser degree nodes), so we developed a novel graph blending framework that allows us to cast the full estimation problem as a simple edge addition/deletion problem. Armed with this framework, we systematically investigate the viability of various topological graph features, such as the degree distribution or the clustering coefficients, and existing graph reconstruction methods for tackling the full estimation problem. Our experimental results suggest that incorporating any topological feature as a source of information actually hinders reconstruction accuracy. We provide a theoretical analysis of this phenomenon and suggest several avenues for improving this estimation problem.
ERIC Educational Resources Information Center
Axtell, M.; Stickles, J.
2010-01-01
The last ten years have seen an explosion of research in the zero-divisor graphs of commutative rings--by professional mathematicians "and" undergraduates. The objective is to find algebraic information within the geometry of these graphs. This topic is approachable by anyone with one or two semesters of abstract algebra. This article gives the…
Graphs as Statements of Belief.
ERIC Educational Resources Information Center
Lake, David
2002-01-01
Identifies points where beliefs are important when making decisions about how graphs are drawn. Describes a simple case of the reaction between 'bicarb soda' and orange or lemon juice and discusses how drawing a graph becomes a statement of belief. (KHR)
A Collection of Features for Semantic Graphs
Eliassi-Rad, T; Fodor, I K; Gallagher, B
2007-05-02
Semantic graphs are commonly used to represent data from one or more data sources. Such graphs extend traditional graphs by imposing types on both nodes and links. This type information defines permissible links among specified nodes and can be represented as a graph commonly referred to as an ontology or schema graph. Figure 1 depicts an ontology graph for data from National Association of Securities Dealers. Each node type and link type may also have a list of attributes. To capture the increased complexity of semantic graphs, concepts derived for standard graphs have to be extended. This document explains briefly features commonly used to characterize graphs, and their extensions to semantic graphs. This document is divided into two sections. Section 2 contains the feature descriptions for static graphs. Section 3 extends the features for semantic graphs that vary over time.
Path similarity skeleton graph matching.
Bai, Xiang; Latecki, Longin Jan
2008-07-01
This paper presents a novel framework to for shape recognition based on object silhouettes. The main idea is to match skeleton graphs by comparing the shortest paths between skeleton endpoints. In contrast to typical tree or graph matching methods, we completely ignore the topological graph structure. Our approach is motivated by the fact that visually similar skeleton graphs may have completely different topological structures. The proposed comparison of shortest paths between endpoints of skeleton graphs yields correct matching results in such cases. The skeletons are pruned by contour partitioning with Discrete Curve Evolution, which implies that the endpoints of skeleton branches correspond to visual parts of the objects. The experimental results demonstrate that our method is able to produce correct results in the presence of articulations, stretching, and occlusion.
Raberto, Marco; Rapallo, Fabio; Scalas, Enrico
2011-01-01
In this paper, we outline a model of graph (or network) dynamics based on two ingredients. The first ingredient is a Markov chain on the space of possible graphs. The second ingredient is a semi-Markov counting process of renewal type. The model consists in subordinating the Markov chain to the semi-Markov counting process. In simple words, this means that the chain transitions occur at random time instants called epochs. The model is quite rich and its possible connections with algebraic geometry are briefly discussed. Moreover, for the sake of simplicity, we focus on the space of undirected graphs with a fixed number of nodes. However, in an example, we present an interbank market model where it is meaningful to use directed graphs or even weighted graphs. PMID:21887245
Visual Matrix Clustering of Social Networks
Wong, Pak C.; Mackey, Patrick S.; Foote, Harlan P.; May, Richard A.
2013-07-01
The prevailing choices to graphically represent a social network in today’s literature are a node-link graph layout and an adjacency matrix. Both visualization techniques have unique strengths and weaknesses when applied to different domain applications. In this article, we focus our discussion on adjacency matrix and how to turn the matrix-based visualization technique from merely showing pairwise associations among network actors (or graph nodes) to depicting clusters of a social network. We also use node-link layouts to supplement the discussion.
Style grammars for interactive visualization of architecture.
Aliaga, Daniel G; Rosen, Paul A; Bekins, Daniel R
2007-01-01
Interactive visualization of architecture provides a way to quickly visualize existing or novel buildings and structures. Such applications require both fast rendering and an effortless input regimen for creating and changing architecture using high-level editing operations that automatically fill in the necessary details. Procedural modeling and synthesis is a powerful paradigm that yields high data amplification and can be coupled with fast-rendering techniques to quickly generate plausible details of a scene without much or any user interaction. Previously, forward generating procedural methods have been proposed where a procedure is explicitly created to generate particular content. In this paper, we present our work in inverse procedural modeling of buildings and describe how to use an extracted repertoire of building grammars to facilitate the visualization and quick modification of architectural structures and buildings. We demonstrate an interactive application where the user draws simple building blocks and, using our system, can automatically complete the building "in the style of" other buildings using view-dependent texture mapping or nonphotorealistic rendering techniques. Our system supports an arbitrary number of building grammars created from user subdivided building models and captured photographs. Using only edit, copy, and paste metaphors, the entire building styles can be altered and transferred from one building to another in a few operations, enhancing the ability to modify an existing architectural structure or to visualize a novel building in the style of the others.
Evolutionary program induction directed by logic grammars
Wong; Leung
1997-01-01
Program induction generates a computer program that can produce the desired behavior for a given set of situations. Two of the approaches in program induction are inductive logic programming (ILP) and genetic programming (GP). Since their formalisms are so different, these two approaches cannot be integrated easily, although they share many common goals and functionalities. A unification will greatly enhance their problem-solving power. Moreover, they are restricted in the computer languages in which programs can be induced. In this paper, we present a flexible system called LOGENPRO (The LOgic gramar-based GENetic PROgramming system) that uses some of the techniques of GP and ILP. It is based on a formalism of logic grammars. The system applies logic grammars to control the evolution of programs in various programming languages and represent context-sensitive information and domain-dependent knowledge. Experiments have been performed to demonstrate that LOGENPRO can emulate GP and GP with automatically defined functions (ADFs). Moreover, LOGENPRO can employ knowledge such as argument types in a unified framework. The experiments show that LOGENPRO has superior performance to that of GP and GP with ADFs when more domain-dependent knowledge is available. We have applied LOGENPRO to evolve general recursive functions for the even-n-parity problem from noisy training examples. A number of experiments have been performed to determine the impact of domain-specific knowledge and noise in training examples on the speed of learning.
Exploring and Making Sense of Large Graphs
2015-08-01
our fast algorithmic methodologies, we also contribute graph-theoretical ideas and models, and real-world applications in two main areas ??? Single ...Graph Exploration: We show how to interpretably summarize a single graph by identifying its important graph structures. We complement summarization with...effectively learn information about the unknown entities. ??? Multiple-Graph Exploration: We extend the idea of single -graph summarization to time
Comparison and enumeration of chemical graphs.
Akutsu, Tatsuya; Nagamochi, Hiroshi
2013-01-01
Chemical compounds are usually represented as graph structured data in computers. In this review article, we overview several graph classes relevant to chemical compounds and the computational complexities of several fundamental problems for these graph classes. In particular, we consider the following problems: determining whether two chemical graphs are identical, determining whether one input chemical graph is a part of the other input chemical graph, finding a maximum common part of two input graphs, finding a reaction atom mapping, enumerating possible chemical graphs, and enumerating stereoisomers. We also discuss the relationship between the fifth problem and kernel functions for chemical compounds.
Implicit Learning of Recursive Context-Free Grammars
Rohrmeier, Martin; Fu, Qiufang; Dienes, Zoltan
2012-01-01
Context-free grammars are fundamental for the description of linguistic syntax. However, most artificial grammar learning experiments have explored learning of simpler finite-state grammars, while studies exploring context-free grammars have not assessed awareness and implicitness. This paper explores the implicit learning of context-free grammars employing features of hierarchical organization, recursive embedding and long-distance dependencies. The grammars also featured the distinction between left- and right-branching structures, as well as between centre- and tail-embedding, both distinctions found in natural languages. People acquired unconscious knowledge of relations between grammatical classes even for dependencies over long distances, in ways that went beyond learning simpler relations (e.g. n-grams) between individual words. The structural distinctions drawn from linguistics also proved important as performance was greater for tail-embedding than centre-embedding structures. The results suggest the plausibility of implicit learning of complex context-free structures, which model some features of natural languages. They support the relevance of artificial grammar learning for probing mechanisms of language learning and challenge existing theories and computational models of implicit learning. PMID:23094021
Implicit learning of recursive context-free grammars.
Rohrmeier, Martin; Fu, Qiufang; Dienes, Zoltan
2012-01-01
Context-free grammars are fundamental for the description of linguistic syntax. However, most artificial grammar learning experiments have explored learning of simpler finite-state grammars, while studies exploring context-free grammars have not assessed awareness and implicitness. This paper explores the implicit learning of context-free grammars employing features of hierarchical organization, recursive embedding and long-distance dependencies. The grammars also featured the distinction between left- and right-branching structures, as well as between centre- and tail-embedding, both distinctions found in natural languages. People acquired unconscious knowledge of relations between grammatical classes even for dependencies over long distances, in ways that went beyond learning simpler relations (e.g. n-grams) between individual words. The structural distinctions drawn from linguistics also proved important as performance was greater for tail-embedding than centre-embedding structures. The results suggest the plausibility of implicit learning of complex context-free structures, which model some features of natural languages. They support the relevance of artificial grammar learning for probing mechanisms of language learning and challenge existing theories and computational models of implicit learning.
GRAPH III: a digitizing and graph plotting program
Selleck, C.B.
1986-03-01
GRAPH is an interactive program that allows the user to perform two functions. The first is to plot two dimensional graphs and the second is to digitize graphs or plots to create data files of points. The program is designed to allow the user to get results quickly and easily. It is written in RATIV (a FORTRAN preprocessor) and is currently in use at Sandia under VMS on a VAX computer and CTSS on a Cray supercomputer. The program provides graphical output through all of the Sandia Virtual Device Interface (VDI) graphics devices. 2 refs., 3 figs., 3 tabs.
qwViz: Visualisation of quantum walks on graphs
NASA Astrophysics Data System (ADS)
Berry, Scott D.; Bourke, Paul; Wang, Jingbo B.
2011-10-01
qwViz is a software package for interactive visualisation of the time-evolution of quantum walks on arbitrarily complex graphs. The package is written in C and uses OpenGL to generate graphics in real-time. The qwViz package can be used to directly simulate discrete-time quantum walks on undirected graphs when provided with the adjacency matrix of the graph. For more detailed studies, qwViz can also be used to visualise externally generated quantum walk data written in an XML-based file format (QWML). Various aspects of the visualisation can be customised and manipulated in real-time, allowing quantum walk dynamics to be probed at various length and time scales.
A new graph-based molecular descriptor using the canonical representation of the molecule.
Hentabli, Hamza; Saeed, Faisal; Abdo, Ammar; Salim, Naomie
2014-01-01
Molecular similarity is a pervasive concept in drug design. The basic idea underlying molecular similarity is the similar property principle, which states that structurally similar molecules will exhibit similar physicochemical and biological properties. In this paper, a new graph-based molecular descriptor (GBMD) is introduced. The GBMD is a new method of obtaining a rough description of 2D molecular structure in textual form based on the canonical representations of the molecule outline shape and it allows rigorous structure specification using small and natural grammars. Simulated virtual screening experiments with the MDDR database show clearly the superiority of the graph-based descriptor compared to many standard descriptors (ALOGP, MACCS, EPFP4, CDKFP, PCFP, and SMILE) using the Tanimoto coefficient (TAN) and the basic local alignment search tool (BLAST) when searches were carried.
Linking speech errors and phonological grammars: Insights from Harmonic Grammar networks
Goldrick, Matthew; Daland, Robert
2009-01-01
Phonological grammars characterize distinctions between relatively well-formed (unmarked) and relatively ill-formed (marked) phonological structures. We review evidence that markedness influences speech error probabilities. Specifically, although errors result in both unmarked as well as marked structures, there is a markedness asymmetry: errors are more likely to produce unmarked outcomes. We show that stochastic disruption to the computational mechanisms realizing a Harmonic Grammar (HG) can account for the broad empirical patterns of speech errors. We demonstrate that our proposal can account for the general markedness asymmetry. We also develop methods for linking particular HG proposals to speech error distributions, and illustrate these methods using a simple HG and a set of initial consonant errors in English. PMID:20046856
A Linguistic Overview of the Nigel Text Generation Grammar.
1983-10-01
M)A 14 491 A LNGUISTIC OVERVIEW OF THE NIGEL TEXT GENERAI ON / GRAMMAR (U) UNIVERSITY Of SOUTHERN CALIFORNIA MARINA GEL REY INFORMAT ION SCIENCES INST...I3 Atl l 0 IS! Repfn: softs ISIRS-83-9 William C. Mann A inuiic Oerie of the Nigel Text Generation Grammar ;L* __ I ELECT. f rx public releaso and...Generation Grammar Reeac Reor S. PERFORMING ORIM RE1O1T11U11ET 7. AuTmOR(e) 11. CONTRACT OR.GRANT 111111091() William C. Mann F92-9C08 9. PERFORMING
2014-08-14
RolX takes the features from Re-FeX or any other feature matrix as input and outputs role assignments (clusters). The output of RolX is a csv file containing the node-role memberships and a csv file containing the role-feature definitions.
Flying through Graphs: An Introduction to Graph Theory.
ERIC Educational Resources Information Center
McDuffie, Amy Roth
2001-01-01
Presents an activity incorporating basic terminology, concepts, and solution methods of graph theory in the context of solving problems related to air travel. Discusses prerequisite knowledge and resources and includes a teacher's guide with a student worksheet. (KHR)
Multigraph: Reusable Interactive Data Graphs
NASA Astrophysics Data System (ADS)
Phillips, M. B.
2010-12-01
There are surprisingly few good software tools available for presenting time series data on the internet. The most common practice is to use a desktop program such as Excel or Matlab to save a graph as an image which can be included in a web page like any other image. This disconnects the graph from the data in a way that makes updating a graph with new data a cumbersome manual process, and it limits the user to one particular view of the data. The Multigraph project defines an XML format for describing interactive data graphs, and software tools for creating and rendering those graphs in web pages and other internet connected applications. Viewing a Multigraph graph is extremely simple and intuitive, and requires no instructions; the user can pan and zoom by clicking and dragging, in a familiar "Google Maps" kind of way. Creating a new graph for inclusion in a web page involves writing a simple XML configuration file. Multigraph can read data in a variety of formats, and can display data from a web service, allowing users to "surf" through large data sets, downloading only those the parts of the data that are needed for display. The Multigraph XML format, or "MUGL" for short, provides a concise description of the visual properties of a graph, such as axes, plot styles, data sources, labels, etc, as well as interactivity properties such as how and whether the user can pan or zoom along each axis. Multigraph reads a file in this format, draws the described graph, and allows the user to interact with it. Multigraph software currently includes a Flash application for embedding graphs in web pages, a Flex component for embedding graphs in larger Flex/Flash applications, and a plugin for creating graphs in the WordPress content management system. Plans for the future include a Java version for desktop viewing and editing, a command line version for batch and server side rendering, and possibly Android and iPhone versions. Multigraph is currently in use on several web
DNA Rearrangements through Spatial Graphs
NASA Astrophysics Data System (ADS)
Jonoska, Nataša; Saito, Masahico
The paper is a short overview of a recent model of homologous DNA recombination events guided by RNA templates that have been observed in certain species of ciliates. This model uses spatial graphs to describe DNA rearrangements and show how gene recombination can be modeled as topological braiding of the DNA. We show that a graph structure, which we refer to as an assembly graph, containing only 1- and 4-valent rigid vertices can provide a physical representation of the DNA at the time of recombination. With this representation, 4-valent vertices correspond to the alignment of the recombination sites, and we model the actual recombination event as smoothing of these vertices.
Green's function approach for quantum graphs: An overview
NASA Astrophysics Data System (ADS)
Andrade, Fabiano M.; Schmidt, A. G. M.; Vicentini, E.; Cheng, B. K.; da Luz, M. G. E.
2016-08-01
Here we review the many aspects and distinct phenomena associated to quantum dynamics on general graph structures. For so, we discuss such class of systems under the energy domain Green's function (G) framework. This approach is particularly interesting because G can be written as a sum over classical-like paths, where local quantum effects are taken into account through the scattering matrix elements (basically, transmission and reflection amplitudes) defined on each one of the graph vertices. Hence, the exact G has the functional form of a generalized semiclassical formula, which through different calculation techniques (addressed in detail here) always can be cast into a closed analytic expression. It allows to solve exactly arbitrary large (although finite) graphs in a recursive and fast way. Using the Green's function method, we survey many properties of open and closed quantum graphs as scattering solutions for the former and eigenspectrum and eigenstates for the latter, also considering quasi-bound states. Concrete examples, like cube, binary trees and Sierpiński-like topologies are presented. Along the work, possible distinct applications using the Green's function methods for quantum graphs are outlined.
Picture grammars in classification and semantic interpretation of 3D coronary vessels visualisations
NASA Astrophysics Data System (ADS)
Ogiela, M. R.; Tadeusiewicz, R.; Trzupek, M.
2009-09-01
The work presents the new opportunity for making semantic descriptions and analysis of medical structures, especially coronary vessels CT spatial reconstructions, with the use of AI graph-based linguistic formalisms. In the paper there will be discussed the manners of applying methods of computational intelligence to the development of a syntactic semantic description of spatial visualisations of the heart's coronary vessels. Such descriptions may be used for both smart ordering of images while archiving them and for their semantic searches in medical multimedia databases. Presented methodology of analysis can furthermore be used for attaining other goals related performance of computer-assisted semantic interpretation of selected elements and/or the entire 3D structure of the coronary vascular tree. These goals are achieved through the use of graph-based image formalisms based on IE graphs generating grammars that allow discovering and automatic semantic interpretation of irregularities visualised on the images obtained during diagnostic examinations of the heart muscle. The basis for the construction of 3D reconstructions of biological objects used in this work are visualisations obtained from helical CT scans, yet the method itself may be applied also for other methods of medical 3D images acquisition. The obtained semantic information makes it possible to make a description of the structure focused on the semantics of various morphological forms of the visualised vessels from the point of view of the operation of coronary circulation and the blood supply of the heart muscle. Thanks to these, the analysis conducted allows fast and — to a great degree — automated interpretation of the semantics of various morphological changes in the coronary vascular tree, and especially makes it possible to detect these stenoses in the lumen of the vessels that can cause critical decrease in blood supply to extensive or especially important fragments of the heart muscle.
An Entropy Model for Artificial Grammar Learning
Pothos, Emmanuel M.
2010-01-01
A model is proposed to characterize the type of knowledge acquired in artificial grammar learning (AGL). In particular, Shannon entropy is employed to compute the complexity of different test items in an AGL task, relative to the training items. According to this model, the more predictable a test item is from the training items, the more likely it is that this item should be selected as compatible with the training items. The predictions of the entropy model are explored in relation to the results from several previous AGL datasets and compared to other AGL measures. This particular approach in AGL resonates well with similar models in categorization and reasoning which also postulate that cognitive processing is geared towards the reduction of entropy. PMID:21607072
Nigel: a systemic grammar for text generation
Mann, W.C.; Matthiessen, C.M.
1983-02-01
Programming a computer to write text which meets a prior need is a challenging research task. As part of such research, Nigel, a large programmed grammar of English, has been created in the framework of systemic linguistics begun by Halliday. In addition to specifying function and structures of English, Nigel has a novel semantic stratum which specifies the situations in which each grammatical feature should be used. The report consists of three papers on Nigel: an introductory overview, the script of a demonstration of its use in generation, and an exposition of how Nigel relates to the systemic framework. Although the effort to develop Nigel is significant both as computer science research and as linguistic inquiry the outlook of the report is oriented to its linguistic significance.
Susceptible-infected-susceptible epidemics on the complete graph and the star graph: Exact analysis
NASA Astrophysics Data System (ADS)
Cator, E.; Van Mieghem, P.
2013-01-01
Since mean-field approximations for susceptible-infected-susceptible (SIS) epidemics do not always predict the correct scaling of the epidemic threshold of the SIS metastable regime, we propose two novel approaches: (a) an ɛ-SIS generalized model and (b) a modified SIS model that prevents the epidemic from dying out (i.e., without the complicating absorbing SIS state). Both adaptations of the SIS model feature a precisely defined steady state (that corresponds to the SIS metastable state) and allow an exact analysis in the complete and star graph consisting of a central node and N leaves. The N-intertwined mean-field approximation (NIMFA) is shown to be nearly exact for the complete graph but less accurate to predict the correct scaling of the epidemic threshold τc in the star graph, which is found as τc=ατc(1), where α=(1)/(2)logN+(3)/(2)loglogN and where τc(1)=(1)/(N)<τc is the first-order epidemic threshold for the star in NIMFA and equal to the inverse of the spectral radius of the star's adjacency matrix.
Information theory and artificial grammar learning: inferring grammaticality from redundancy.
Jamieson, Randall K; Nevzorova, Uliana; Lee, Graham; Mewhort, D J K
2016-03-01
In artificial grammar learning experiments, participants study strings of letters constructed using a grammar and then sort novel grammatical test exemplars from novel ungrammatical ones. The ability to distinguish grammatical from ungrammatical strings is often taken as evidence that the participants have induced the rules of the grammar. We show that judgements of grammaticality are predicted by the local redundancy of the test strings, not by grammaticality itself. The prediction holds in a transfer test in which test strings involve different letters than the training strings. Local redundancy is usually confounded with grammaticality in stimuli widely used in the literature. The confounding explains why the ability to distinguish grammatical from ungrammatical strings has popularized the idea that participants have induced the rules of the grammar, when they have not. We discuss the judgement of grammaticality task in terms of attribute substitution and pattern goodness. When asked to judge grammaticality (an inaccessible attribute), participants answer an easier question about pattern goodness (an accessible attribute).
Graph anomalies in cyber communications
Vander Wiel, Scott A; Storlie, Curtis B; Sandine, Gary; Hagberg, Aric A; Fisk, Michael
2011-01-11
Enterprises monitor cyber traffic for viruses, intruders and stolen information. Detection methods look for known signatures of malicious traffic or search for anomalies with respect to a nominal reference model. Traditional anomaly detection focuses on aggregate traffic at central nodes or on user-level monitoring. More recently, however, traffic is being viewed more holistically as a dynamic communication graph. Attention to the graph nature of the traffic has expanded the types of anomalies that are being sought. We give an overview of several cyber data streams collected at Los Alamos National Laboratory and discuss current work in modeling the graph dynamics of traffic over the network. We consider global properties and local properties within the communication graph. A method for monitoring relative entropy on multiple correlated properties is discussed in detail.
Constructing Dense Graphs with Unique Hamiltonian Cycles
ERIC Educational Resources Information Center
Lynch, Mark A. M.
2012-01-01
It is not difficult to construct dense graphs containing Hamiltonian cycles, but it is difficult to generate dense graphs that are guaranteed to contain a unique Hamiltonian cycle. This article presents an algorithm for generating arbitrarily large simple graphs containing "unique" Hamiltonian cycles. These graphs can be turned into dense graphs…
Exploring manifold structure of face images via multiple graphs
NASA Astrophysics Data System (ADS)
Alghamdi, Masheal
2013-12-01
Geometric structure in the data provides important information for face image recognition and classification tasks. Graph regularized non-negative matrix factorization (GrNMF) performs well in this task. However, it is sensitive to the parameters selection. Wang et al. proposed multiple graph regularized non-negative matrix factorization (MultiGrNMF) to solve the parameter selection problem by testing it on medical images. In this paper, we introduce the MultiGrNMF algorithm in the context of still face Image classification, and conduct a comparative study of NMF, GrNMF, and MultiGrNMF using two well-known face databases. Experimental results show that MultiGrNMF outperforms NMF and GrNMF for most cases.
Clues from Information Theory Indicating a Phased Emergence of Grammar
NASA Astrophysics Data System (ADS)
Lyon, Caroline; Nehaniv, Chrystopher L.; Dickerson, Bob
In this chapter we present evidence that there is an underlying local sequential structure in present day language, and suggest that the components of such a structure could have been the basis of a more highly evolved hierarchical grammar. The primary local sequential structure is shown to have its own benefits, which indicate that there could be an intermediate stage in the evolution of grammar, before the advantages of a fully developed syntax were realised.
Fast Dynamic Meshing Method Based on Delaunay Graph and Inverse Distance Weighting Interpolation
NASA Astrophysics Data System (ADS)
Wang, Yibin; Qin, Ning; Zhao, Ning
2016-06-01
A novel mesh deformation technique is developed based on the Delaunay graph mapping method and the inverse distance weighting (IDW) interpolation. The algorithm maintains the advantages of the efficiency of Delaunay-graph-mapping mesh deformation while possess the ability for better controlling the near surface mesh quality. The Delaunay graph is used to divide the mesh domain into a number of sub-domains. On each of the sub-domains, the inverse distance weighting interpolation is applied to build a much smaller sized translation matrix between the original mesh and the deformed mesh, resulting a similar efficiency for the mesh deformation as compared to the fast Delaunay graph mapping method. The paper will show how the near-wall mesh quality is controlled and improved by the new method while the computational time is compared with the original Delaunay graph mapping method.
Chromatic polynomials of random graphs
NASA Astrophysics Data System (ADS)
Van Bussel, Frank; Ehrlich, Christoph; Fliegner, Denny; Stolzenberg, Sebastian; Timme, Marc
2010-04-01
Chromatic polynomials and related graph invariants are central objects in both graph theory and statistical physics. Computational difficulties, however, have so far restricted studies of such polynomials to graphs that were either very small, very sparse or highly structured. Recent algorithmic advances (Timme et al 2009 New J. Phys. 11 023001) now make it possible to compute chromatic polynomials for moderately sized graphs of arbitrary structure and number of edges. Here we present chromatic polynomials of ensembles of random graphs with up to 30 vertices, over the entire range of edge density. We specifically focus on the locations of the zeros of the polynomial in the complex plane. The results indicate that the chromatic zeros of random graphs have a very consistent layout. In particular, the crossing point, the point at which the chromatic zeros with non-zero imaginary part approach the real axis, scales linearly with the average degree over most of the density range. While the scaling laws obtained are purely empirical, if they continue to hold in general there are significant implications: the crossing points of chromatic zeros in the thermodynamic limit separate systems with zero ground state entropy from systems with positive ground state entropy, the latter an exception to the third law of thermodynamics.
Exactly solvable interacting two-particle quantum graphs
NASA Astrophysics Data System (ADS)
Bolte, Jens; Garforth, George
2017-03-01
We construct models of exactly solvable two-particle quantum graphs with certain non-local two-particle interactions, establishing appropriate boundary conditions via suitable self-adjoint realisations of the two-particle Laplacian. Showing compatibility with the Bethe ansatz method, we calculate quantisation conditions in the form of secular equations from which the spectra can be deduced. We compare spectral statistics of some examples to well known results in random matrix theory, analysing the chaotic properties of their classical counterparts.
Agreement Problems in Networks with Directed Graphs and Switching Topology
2003-02-15
C–3613. References [1] N. Biggs. Algebraic Graph Theory. Cambridge Tracks in Mathematics. Cambridge University Press , 1974. 15 [2] J. P. Desai, J. P...Springer, 2001. [9] R. A. Horn and C. R. Johnson. Matrix Analysis. Cambridge University Press , 1987. [10] A. Jadbabaie, J. Lin, and S. A. Morse...Networks of Dynamic Agents. Proc. of the American Control Conference, June 2003. [15] F. Paganini , J. Doyle, and S Low. Scalable laws for stable
Khovanov homology of graph-links
Nikonov, Igor M
2012-08-31
Graph-links arise as the intersection graphs of turning chord diagrams of links. Speaking informally, graph-links provide a combinatorial description of links up to mutations. Many link invariants can be reformulated in the language of graph-links. Khovanov homology, a well-known and useful knot invariant, is defined for graph-links in this paper (in the case of the ground field of characteristic two). Bibliography: 14 titles.
The contribution of phonological short-term memory to artificial grammar learning.
Andrade, Jackie; Baddeley, Alan
2011-05-01
Three experiments investigated the contribution of phonological short-term memory (STM) to grammar learning by manipulating rehearsal during study of an auditory artificial grammar made up from a vocabulary of spoken Mandarin syllables. Experiment 1 showed that concurrent, irrelevant articulation impaired grammar learning compared with a nonverbal control task. Experiment 2 replicated and extended this finding, showing that repeating the grammatical strings at study improved grammar learning compared with suppressing rehearsal or remaining silent during learning. Experiment 3 found no effects of rehearsal on grammar learning once participants had learned the component syllables. The findings suggest that phonological STM aids artificial grammar learning via effects on vocabulary learning.
Barrès, Victor; Lee, Jinyong
2014-01-01
How does the language system coordinate with our visual system to yield flexible integration of linguistic, perceptual, and world-knowledge information when we communicate about the world we perceive? Schema theory is a computational framework that allows the simulation of perceptuo-motor coordination programs on the basis of known brain operating principles such as cooperative computation and distributed processing. We present first its application to a model of language production, SemRep/TCG, which combines a semantic representation of visual scenes (SemRep) with Template Construction Grammar (TCG) as a means to generate verbal descriptions of a scene from its associated SemRep graph. SemRep/TCG combines the neurocomputational framework of schema theory with the representational format of construction grammar in a model linking eye-tracking data to visual scene descriptions. We then offer a conceptual extension of TCG to include language comprehension and address data on the role of both world knowledge and grammatical semantics in the comprehension performances of agrammatic aphasic patients. This extension introduces a distinction between heavy and light semantics. The TCG model of language comprehension offers a computational framework to quantitatively analyze the distributed dynamics of language processes, focusing on the interactions between grammatical, world knowledge, and visual information. In particular, it reveals interesting implications for the understanding of the various patterns of comprehension performances of agrammatic aphasics measured using sentence-picture matching tasks. This new step in the life cycle of the model serves as a basis for exploring the specific challenges that neurolinguistic computational modeling poses to the neuroinformatics community.
Principal Graph and Structure Learning Based on Reversed Graph Embedding.
Mao, Qi; Wang, Li; Tsang, Ivor; Sun, Yijun
2016-12-05
Many scientific datasets are of high dimension, and the analysis usually requires retaining the most important structures of data. Principal curve is a widely used approach for this purpose. However, many existing methods work only for data with structures that are mathematically formulated by curves, which is quite restrictive for real applications. A few methods can overcome the above problem, but they either require complicated human-made rules for a specific task with lack of adaption flexibility to different tasks, or cannot obtain explicit structures of data. To address these issues, we develop a novel principal graph and structure learning framework that captures the local information of the underlying graph structure based on reversed graph embedding. As showcases, models that can learn a spanning tree or a weighted undirected `1 graph are proposed, and a new learning algorithm is developed that learns a set of principal points and a graph structure from data, simultaneously. The new algorithm is simple with guaranteed convergence. We then extend the proposed framework to deal with large-scale data. Experimental results on various synthetic and six real world datasets show that the proposed method compares favorably with baselines and can uncover the underlying structure correctly.
GraphMeta: Managing HPC Rich Metadata in Graphs
Dai, Dong; Chen, Yong; Carns, Philip; Jenkins, John; Zhang, Wei; Ross, Robert
2016-01-01
High-performance computing (HPC) systems face increasingly critical metadata management challenges, especially in the approaching exascale era. These challenges arise not only from exploding metadata volumes, but also from increasingly diverse metadata, which contains data provenance and arbitrary user-defined attributes in addition to traditional POSIX metadata. This ‘rich’ metadata is becoming critical to supporting advanced data management functionality such as data auditing and validation. In our prior work, we identified a graph-based model as a promising solution to uniformly manage HPC rich metadata due to its flexibility and generality. However, at the same time, graph-based HPC rich metadata anagement also introduces significant challenges to the underlying infrastructure. In this study, we first identify the challenges on the underlying infrastructure to support scalable, high-performance rich metadata management. Based on that, we introduce GraphMeta, a graphbased engine designed for this use case. It achieves performance scalability by introducing a new graph partitioning algorithm and a write-optimal storage engine. We evaluate GraphMeta under both synthetic and real HPC metadata workloads, compare it with other approaches, and demonstrate its advantages in terms of efficiency and usability for rich metadata management in HPC systems.
Private Graphs - Access Rights on Graphs for Seamless Navigation
NASA Astrophysics Data System (ADS)
Dorner, W.; Hau, F.; Pagany, R.
2016-06-01
After the success of GNSS (Global Navigational Satellite Systems) and navigation services for public streets, indoor seems to be the next big development in navigational services, relying on RTLS - Real Time Locating Services (e.g. WIFI) and allowing seamless navigation. In contrast to navigation and routing services on public streets, seamless navigation will cause an additional challenge: how to make routing data accessible to defined users or restrict access rights for defined areas or only to parts of the graph to a defined user group? The paper will present case studies and data from literature, where seamless and especially indoor navigation solutions are presented (hospitals, industrial complexes, building sites), but the problem of restricted access rights was only touched from a real world, but not a technical perspective. The analysis of case studies will show, that the objective of navigation and the different target groups for navigation solutions will demand well defined access rights and require solutions, how to make only parts of a graph to a user or application available to solve a navigational task. The paper will therefore introduce the concept of private graphs, which is defined as a graph for navigational purposes covering the street, road or floor network of an area behind a public street and suggest different approaches how to make graph data for navigational purposes available considering access rights and data protection, privacy and security issues as well.
Constructing a Nonnegative Low-Rank and Sparse Graph With Data-Adaptive Features.
Zhuang, Liansheng; Gao, Shenghua; Tang, Jinhui; Wang, Jingjing; Lin, Zhouchen; Ma, Yi; Yu, Nenghai
2015-11-01
This paper aims at constructing a good graph to discover the intrinsic data structures under a semisupervised learning setting. First, we propose to build a nonnegative low-rank and sparse (referred to as NNLRS) graph for the given data representation. In particular, the weights of edges in the graph are obtained by seeking a nonnegative low-rank and sparse reconstruction coefficients matrix that represents each data sample as a linear combination of others. The so-obtained NNLRS-graph captures both the global mixture of subspaces structure (by the low-rankness) and the locally linear structure (by the sparseness) of the data, hence it is both generative and discriminative. Second, as good features are extremely important for constructing a good graph, we propose to learn the data embedding matrix and construct the graph simultaneously within one framework, which is termed as NNLRS with embedded features (referred to as NNLRS-EF). Extensive NNLRS experiments on three publicly available data sets demonstrate that the proposed method outperforms the state-of-the-art graph construction method by a large margin for both semisupervised classification and discriminative analysis, which verifies the effectiveness of our proposed method.
Sharing Teaching Ideas: Graphing Families of Curves Using Transformations of Reference Graphs
ERIC Educational Resources Information Center
Kukla, David
2007-01-01
This article provides for a fast extremely accurate approach to graphing functions that is based on learning function reference graphs and then applying algebraic transformations to these reference graphs.
Bounds of the spectral radius and the Nordhaus-Gaddum type of the graphs.
Wang, Tianfei; Jia, Liping; Sun, Feng
2013-01-01
The Laplacian spectra are the eigenvalues of Laplacian matrix L(G) = D(G) - A(G), where D(G) and A(G) are the diagonal matrix of vertex degrees and the adjacency matrix of a graph G, respectively, and the spectral radius of a graph G is the largest eigenvalue of A(G). The spectra of the graph and corresponding eigenvalues are closely linked to the molecular stability and related chemical properties. In quantum chemistry, spectral radius of a graph is the maximum energy level of molecules. Therefore, good upper bounds for the spectral radius are conducive to evaluate the energy of molecules. In this paper, we first give several sharp upper bounds on the adjacency spectral radius in terms of some invariants of graphs, such as the vertex degree, the average 2-degree, and the number of the triangles. Then, we give some numerical examples which indicate that the results are better than the mentioned upper bounds in some sense. Finally, an upper bound of the Nordhaus-Gaddum type is obtained for the sum of Laplacian spectral radius of a connected graph and its complement. Moreover, some examples are applied to illustrate that our result is valuable.
Graph classification by means of Lipschitz embedding.
Riesen, Kaspar; Bunke, Horst
2009-12-01
In pattern recognition and related fields, graph-based representations offer a versatile alternative to the widely used feature vectors. Therefore, an emerging trend of representing objects by graphs can be observed. This trend is intensified by the development of novel approaches in graph-based machine learning, such as graph kernels or graph-embedding techniques. These procedures overcome a major drawback of graphs, which consists of a serious lack of algorithms for classification. This paper is inspired by the idea of representing graphs through dissimilarities and extends our previous work to the more general setting of Lipschitz embeddings. In an experimental evaluation, we empirically confirm that classifiers that rely on the original graph distances can be outperformed by a classification system using the Lipschitz embedded graphs.
Eye Movements in Implicit Artificial Grammar Learning.
Silva, Susana; Inácio, Filomena; Folia, Vasiliki; Petersson, Karl Magnus
2017-03-13
Artificial grammar learning (AGL) has been probed with forced-choice behavioral tests (active tests). Recent attempts to probe the outcomes of learning (implicitly acquired knowledge) with eye-movement responses (passive tests) have shown null results. However, these latter studies have not tested for sensitivity effects, for example, increased eye movements on a printed violation. In this study, we tested for sensitivity effects in AGL tests with (Experiment 1) and without (Experiment 2) concurrent active tests (preference- and grammaticality classification) in an eye-tracking experiment. Eye movements discriminated between sequence types in passive tests and more so in active tests. The eye-movement profile did not differ between preference and grammaticality classification, and it resembled sensitivity effects commonly observed in natural syntax processing. Our findings show that the outcomes of implicit structured sequence learning can be characterized in eye tracking. More specifically, whole trial measures (dwell time, number of fixations) showed robust AGL effects, whereas first-pass measures (first-fixation duration) did not. Furthermore, our findings strengthen the link between artificial and natural syntax processing, and they shed light on the factors that determine performance differences in preference and grammaticality classification tests. (PsycINFO Database Record
CLIL in physics lessons at grammar school
NASA Astrophysics Data System (ADS)
Štefančínová, Iveta; Valovičová, Ä½ubomíra
2017-01-01
Content and Language Integrated Learning (CLIL) is one of the most outstanding approaches in foreign language teaching. This teaching method has promising prospects for the future of modern education as teaching subject and foreign languages are combined to offer a better preparation for life in Europe, especially when the mobility is becoming a highly significant factor of everyday life. We realized a project called Foreign languages in popularizing science at grammar school. Within the project five teachers with approbation subjects of English, French, German and Physics attended the methodological courses abroad. The teachers applied the gained experience in teaching and linking science teaching with the teaching of foreign languages. Outputs of the project (e.g. English-German-French-Slovak glossary of natural science terminology, student activity sheets, videos with natural science orientation in a foreign language, physical experiments in foreign languages, multimedia fairy tales with natural contents, posters of some scientists) are prepared for the CLIL-oriented lessons. We collected data of the questionnaire for students concerning attitude towards CLIL. The questionnaire for teachers showed data about the attitude, experience, and needs of teachers employing CLIL in their lessons.
Algebraic connectivity and graph robustness.
Feddema, John Todd; Byrne, Raymond Harry; Abdallah, Chaouki T.
2009-07-01
Recent papers have used Fiedler's definition of algebraic connectivity to show that network robustness, as measured by node-connectivity and edge-connectivity, can be increased by increasing the algebraic connectivity of the network. By the definition of algebraic connectivity, the second smallest eigenvalue of the graph Laplacian is a lower bound on the node-connectivity. In this paper we show that for circular random lattice graphs and mesh graphs algebraic connectivity is a conservative lower bound, and that increases in algebraic connectivity actually correspond to a decrease in node-connectivity. This means that the networks are actually less robust with respect to node-connectivity as the algebraic connectivity increases. However, an increase in algebraic connectivity seems to correlate well with a decrease in the characteristic path length of these networks - which would result in quicker communication through the network. Applications of these results are then discussed for perimeter security.
Graph Analytics for Signature Discovery
Hogan, Emilie A.; Johnson, John R.; Halappanavar, Mahantesh; Lo, Chaomei
2013-06-01
Within large amounts of seemingly unstructured data it can be diffcult to find signatures of events. In our work we transform unstructured data into a graph representation. By doing this we expose underlying structure in the data and can take advantage of existing graph analytics capabilities, as well as develop new capabilities. Currently we focus on applications in cybersecurity and communication domains. Within cybersecurity we aim to find signatures for perpetrators using the pass-the-hash attack, and in communications we look for emails or phone calls going up or down a chain of command. In both of these areas, and in many others, the signature we look for is a path with certain temporal properties. In this paper we discuss our methodology for finding these temporal paths within large graphs.
Graph modeling systems and methods
Neergaard, Mike
2015-10-13
An apparatus and a method for vulnerability and reliability modeling are provided. The method generally includes constructing a graph model of a physical network using a computer, the graph model including a plurality of terminating vertices to represent nodes in the physical network, a plurality of edges to represent transmission paths in the physical network, and a non-terminating vertex to represent a non-nodal vulnerability along a transmission path in the physical network. The method additionally includes evaluating the vulnerability and reliability of the physical network using the constructed graph model, wherein the vulnerability and reliability evaluation includes a determination of whether each terminating and non-terminating vertex represents a critical point of failure. The method can be utilized to evaluate wide variety of networks, including power grid infrastructures, communication network topologies, and fluid distribution systems.
Sequential visibility-graph motifs
NASA Astrophysics Data System (ADS)
Iacovacci, Jacopo; Lacasa, Lucas
2016-04-01
Visibility algorithms transform time series into graphs and encode dynamical information in their topology, paving the way for graph-theoretical time series analysis as well as building a bridge between nonlinear dynamics and network science. In this work we introduce and study the concept of sequential visibility-graph motifs, smaller substructures of n consecutive nodes that appear with characteristic frequencies. We develop a theory to compute in an exact way the motif profiles associated with general classes of deterministic and stochastic dynamics. We find that this simple property is indeed a highly informative and computationally efficient feature capable of distinguishing among different dynamics and robust against noise contamination. We finally confirm that it can be used in practice to perform unsupervised learning, by extracting motif profiles from experimental heart-rate series and being able, accordingly, to disentangle meditative from other relaxation states. Applications of this general theory include the automatic classification and description of physical, biological, and financial time series.
NASA Astrophysics Data System (ADS)
Algor, Ilan
1988-03-01
The problem concerns the minimum time in which a number of messages can be transmitted through a communication network in which each node can transmit to many other nodes simultaneously but can receive only one message at a time. In the undirected version of the problem, the graphs, G, representing the messages are finite, undirected and simple; the messages transmitted in unit time form a subgraph which is a star. The star aboricity, st(G) of a graph G is the minimum number of star forests whose union covers all edges of G. A maximum value is derived for the star aboricity of any d-regular graph G, and is proved through probabilistic arguments.
Optimal preparation of graph states
Cabello, Adan; Lopez-Tarrida, Antonio J.; Danielsen, Lars Eirik; Portillo, Jose R.
2011-04-15
We show how to prepare any graph state of up to 12 qubits with (a) the minimum number of controlled-Z gates and (b) the minimum preparation depth. We assume only one-qubit and controlled-Z gates. The method exploits the fact that any graph state belongs to an equivalence class under local Clifford operations. We extend up to 12 qubits the classification of graph states according to their entanglement properties, and identify each class using only a reduced set of invariants. For any state, we provide a circuit with both properties (a) and (b), if it does exist, or, if it does not, one circuit with property (a) and one with property (b), including the explicit one-qubit gates needed.
Rosmanis, Ansis
2011-02-15
I introduce a continuous-time quantum walk on graphs called the quantum snake walk, the basis states of which are fixed-length paths (snakes) in the underlying graph. First, I analyze the quantum snake walk on the line, and I show that, even though most states stay localized throughout the evolution, there are specific states that most likely move on the line as wave packets with momentum inversely proportional to the length of the snake. Next, I discuss how an algorithm based on the quantum snake walk might potentially be able to solve an extended version of the glued trees problem, which asks to find a path connecting both roots of the glued trees graph. To the best of my knowledge, no efficient quantum algorithm solving this problem is known yet.
Forgiving Ourselves and Forging Ahead: Teaching Grammar in a New Millennium
ERIC Educational Resources Information Center
Nunan, Susan Losee
2005-01-01
Various studies revealed the ineffectiveness of direct grammar instruction to produce better writers. However, a high school teacher finds that explaining grammar rules provides students with tools for building complex thoughts and expressing themselves more elaborately.
Quelques problemes poses a la grammaire casuelle (Some Problems Regarding Case Grammar)
ERIC Educational Resources Information Center
Fillmore, Charles J.
1975-01-01
Discusses problems related to case grammar theory, including: the organizations of a case grammar; determination of semantic roles; definition and hierarchy of cases; cause-effect relations; and formalization and notation. (Text is in French.) (AM)
Interacting particle systems on graphs
NASA Astrophysics Data System (ADS)
Sood, Vishal
In this dissertation, the dynamics of socially or biologically interacting populations are investigated. The individual members of the population are treated as particles that interact via links on a social or biological network represented as a graph. The effect of the structure of the graph on the properties of the interacting particle system is studied using statistical physics techniques. In the first chapter, the central concepts of graph theory and social and biological networks are presented. Next, interacting particle systems that are drawn from physics, mathematics and biology are discussed in the second chapter. In the third chapter, the random walk on a graph is studied. The mean time for a random walk to traverse between two arbitrary sites of a random graph is evaluated. Using an effective medium approximation it is found that the mean first-passage time between pairs of sites, as well as all moments of this first-passage time, are insensitive to the density of links in the graph. The inverse of the mean-first passage time varies non-monotonically with the density of links near the percolation transition of the random graph. Much of the behavior can be understood by simple heuristic arguments. Evolutionary dynamics, by which mutants overspread an otherwise uniform population on heterogeneous graphs, are studied in the fourth chapter. Such a process underlies' epidemic propagation, emergence of fads, social cooperation or invasion of an ecological niche by a new species. The first part of this chapter is devoted to neutral dynamics, in which the mutant genotype does not have a selective advantage over the resident genotype. The time to extinction of one of the two genotypes is derived. In the second part of this chapter, selective advantage or fitness is introduced such that the mutant genotype has a higher birth rate or a lower death rate. This selective advantage leads to a dynamical competition in which selection dominates for large populations
Boosting for multi-graph classification.
Wu, Jia; Pan, Shirui; Zhu, Xingquan; Cai, Zhihua
2015-03-01
In this paper, we formulate a novel graph-based learning problem, multi-graph classification (MGC), which aims to learn a classifier from a set of labeled bags each containing a number of graphs inside the bag. A bag is labeled positive, if at least one graph in the bag is positive, and negative otherwise. Such a multi-graph representation can be used for many real-world applications, such as webpage classification, where a webpage can be regarded as a bag with texts and images inside the webpage being represented as graphs. This problem is a generalization of multi-instance learning (MIL) but with vital differences, mainly because instances in MIL share a common feature space whereas no feature is available to represent graphs in a multi-graph bag. To solve the problem, we propose a boosting based multi-graph classification framework (bMGC). Given a set of labeled multi-graph bags, bMGC employs dynamic weight adjustment at both bag- and graph-levels to select one subgraph in each iteration as a weak classifier. In each iteration, bag and graph weights are adjusted such that an incorrectly classified bag will receive a higher weight because its predicted bag label conflicts to the genuine label, whereas an incorrectly classified graph will receive a lower weight value if the graph is in a positive bag (or a higher weight if the graph is in a negative bag). Accordingly, bMGC is able to differentiate graphs in positive and negative bags to derive effective classifiers to form a boosting model for MGC. Experiments and comparisons on real-world multi-graph learning tasks demonstrate the algorithm performance.
Approximate Graph Edit Distance in Quadratic Time.
Riesen, Kaspar; Ferrer, Miquel; Bunke, Horst
2015-09-14
Graph edit distance is one of the most flexible and general graph matching models available. The major drawback of graph edit distance, however, is its computational complexity that restricts its applicability to graphs of rather small size. Recently the authors of the present paper introduced a general approximation framework for the graph edit distance problem. The basic idea of this specific algorithm is to first compute an optimal assignment of independent local graph structures (including substitutions, deletions, and insertions of nodes and edges). This optimal assignment is complete and consistent with respect to the involved nodes of both graphs and can thus be used to instantly derive an admissible (yet suboptimal) solution for the original graph edit distance problem in O(n3) time. For large scale graphs or graph sets, however, the cubic time complexity may still be too high. Therefore, we propose to use suboptimal algorithms with quadratic rather than cubic time for solving the basic assignment problem. In particular, the present paper introduces five different greedy assignment algorithms in the context of graph edit distance approximation. In an experimental evaluation we show that these methods have great potential for further speeding up the computation of graph edit distance while the approximated distances remain sufficiently accurate for graph based pattern classification.
Graph run-length matrices for histopathological image segmentation.
Tosun, Akif Burak; Gunduz-Demir, Cigdem
2011-03-01
The histopathological examination of tissue specimens is essential for cancer diagnosis and grading. However, this examination is subject to a considerable amount of observer variability as it mainly relies on visual interpretation of pathologists. To alleviate this problem, it is very important to develop computational quantitative tools, for which image segmentation constitutes the core step. In this paper, we introduce an effective and robust algorithm for the segmentation of histopathological tissue images. This algorithm incorporates the background knowledge of the tissue organization into segmentation. For this purpose, it quantifies spatial relations of cytological tissue components by constructing a graph and uses this graph to define new texture features for image segmentation. This new texture definition makes use of the idea of gray-level run-length matrices. However, it considers the runs of cytological components on a graph to form a matrix, instead of considering the runs of pixel intensities. Working with colon tissue images, our experiments demonstrate that the texture features extracted from "graph run-length matrices" lead to high segmentation accuracies, also providing a reasonable number of segmented regions. Compared with four other segmentation algorithms, the results show that the proposed algorithm is more effective in histopathological image segmentation.
Impact of Consciousness-Raising Activities on Young English Language Learners' Grammar Performance
ERIC Educational Resources Information Center
Fatemipour, Hamidreza; Hemmati, Shiva
2015-01-01
Grammar Consciousness-Raising (GCR) is an approach to teaching of grammar which learners instead of being taught the given rules, experience language data. The data challenge them to rethink, restructure their existing mental grammar and construct an explicit rule to describe the grammatical feature which the data illustrate (Ellis, 2002). And…
ERIC Educational Resources Information Center
Eckstein, Grant
2016-01-01
Although most writing centres maintain policies against providing grammar correction during writing tutorials, it is undeniable that students expect some level of grammar intervention there. Just how much students expect and receive is a matter of speculation. This article examines the grammar-correction issue by reporting on a survey of L1, L2,…
ERIC Educational Resources Information Center
Washington, Karla N.
2013-01-01
Purpose: To determine whether (a) expressive grammar intervention facilitated social and emergent literacy outcomes better than no intervention and (b) expressive grammar gains and/or initial expressive grammar level predicted social and emergent literacy outcomes. Method: This investigation was a follow-up to a recently published study exploring…
The Role of Grammar in the Writing Curriculum: A Review of the Literature
ERIC Educational Resources Information Center
Myhill, Debra; Watson, Annabel
2014-01-01
For most Anglophone countries, the history of grammar teaching over the past 50 years is one of contestation, debate and dissent: and 50 years on we are no closer to reaching a consensus about the role of grammar in the English/Language Arts curriculum. The debate has been described through the metaphor of battle and grammar wars (Kamler, 1995;…
Development and Validation of a Diagnostic Grammar Test for Japanese Learners of English
ERIC Educational Resources Information Center
Koizumi, Rie; Sakai, Hideki; Ido, Takahiro; Ota, Hiroshi; Hayama, Megumi; Sato, Masatoshi; Nemoto, Akiko
2011-01-01
This article reports on the development and validation of the English Diagnostic Test of Grammar (EDiT Grammar) for Japanese learners of English. From among the many aspects of grammar, this test focuses on the knowledge of basic English noun phrases (NPs), especially their internal structures, because previous research has indicated the…
Improving Student Writing Using a Web-Based Targeted Approach to Grammar System (TAGS).
ERIC Educational Resources Information Center
Henderson, Bruce
2002-01-01
Notes that the need to teach basic grammar has increased as journalism programs expand their focus to match workforce skills. Proposes that a Web-based Targeted Approach to Grammar System (TAGS) is a development in grammar checkers that is useful for teaching and learning. Discusses a pedagogical approach to using TAGS via the Web. (PM)
The Nature of the Initial State Zulu L2 Grammar and Subsequent Interlanguage Development.
ERIC Educational Resources Information Center
Dube, Sibusisiwe
2000-01-01
A notable feature of developing interlanguage grammars is the apparent optionality in those areas of grammar where optionality is not characteristic of stable state grammars. In the Valueless Features Hypothesis, it is proposed that the appearance of apparent optionality in the very early stages of interlanguage development is due to the partial…
Graph theoretical analysis of climate data
NASA Astrophysics Data System (ADS)
Zerenner, T.; Hense, A.
2012-04-01
Applying methods from graph and network theory to climatological data is a quite new approach and contains numerous difficulties. The atmosphere is a high dimensional and complex dynamical system which per se does not show a network-like structure. It does not consist of well-defined nodes and edges. Thus considering such a system as a network or graph inevitably involves radical simplifications and ambiguities. Nevertheless network analysis has provided useful results for different kinds of complex systems for example in biology or medical science (neural and gene interaction networks). The application of these methods on climate data provides interesting results as well. If the network construction is based on the correlation matrix of the underlying data, the resulting network structures show many well known patterns and characteristics of the atmospheric circulation (Tsonis et al. 2006, Donges et al. 2009). The interpretation of these network structures is yet questionable. Using Pearson Correlation for network construction does not allow to differ between direct and indirect dependencies. An edge does not necessarily represent a causal connection. An interpretation of these structures for instance concerning the stability of the climate system is therefore doubtful. Gene interaction networks for example are often constructed using partial correlations (Wu et al. 2003), which makes it possible to distinguish between direct and indirect dependencies. Although a high value of partial correlation does not guarantee causality it is a step in the direction of measuring causal dependencies. This approach is known as Gaussian Graphical Models, GGMs. For high dimensional datasets such as climate data partial correlations can be obtained by calculating the precision matrix, the inverse covariance matrix. Since the maximum likelihood estimates of covariance matrices of climate datasets are singular the precision matrices can only be estimated for example by using the
Laplacian versus adjacency matrix in quantum walk search
NASA Astrophysics Data System (ADS)
Wong, Thomas G.; Tarrataca, Luís; Nahimov, Nikolay
2016-10-01
A quantum particle evolving by Schrödinger's equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace's operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Laplacian and adjacency matrix. The two walks differ qualitatively and quantitatively in their required jumping rate, runtime, sampling of marked vertices, and in what constitutes a natural initial state. Thus the choice of the Laplacian or adjacency matrix to effect the walk has important algorithmic consequences.
Comparison Graph of Sea Ice Minimum - 2010
This animated graph tracks the retreat of sea ice, measured in millions of square kilometers, averaged from the start of the satellite record in 1979 through 2000 (white). Next, the graph follows t...
Mathematical Minute: Rotating a Function Graph
ERIC Educational Resources Information Center
Bravo, Daniel; Fera, Joseph
2013-01-01
Using calculus only, we find the angles you can rotate the graph of a differentiable function about the origin and still obtain a function graph. We then apply the solution to odd and even degree polynomials.
Standard Distributions: One Graph Fits All
ERIC Educational Resources Information Center
Wagner, Clifford H.
2007-01-01
Standard distributions are ubiquitous but not unique. With suitable scaling, the graph of a standard distribution serves as the graph for every distribution in the family. The standard exponential can easily be taught in elementary statistics courses.
Graphing and Social Studies: An Interdisciplinary Activity.
ERIC Educational Resources Information Center
Brehm, Julia L.
1996-01-01
Describes a graphing activity that promotes mathematical connections with social studies lessons. Students should be familiar with graphing on the Cartesian coordinate system to play this variation of the game Battleship on maps of various regions of the world. (AIM)
Torsional rigidity, isospectrality and quantum graphs
NASA Astrophysics Data System (ADS)
Colladay, Don; Kaganovskiy, Leon; McDonald, Patrick
2017-01-01
We study torsional rigidity for graph and quantum graph analogs of well-known pairs of isospectral non-isometric planar domains. We prove that such isospectral pairs are distinguished by torsional rigidity.
The developmental acquisition of English grammar as an additional language.
Quinn, C
2001-01-01
The results are presented here of an investigation into the development of receptive and expressive English grammar when this is acquired as a second language. A cross-sectional survey using standardised assessments was conducted. 103 children were randomly selected from three local primary schools. These children were aged between 5 and 11 years and were acquiring English sequentially. Data relating to the receptive and expressive grammar of English as a second language was collected from each child. Analysis of this data revealed preliminary developmental patterns that appear to be specific to the sequential acquisition of English grammar. This data confirms the importance of not using data pertaining to the acquisition of first language English for English that is acquired as a second language.
Automating 3D reconstruction using a probabilistic grammar
NASA Astrophysics Data System (ADS)
Xiong, Hanwei; Xu, Jun; Xu, Chenxi; Pan, Ming
2015-10-01
3D reconstruction of objects from point clouds with a laser scanner is still a laborious task in many applications. Automating 3D process is an ongoing research topic and suffers from the complex structure of the data. The main difficulty is due to lack of knowledge of real world objects structure. In this paper, we accumulate such structure knowledge by a probabilistic grammar learned from examples in the same category. The rules of the grammar capture compositional structures at different levels, and a feature dependent probability function is attached for every rule. The learned grammar can be used to parse new 3D point clouds, organize segment patches in a hierarchal way, and assign them meaningful labels. The parsed semantics can be used to guide the reconstruction algorithms automatically. Some examples are given to explain the method.
A phrase-driven grammar system for interactive data visualization
NASA Astrophysics Data System (ADS)
Lee, Sang Yun; Neumann, Ulrich
2008-01-01
A Phrase-Driven Grammar System (PDGS) is a novel GUI for facilitating the visualization of data. The PDGS integrates data source applications and external visualization tools into its framework and functions as a middle-layer application to coordinate their operations. It allows users to formulate data query and visualization descriptions by selecting graphical icons in a menu or on a map. To specify data query and visualization intuitively and efficiently, we designed Graphical User Interface and a natural-language-like grammar, Phrase-Driven Grammar (PDG). The formulation of PDG data query and visualization descriptions is a constrained natural-language phrase building process. PDG phrases produce graphical visualizations of the data query, allowing users to interactively explore meaningful data relationships, trends, and exceptions.
On the structure of context-sensitive grammars
NASA Technical Reports Server (NTRS)
Book, R. V.
1973-01-01
Consideration of the problem of explaining the use of context in generating noncontext-free languages. A number of existing results regarding the constraints placed on the form of the rules (i.e., on the context) of context-sensitive grammars are reviewed and interpreted. Three types of constraints are considered - namely, constraints which do not restrict the weak generative capacity of the class of grammars (i.e., all the context-sensitive languages are generated by grammars with these constraints), constraints which restrict the weak generative capacity to the extent that all context-sensitive languages are not generated but some noncontext-free languages are generated, and constraints which restrict the weak generative capacity to such an extent that only context-free languages are generated.
Humidity Graphs for All Seasons.
ERIC Educational Resources Information Center
Esmael, F.
1982-01-01
In a previous article in this journal (Vol. 17, p358, 1979), a wet-bulb depression table was recommended for two simple experiments to determine relative humidity. However, the use of a graph is suggested because it gives the relative humidity directly from the wet and dry bulb readings. (JN)
NASA Astrophysics Data System (ADS)
Prudente, Matthew James
Given a graph G with pebbles on the vertices, we define a pebbling move as removing two pebbles from a vertex u, placing one pebble on a neighbor v, and discarding the other pebble, like a toll. The pebbling number pi( G) is the least number of pebbles needed so that every arrangement of pi(G) pebbles can place a pebble on any vertex through a sequence of pebbling moves. We introduce a new variation on graph pebbling called two-player pebbling. In this, players called the mover and the defender alternate moves, with the stipulation that the defender cannot reverse the previous move. The mover wins only if they can place a pebble on a specified vertex and the defender wins if the mover cannot. We define η(G), analogously, as the minimum number of pebbles such that given every configuration of the η( G) pebbles and every specified vertex r, the mover has a winning strategy. First, we will investigate upper bounds for η( G) on various classes of graphs and find a certain structure for which the defender has a winning strategy, no matter how many pebbles are in a configuration. Then, we characterize winning configurations for both players on a special class of diameter 2 graphs. Finally, we show winning configurations for the mover on paths using a recursive argument.
Graphs and Enhancing Maple Multiplication.
ERIC Educational Resources Information Center
Cecil, David R.; Wang, Rongdong
2002-01-01
Description of a technique in Maple programming language that automatically prints all paths of any desired length along with the name of each vertex, proceeding in order from the beginning vertex to the ending vertex for a given graph. (Author/MM)
Ancestral Genres of Mathematical Graphs
ERIC Educational Resources Information Center
Gerofsky, Susan
2011-01-01
Drawing from sources in gesture studies, cognitive science, the anthropology of religion and art/architecture history, this article explores cultural, bodily and cosmological resonances carried (unintentionally) by mathematical graphs on Cartesian coordinates. Concepts of asymmetric bodily spaces, grids, orthogonality, mapping and sacred spaces…
Situating Graphs as Workplace Knowledge
ERIC Educational Resources Information Center
Noss, Richard; Bakker, Arthur; Hoyles, Celia; Kent, Phillip
2007-01-01
We investigate the use and knowledge of graphs in the context of a large industrial factory. We are particularly interested in the question of "transparency", a question that has been extensively considered in the general literature on tool use and, more recently, by Michael Roth and his colleagues in the context of scientific work. Roth uses the…
Conceptual graphs for semantics and knowledge processing
Fargues, J.; Landau, M.C.; Dugourd, A.; Catach, L.
1986-01-01
This paper discusses the representational and algorithmic power of the conceptual graph model for natural language semantics and knowledge processing. Also described is a Prolog-like resolution method for conceptual graphs, which allows to perform deduction on very large semantic domains. The interpreter developed is similar to a Prolog interpreter in which the terms are any conceptual graphs and in which the unification algorithm is replaced by a specialized algorithm for conceptual graphs.
Claw-Free Maximal Planar Graphs
1989-01-01
0, 1,2 and 3 points of degree 6 respectively.) Now suppose G,. has no claws for 3 < r < i and consider graph G ,+,. Graph G,+ 1 is obtained from Gr by...adjacent to a point v by N(v) and call the induced subgraph GiN(v)] the neighborhood graph of v in G . Graph G is said to be locally n-connected if for all
Chemical Applications of Graph Theory: Part II. Isomer Enumeration.
ERIC Educational Resources Information Center
Hansen, Peter J.; Jurs, Peter C.
1988-01-01
Discusses the use of graph theory to aid in the depiction of organic molecular structures. Gives a historical perspective of graph theory and explains graph theory terminology with organic examples. Lists applications of graph theory to current research projects. (ML)
Collaborative Robotic Instruction: A Graph Teaching Experience
ERIC Educational Resources Information Center
Mitnik, Ruben; Recabarren, Matias; Nussbaum, Miguel; Soto, Alvaro
2009-01-01
Graphing is a key skill in the study of Physics. Drawing and interpreting graphs play a key role in the understanding of science, while the lack of these has proved to be a handicap and a limiting factor in the learning of scientific concepts. It has been observed that despite the amount of previous graph-working experience, students of all ages…
47 CFR 80.761 - Conversion graphs.
Code of Federal Regulations, 2012 CFR
2012-10-01
... 47 Telecommunication 5 2012-10-01 2012-10-01 false Conversion graphs. 80.761 Section 80.761... MARITIME SERVICES Standards for Computing Public Coast Station VHF Coverage § 80.761 Conversion graphs. The following graphs must be employed where conversion from one to the other of the indicated types of units...
Positive and Unlabeled Multi-Graph Learning.
Wu, Jia; Pan, Shirui; Zhu, Xingquan; Zhang, Chengqi; Wu, Xindong
2016-03-23
In this paper, we advance graph classification to handle multi-graph learning for complicated objects, where each object is represented as a bag of graphs and the label is only available to each bag but not individual graphs. In addition, when training classifiers, users are only given a handful of positive bags and many unlabeled bags, and the learning objective is to train models to classify previously unseen graph bags with maximum accuracy. To achieve the goal, we propose a positive and unlabeled multi-graph learning (puMGL) framework to first select informative subgraphs to convert graphs into a feature space. To utilize unlabeled bags for learning, puMGL assigns a confidence weight to each bag and dynamically adjusts its weight value to select "reliable negative bags." A number of representative graphs, selected from positive bags and identified reliable negative graph bags, form a "margin graph pool" which serves as the base for deriving subgraph patterns, training graph classifiers, and further updating the bag weight values. A closed-loop iterative process helps discover optimal subgraphs from positive and unlabeled graph bags for learning. Experimental comparisons demonstrate the performance of puMGL for classifying real-world complicated objects.
47 CFR 80.761 - Conversion graphs.
Code of Federal Regulations, 2013 CFR
2013-10-01
... 47 Telecommunication 5 2013-10-01 2013-10-01 false Conversion graphs. 80.761 Section 80.761... MARITIME SERVICES Standards for Computing Public Coast Station VHF Coverage § 80.761 Conversion graphs. The following graphs must be employed where conversion from one to the other of the indicated types of units...
47 CFR 80.761 - Conversion graphs.
Code of Federal Regulations, 2010 CFR
2010-10-01
... 47 Telecommunication 5 2010-10-01 2010-10-01 false Conversion graphs. 80.761 Section 80.761... MARITIME SERVICES Standards for Computing Public Coast Station VHF Coverage § 80.761 Conversion graphs. The following graphs must be employed where conversion from one to the other of the indicated types of units...
ERIC Educational Resources Information Center
McMillen, Sue; McMillen, Beth
2010-01-01
Connecting stories to qualitative coordinate graphs has been suggested as an effective instructional strategy. Even students who are able to "create" bar graphs may struggle to correctly "interpret" them. Giving children opportunities to work with qualitative graphs can help them develop the skills to interpret, describe, and compare information…
So Many Graphs, So Little Time
ERIC Educational Resources Information Center
Wall, Jennifer J.; Benson, Christine C.
2009-01-01
Interpreting graphs found in various content areas is an important skill for students, especially in light of high-stakes testing. In addition, reading and understanding graphs is an important part of numeracy, or numeric literacy, a skill necessary for informed citizenry. This article explores the different categories of graphs, provides…
47 CFR 80.761 - Conversion graphs.
Code of Federal Regulations, 2011 CFR
2011-10-01
... 47 Telecommunication 5 2011-10-01 2011-10-01 false Conversion graphs. 80.761 Section 80.761... MARITIME SERVICES Standards for Computing Public Coast Station VHF Coverage § 80.761 Conversion graphs. The following graphs must be employed where conversion from one to the other of the indicated types of units...
47 CFR 80.761 - Conversion graphs.
Code of Federal Regulations, 2014 CFR
2014-10-01
... 47 Telecommunication 5 2014-10-01 2014-10-01 false Conversion graphs. 80.761 Section 80.761... MARITIME SERVICES Standards for Computing Public Coast Station VHF Coverage § 80.761 Conversion graphs. The following graphs must be employed where conversion from one to the other of the indicated types of units...
Teaching and Assessing Graphing Using Active Learning
ERIC Educational Resources Information Center
McFarland, Jenny
2010-01-01
As a college biology instructor, I often see graphs in lab reports that do not meet my expectations. I also observe that many college students do not always adequately differentiate between good and poor (or misleading) graphs. The activity described in this paper is the result of my work with students to improve their graphing literacy. The…
Some Applications of Graph Theory to Clustering
ERIC Educational Resources Information Center
Hubert, Lawrence J.
1974-01-01
The connection between graph theory and clustering is reviewed and extended. Major emphasis is on restating, in a graph-theoretic context, selected past work in clustering, and conversely, developing alternative strategies from several standard concepts used in graph theory per se. (Author/RC)
Graph Partitioning Models for Parallel Computing
Hendrickson, B.; Kolda, T.G.
1999-03-02
Calculations can naturally be described as graphs in which vertices represent computation and edges reflect data dependencies. By partitioning the vertices of a graph, the calculation can be divided among processors of a parallel computer. However, the standard methodology for graph partitioning minimizes the wrong metric and lacks expressibility. We survey several recently proposed alternatives and discuss their relative merits.
An Evaluation of Universal Grammar and the Phonological Mind1
Everett, Daniel L.
2016-01-01
This paper argues against the hypothesis of a “phonological mind” advanced by Berent. It establishes that there is no evidence that phonology is innate and that, in fact, the simplest hypothesis seems to be that phonology is learned like other human abilities. Moreover, the paper fleshes out the original claim of Philip Lieberman that Universal Grammar predicts that not everyone should be able to learn every language, i.e., the opposite of what UG is normally thought to predict. The paper also underscores the problem that the absence of recursion in Pirahã represents for Universal Grammar proposals. PMID:26903889
A Conceptual Framework for Grammar-Driven Synthesis.
1980-12-01
AD°AlO0 159 NAVAL POSTGRADUATE SCHOOL MONTEREY CA FIO 9/2 A CONCEPTUAL FRAMEWORK FOR GRAMMAR-DRIVEN SYNTHESIS.(U) DEC 80 W R SHOCKLEY, D P HADDOW...UNCLASSIFIED NL iflfl/lf/l...l../l IEIIIIEIIIEEI hhhhmmhmmmhu LEVEK NAVAL POSTGRADUATE SCHOOL Monterey, California THESIS A CONCEPTUAL FRAMEWORK FOR...1, . VT ACCg"bOk NNyls CATALOG TUMBIOR 4. T....... I Ji D COVEEO ’ I. A Conceptual Framework for Grammar-Driven Synthesi Me- - ~er’s j sisjec, 1980 P
An Evaluation of Universal Grammar and the Phonological Mind.
Everett, Daniel L
2016-01-01
This paper argues against the hypothesis of a "phonological mind" advanced by Berent. It establishes that there is no evidence that phonology is innate and that, in fact, the simplest hypothesis seems to be that phonology is learned like other human abilities. Moreover, the paper fleshes out the original claim of Philip Lieberman that Universal Grammar predicts that not everyone should be able to learn every language, i.e., the opposite of what UG is normally thought to predict. The paper also underscores the problem that the absence of recursion in Pirahã represents for Universal Grammar proposals.
On Anaphora and the Binding Principles in Categorial Grammar
NASA Astrophysics Data System (ADS)
Morrill, Glyn; Valentín, Oriol
In type logical categorial grammar the analysis of an expression is a resource-conscious proof. Anaphora represents a particular challenge to this approach in that the antecedent resource is multiplied in the semantics. This duplication, which corresponds logically to the structural rule of contraction, may be treated lexically or syntactically. Furthermore, anaphora is subject to constraints, which Chomsky (1981) formulated as Binding Principles A, B, and C. In this paper we consider English anaphora in categorial grammar including reference to the binding principles. We invoke displacement calculus, modal categorial calculus, categorial calculus with limited contraction, and entertain addition of negation as failure.
Johnson, Todd; Bartol, Tom; Sejnowski, Terrence; Mjolsness, Eric
2015-06-18
A stochastic reaction network model of Ca(2+) dynamics in synapses (Pepke et al PLoS Comput. Biol. 6 e1000675) is expressed and simulated using rule-based reaction modeling notation in dynamical grammars and in MCell. The model tracks the response of calmodulin and CaMKII to calcium influx in synapses. Data from numerically intensive simulations is used to train a reduced model that, out of sample, correctly predicts the evolution of interaction parameters characterizing the instantaneous probability distribution over molecular states in the much larger fine-scale models. The novel model reduction method, 'graph-constrained correlation dynamics', requires a graph of plausible state variables and interactions as input. It parametrically optimizes a set of constant coefficients appearing in differential equations governing the time-varying interaction parameters that determine all correlations between variables in the reduced model at any time slice.
Structural pursuit over multiple undirected graphs*
Zhu, Yunzhang; Shen, Xiaotong; Pan, Wei
2014-01-01
Summary Gaussian graphical models are useful to analyze and visualize conditional dependence relationships between interacting units. Motivated from network analysis under di erent experimental conditions, such as gene networks for disparate cancer subtypes, we model structural changes over multiple networks with possible heterogeneities. In particular, we estimate multiple precision matrices describing dependencies among interacting units through maximum penalized likelihood. Of particular interest are homogeneous groups of similar entries across and zero-entries of these matrices, referred to as clustering and sparseness structures, respectively. A non-convex method is proposed to seek a sparse representation for each matrix and identify clusters of the entries across the matrices. Computationally, we develop an e cient method on the basis of di erence convex programming, the augmented Lagrangian method and the block-wise coordinate descent method, which is scalable to hundreds of graphs of thousands nodes through a simple necessary and sufficient partition rule, which divides nodes into smaller disjoint subproblems excluding zero-coe cients nodes for arbitrary graphs with convex relaxation. Theoretically, a finite-sample error bound is derived for the proposed method to reconstruct the clustering and sparseness structures. This leads to consistent reconstruction of these two structures simultaneously, permitting the number of unknown parameters to be exponential in the sample size, and yielding the optimal performance of the oracle estimator as if the true structures were given a priori. Simulation studies suggest that the method enjoys the benefit of pursuing these two disparate kinds of structures, and compares favorably against its convex counterpart in the accuracy of structure pursuit and parameter estimation. PMID:25642006
ERIC Educational Resources Information Center
National Council of Teachers of English, Urbana, IL. Assembly for the Teaching of English Grammar.
Providing alternatives to the way grammar is taught, this proceedings includes every paper (or summary) except one delivered at a conference on the future of grammar in American schools. Papers in the proceedings are: "Keynote: The Future of Grammar in American Schools" (Martha Kolln); "Approaches to Grammar: Teaching &…
Derive Workshop Matrix Algebra and Linear Algebra.
ERIC Educational Resources Information Center
Townsley Kulich, Lisa; Victor, Barbara
This document presents the course content for a workshop that integrates the use of the computer algebra system Derive with topics in matrix and linear algebra. The first section is a guide to using Derive that provides information on how to write algebraic expressions, make graphs, save files, edit, define functions, differentiate expressions,…
Schmidt, Deena R; Thomas, Peter J
2014-04-17
Mathematical models of cellular physiological mechanisms often involve random walks on graphs representing transitions within networks of functional states. Schmandt and Galán recently introduced a novel stochastic shielding approximation as a fast, accurate method for generating approximate sample paths from a finite state Markov process in which only a subset of states are observable. For example, in ion-channel models, such as the Hodgkin-Huxley or other conductance-based neural models, a nerve cell has a population of ion channels whose states comprise the nodes of a graph, only some of which allow a transmembrane current to pass. The stochastic shielding approximation consists of neglecting fluctuations in the dynamics associated with edges in the graph not directly affecting the observable states. We consider the problem of finding the optimal complexity reducing mapping from a stochastic process on a graph to an approximate process on a smaller sample space, as determined by the choice of a particular linear measurement functional on the graph. The partitioning of ion-channel states into conducting versus nonconducting states provides a case in point. In addition to establishing that Schmandt and Galán's approximation is in fact optimal in a specific sense, we use recent results from random matrix theory to provide heuristic error estimates for the accuracy of the stochastic shielding approximation for an ensemble of random graphs. Moreover, we provide a novel quantitative measure of the contribution of individual transitions within the reaction graph to the accuracy of the approximate process.
Reproducibility of graph metrics of human brain functional networks.
Deuker, Lorena; Bullmore, Edward T; Smith, Marie; Christensen, Soren; Nathan, Pradeep J; Rockstroh, Brigitte; Bassett, Danielle S
2009-10-01
Graph theory provides many metrics of complex network organization that can be applied to analysis of brain networks derived from neuroimaging data. Here we investigated the test-retest reliability of graph metrics of functional networks derived from magnetoencephalography (MEG) data recorded in two sessions from 16 healthy volunteers who were studied at rest and during performance of the n-back working memory task in each session. For each subject's data at each session, we used a wavelet filter to estimate the mutual information (MI) between each pair of MEG sensors in each of the classical frequency intervals from gamma to low delta in the overall range 1-60 Hz. Undirected binary graphs were generated by thresholding the MI matrix and 8 global network metrics were estimated: the clustering coefficient, path length, small-worldness, efficiency, cost-efficiency, assortativity, hierarchy, and synchronizability. Reliability of each graph metric was assessed using the intraclass correlation (ICC). Good reliability was demonstrated for most metrics applied to the n-back data (mean ICC=0.62). Reliability was greater for metrics in lower frequency networks. Higher frequency gamma- and beta-band networks were less reliable at a global level but demonstrated high reliability of nodal metrics in frontal and parietal regions. Performance of the n-back task was associated with greater reliability than measurements on resting state data. Task practice was also associated with greater reliability. Collectively these results suggest that graph metrics are sufficiently reliable to be considered for future longitudinal studies of functional brain network changes.
Generalization of the Bollobás-Riordan polynomial for tensor graphs
NASA Astrophysics Data System (ADS)
Tanasa, Adrian
2011-07-01
Tensor models are used nowadays for implementing a fundamental theory of quantum gravity. We define here a polynomial T encoding the supplementary topological information. This polynomial is a natural generalization of the Bollobás-Riordan polynomial (used to characterize matrix graphs) and is different from the Gurău polynomial [R. Gurău, Ann. Henri Poincare 11, 565 (2010)], 10.1007/s00023-010-0035-6, defined for a particular class of tensor graphs, the colorable ones. The polynomial T is defined for both colorable and non-colorable graphs and it is proved to satisfy the deletion/contraction relation. A non-trivial example of a non-colorable graphs is analyzed.
ERIC Educational Resources Information Center
Hubert, Lawrence; Arabie, Phipps; Meulman, Jacqueline
1998-01-01
Introduces a method for fitting order-constrained matrices that satisfy the strongly anti-Robinson restrictions (SAR). The method permits a representation of the fitted values in a (least-squares) SAR approximating matrix as lengths of paths in a graph. The approach is illustrated with a published proximity matrix. (SLD)
NASA Astrophysics Data System (ADS)
Xiong, B.; Oude Elberink, S.; Vosselman, G.
2014-07-01
In the task of 3D building model reconstruction from point clouds we face the problem of recovering a roof topology graph in the presence of noise, small roof faces and low point densities. Errors in roof topology graphs will seriously affect the final modelling results. The aim of this research is to automatically correct these errors. We define the graph correction as a graph-to-graph problem, similar to the spelling correction problem (also called the string-to-string problem). The graph correction is more complex than string correction, as the graphs are 2D while strings are only 1D. We design a strategy based on a dictionary of graph edit operations to automatically identify and correct the errors in the input graph. For each type of error the graph edit dictionary stores a representative erroneous subgraph as well as the corrected version. As an erroneous roof topology graph may contain several errors, a heuristic search is applied to find the optimum sequence of graph edits to correct the errors one by one. The graph edit dictionary can be expanded to include entries needed to cope with errors that were previously not encountered. Experiments show that the dictionary with only fifteen entries already properly corrects one quarter of erroneous graphs in about 4500 buildings, and even half of the erroneous graphs in one test area, achieving as high as a 95% acceptance rate of the reconstructed models.
Dense Trivalent Graphs for Processor Interconnection,
1981-01-01
this paper is organized as follows: Sec- tion 2 introduces notation and defines the new family of graphs, which we call Moebius graphs. Section 3...the shuffle exchange [9].) Let Id denote the identity function on 2 The Moebius graph of order n (so named because the function f introduces a loop...We will write vk = p(v ). 3. DIAMETER OF THE MOEBIUS GRAPH In this section we will show that the diameter of the Moe- bius graph is bounded by L3/2 nj
Stability Properties of Inclusive Connectivity for Graphs
1993-12-01
of G . Graphs illustrating the two possible relationships between the three inclusive connectivity parameters for edges are shown in Figures 2.12 and...For simplicity in this section, we will call this graph G the "internal G graph " due to its location in the figures, and the "K4 with one edge doubly...to one copy of the subdivided K4 producing the graph in Figure 5.25. 117 1(4 with one edge Internal G graph K4 with one edge Figure 5.24 The
Proving relations between modular graph functions
NASA Astrophysics Data System (ADS)
Basu, Anirban
2016-12-01
We consider modular graph functions that arise in the low energy expansion of the four graviton amplitude in type II string theory. The vertices of these graphs are the positions of insertions of vertex operators on the toroidal worldsheet, while the links are the scalar Green functions connecting the vertices. Graphs with four and five links satisfy several non-trivial relations, which have been proved recently. We prove these relations by using elementary properties of Green functions and the details of the graphs. We also prove a relation between modular graph functions with six links.
Constrained Graph Optimization: Interdiction and Preservation Problems
Schild, Aaron V
2012-07-30
The maximum flow, shortest path, and maximum matching problems are a set of basic graph problems that are critical in theoretical computer science and applications. Constrained graph optimization, a variation of these basic graph problems involving modification of the underlying graph, is equally important but sometimes significantly harder. In particular, one can explore these optimization problems with additional cost constraints. In the preservation case, the optimizer has a budget to preserve vertices or edges of a graph, preventing them from being deleted. The optimizer wants to find the best set of preserved edges/vertices in which the cost constraints are satisfied and the basic graph problems are optimized. For example, in shortest path preservation, the optimizer wants to find a set of edges/vertices within which the shortest path between two predetermined points is smallest. In interdiction problems, one deletes vertices or edges from the graph with a particular cost in order to impede the basic graph problems as much as possible (for example, delete edges/vertices to maximize the shortest path between two predetermined vertices). Applications of preservation problems include optimal road maintenance, power grid maintenance, and job scheduling, while interdiction problems are related to drug trafficking prevention, network stability assessment, and counterterrorism. Computational hardness results are presented, along with heuristic methods for approximating solutions to the matching interdiction problem. Also, efficient algorithms are presented for special cases of graphs, including on planar graphs. The graphs in many of the listed applications are planar, so these algorithms have important practical implications.
On a programming language for graph algorithms
NASA Technical Reports Server (NTRS)
Rheinboldt, W. C.; Basili, V. R.; Mesztenyi, C. K.
1971-01-01
An algorithmic language, GRAAL, is presented for describing and implementing graph algorithms of the type primarily arising in applications. The language is based on a set algebraic model of graph theory which defines the graph structure in terms of morphisms between certain set algebraic structures over the node set and arc set. GRAAL is modular in the sense that the user specifies which of these mappings are available with any graph. This allows flexibility in the selection of the storage representation for different graph structures. In line with its set theoretic foundation, the language introduces sets as a basic data type and provides for the efficient execution of all set and graph operators. At present, GRAAL is defined as an extension of ALGOL 60 (revised) and its formal description is given as a supplement to the syntactic and semantic definition of ALGOL. Several typical graph algorithms are written in GRAAL to illustrate various features of the language and to show its applicability.
Efficient Graph Sequence Mining Using Reverse Search
NASA Astrophysics Data System (ADS)
Inokuchi, Akihiro; Ikuta, Hiroaki; Washio, Takashi
The mining of frequent subgraphs from labeled graph data has been studied extensively. Furthermore, much attention has recently been paid to frequent pattern mining from graph sequences. A method, called GTRACE, has been proposed to mine frequent patterns from graph sequences under the assumption that changes in graphs are gradual. Although GTRACE mines the frequent patterns efficiently, it still needs substantial computation time to mine the patterns from graph sequences containing large graphs and long sequences. In this paper, we propose a new version of GTRACE that permits efficient mining of frequent patterns based on the principle of a reverse search. The underlying concept of the reverse search is a general scheme for designing efficient algorithms for hard enumeration problems. Our performance study shows that the proposed method is efficient and scalable for mining both long and large graph sequence patterns and is several orders of magnitude faster than the original GTRACE.
Fast Approximate Quadratic Programming for Graph Matching
Vogelstein, Joshua T.; Conroy, John M.; Lyzinski, Vince; Podrazik, Louis J.; Kratzer, Steven G.; Harley, Eric T.; Fishkind, Donniell E.; Vogelstein, R. Jacob; Priebe, Carey E.
2015-01-01
Quadratic assignment problems arise in a wide variety of domains, spanning operations research, graph theory, computer vision, and neuroscience, to name a few. The graph matching problem is a special case of the quadratic assignment problem, and graph matching is increasingly important as graph-valued data is becoming more prominent. With the aim of efficiently and accurately matching the large graphs common in big data, we present our graph matching algorithm, the Fast Approximate Quadratic assignment algorithm. We empirically demonstrate that our algorithm is faster and achieves a lower objective value on over 80% of the QAPLIB benchmark library, compared with the previous state-of-the-art. Applying our algorithm to our motivating example, matching C. elegans connectomes (brain-graphs), we find that it efficiently achieves performance. PMID:25886624
Molecular graph convolutions: moving beyond fingerprints.
Kearnes, Steven; McCloskey, Kevin; Berndl, Marc; Pande, Vijay; Riley, Patrick
2016-08-01
Molecular "fingerprints" encoding structural information are the workhorse of cheminformatics and machine learning in drug discovery applications. However, fingerprint representations necessarily emphasize particular aspects of the molecular structure while ignoring others, rather than allowing the model to make data-driven decisions. We describe molecular graph convolutions, a machine learning architecture for learning from undirected graphs, specifically small molecules. Graph convolutions use a simple encoding of the molecular graph-atoms, bonds, distances, etc.-which allows the model to take greater advantage of information in the graph structure. Although graph convolutions do not outperform all fingerprint-based methods, they (along with other graph-based methods) represent a new paradigm in ligand-based virtual screening with exciting opportunities for future improvement.
The Feynman Identity for Planar Graphs
NASA Astrophysics Data System (ADS)
da Costa, G. A. T. F.
2016-08-01
The Feynman identity (FI) of a planar graph relates the Euler polynomial of the graph to an infinite product over the equivalence classes of closed nonperiodic signed cycles in the graph. The main objectives of this paper are to compute the number of equivalence classes of nonperiodic cycles of given length and sign in a planar graph and to interpret the data encoded by the FI in the context of free Lie superalgebras. This solves in the case of planar graphs a problem first raised by Sherman and sets the FI as the denominator identity of a free Lie superalgebra generated from a graph. Other results are obtained. For instance, in connection with zeta functions of graphs.
Fast approximate quadratic programming for graph matching.
Vogelstein, Joshua T; Conroy, John M; Lyzinski, Vince; Podrazik, Louis J; Kratzer, Steven G; Harley, Eric T; Fishkind, Donniell E; Vogelstein, R Jacob; Priebe, Carey E
2015-01-01
Quadratic assignment problems arise in a wide variety of domains, spanning operations research, graph theory, computer vision, and neuroscience, to name a few. The graph matching problem is a special case of the quadratic assignment problem, and graph matching is increasingly important as graph-valued data is becoming more prominent. With the aim of efficiently and accurately matching the large graphs common in big data, we present our graph matching algorithm, the Fast Approximate Quadratic assignment algorithm. We empirically demonstrate that our algorithm is faster and achieves a lower objective value on over 80% of the QAPLIB benchmark library, compared with the previous state-of-the-art. Applying our algorithm to our motivating example, matching C. elegans connectomes (brain-graphs), we find that it efficiently achieves performance.
Hierarchical structure of the logical Internet graph
NASA Astrophysics Data System (ADS)
Ge, Zihui; Figueiredo, Daniel R.; Jaiswal, Sharad; Gao, Lixin
2001-07-01
The study of the Internet topology has recently received much attention from the research community. In particular, the observation that the network graph has interesting properties, such as power laws, that might be explored in a myriad of ways. Most of the work in characterizing the Internet graph is based on the physical network graph, i.e., the connectivity graph. In this paper we investigate how logical relationships between nodes of the AS graph can be used to gain insight to its structure. We characterize the logical graph using various metrics and identify the presence of power laws in the number of customers that a provider has. Using these logical relationships we define a structural model of the AS graph. The model highlights the hierarchical nature of logical relationships and the preferential connection to larger providers. We also investigate the consistency of this model over time and observe interesting properties of the hierarchical structure.
Phillips, David J; McGlaughlin, Alec; Ruth, David; Jager, Leah R; Soldan, Anja
2015-01-01
Graph theory is increasingly being used to study brain connectivity across the spectrum of Alzheimer's disease (AD), but prior findings have been inconsistent, likely reflecting methodological differences. We systematically investigated how methods of graph creation (i.e., type of correlation matrix and edge weighting) affect structural network properties and group differences. We estimated the structural connectivity of brain networks based on correlation maps of cortical thickness obtained from MRI. Four groups were compared: 126 cognitively normal older adults, 103 individuals with Mild Cognitive Impairment (MCI) who retained MCI status for at least 3 years (stable MCI), 108 individuals with MCI who progressed to AD-dementia within 3 years (progressive MCI), and 105 individuals with AD-dementia. Small-world measures of connectivity (characteristic path length and clustering coefficient) differed across groups, consistent with prior studies. Groups were best discriminated by the Randić index, which measures the degree to which highly connected nodes connect to other highly connected nodes. The Randić index differentiated the stable and progressive MCI groups, suggesting that it might be useful for tracking and predicting the progression of AD. Notably, however, the magnitude and direction of group differences in all three measures were dependent on the method of graph creation, indicating that it is crucial to take into account how graphs are constructed when interpreting differences across diagnostic groups and studies. The algebraic connectivity measures showed few group differences, independent of the method of graph construction, suggesting that global connectivity as it relates to node degree is not altered in early AD.
Using a Corpus in a 300-Level Spanish Grammar Course
ERIC Educational Resources Information Center
Benavides, Carlos
2015-01-01
The present study examined the use and effectiveness of a large corpus--the Corpus del Español (Davies, 2002)--in a 300-level Spanish grammar university course. Students conducted hands-on corpus searches with the goal of finding concordances containing particular types of collocations (combinations of words that tend to co-occur) and tokens (any…
Grammar Is a System That Characterizes Talk in Interaction
Ginzburg, Jonathan; Poesio, Massimo
2016-01-01
Much of contemporary mainstream formal grammar theory is unable to provide analyses for language as it occurs in actual spoken interaction. Its analyses are developed for a cleaned up version of language which omits the disfluencies, non-sentential utterances, gestures, and many other phenomena that are ubiquitous in spoken language. Using evidence from linguistics, conversation analysis, multimodal communication, psychology, language acquisition, and neuroscience, we show these aspects of language use are rule governed in much the same way as phenomena captured by conventional grammars. Furthermore, we argue that over the past few years some of the tools required to provide a precise characterizations of such phenomena have begun to emerge in theoretical and computational linguistics; hence, there is no reason for treating them as “second class citizens” other than pre-theoretical assumptions about what should fall under the purview of grammar. Finally, we suggest that grammar formalisms covering such phenomena would provide a better foundation not just for linguistic analysis of face-to-face interaction, but also for sister disciplines, such as research on spoken dialogue systems and/or psychological work on language acquisition. PMID:28066279
Caught'ya Again! More Grammar with a Giggle.
ERIC Educational Resources Information Center
Kiester, Jane Bell
This teaching guide is built around a method (called the "Caught'ya" method) of teaching grammar and mechanics with humor. The guide contains story ideas and three sets of 100 Caught'ya sentences, as well as a chapter which discusses specific ways to use the Caught'ya at home. Following an introduction, the guide is divided into the…
Aspects of a Grammar of Makary Kotoko (Chadic, Cameroon)
ERIC Educational Resources Information Center
Allison, Sean David
2012-01-01
Makary Kotoko (MK), a Central Chadic B language, is spoken in the north of Cameroon just south of Lake Chad. Published works on MK to date include about a dozen articles on different aspects of the grammar of the language, primarily by H. Tourneux. The present work, which is based on a substantial corpus of recorded texts, is a systematic…
E-Learning Turkish Language and Grammar: Analyzing Learners' Behavior
ERIC Educational Resources Information Center
Georgalas, Panagiotis
2012-01-01
This study analyses the behavior and the preferences of the Greek learners of Turkish language, who use a particular e-learning website in parallel with their studies, namely: http://turkish.pgeorgalas.gr. The website offers free online material in Greek and English language for learning the Turkish language and grammar. The traffic of several…
The Foreign Language Syllabus--Grammar, Notions and Functions.
ERIC Educational Resources Information Center
Saltarelli, Mario, Ed.
1983-01-01
Papers in this journal issue concern various aspects of foreign language syllabus construction. Titles and authors are: "The Threshold Level: A Notional-Functional Syllabus" (Barbara F. Matthies); "Functions of Grammar in a Language Teaching Syllabus" (William E. Rutherford); "Communicative and Grammatical Syllabuses to…
Teacher Knowledge on Grammar Teaching: A Case Study
ERIC Educational Resources Information Center
Sarac-Suzer H. Sezgi
2007-01-01
This study aims to explore teachers' knowledge and belief on how to teach grammar to Turkish learners of English as a foreign language. It is designed as a case study. Its data and findings are limited to the selected setting which is the Department of Basic English at Hacettepe University, Turkey. The research process was composed of two stages.…
Referential Markers and Agreement Markers in Functional Discourse Grammar
ERIC Educational Resources Information Center
Hengeveld, Kees
2012-01-01
It follows from the ordering principles that are applied in Functional Discourse Grammar that the positional possibilities of markers of agreement and those of cross-reference are different. Markers of cross reference are predicted to occur closer to the verb stem, while markers of agreement would occupy peripheral positions. This paper tests…
Fluency Does Not Express Implicit Knowledge of Artificial Grammars
ERIC Educational Resources Information Center
Scott, Ryan B.; Dienes, Zoltan
2010-01-01
It is commonly held that implicit knowledge expresses itself as fluency. A perceptual clarification task was used to examine the relationship between perceptual processing fluency, subjective familiarity, and grammaticality judgments in a task frequently used to produce implicit knowledge, artificial grammar learning (AGL). Four experiments…
On the Form of Bilingual Grammars: The Phonological Component.
ERIC Educational Resources Information Center
Elerick, Charles
This research is based on the assumption that a Spanish/English bilingual is aware of the phonological and semantic relatedness of the many hundreds of pairs of transparently cognate items in the two languages. This awareness is linguistically significant in that it is reflected in the internalized grammar of the bilingual. The bilingual speaker…
Solomon Islands Pijin: Grammar Handbook. Peace Corps Language Handbook Series.
ERIC Educational Resources Information Center
Huebner, Thom; Horoi, Stephen Rex
This grammar handbook analyzes the rules of Solomon Islands Pijin and provides exercises on them. It is divided into 24 lessons. The first part of each lesson is a description of some element or function of the language, with examples; the second part is made up of oral and written exercises. The volume concludes with appendices on the personal…
Slavic in Head-Driven Phrase Structure Grammar.
ERIC Educational Resources Information Center
Borsley, Robert D., Ed.; Przepiorkowski, Adam, Ed.
The collection of essays on the properties of Slavic languages in the context of the theory of head-driven phrase structure grammar (HPSG) includes: "Typological Similarities in HPSG" (Tania Avgustinova, Wojciech Skut, Hans Uszkoreit); "Auxiliaries, Verbs and Complementizers in Polish" (Robert D. Borsley); "An Architecture…
The Strategies Approach: Effective for Reviewing Grammar and Punctuation Concepts
ERIC Educational Resources Information Center
Quible, Zane K.
2008-01-01
This article is based on results of a quasi-experimental study in which the efficacy of the strategies approach for reviewing grammar and punctuation concepts was assessed in a business communication course. The control group studied rules-based review materials; the treatment group studied strategies-based review materials. On the three sets of…
Program Evaluation: English Grammar in the Language Classroom
ERIC Educational Resources Information Center
Azimi, Mozhgan
2014-01-01
The present study wants to find out the reasons for choosing the current methods/techniques for teaching grammar and it also wants to investigate whether there is a relation between teachers' thinking and their actions in the class or not. For this reason, four language teachers were selected. The subjects were selected by non-random sampling.…
A Grammar of Southern Pomo: An Indigenous Language of California
ERIC Educational Resources Information Center
Walker, Neil Alexander
2013-01-01
Southern Pomo is a moribund indigenous language, one of seven closely related Pomoan languages once spoken in Northern California in the vicinity of the Russian River drainage, Clear Lake, and the adjacent Pacific coast. This work is the first full-length grammar of the language. It is divided into three parts. Part I introduces the sociocultural…
The Pedagogic Effectiveness of Developmental Readiness in ESL Grammar Instruction
ERIC Educational Resources Information Center
Mansouri, Fethi; Duffy, Loretta
2005-01-01
The project reported in this paper aims to test the concept of "learner developmental readiness" and its pedagogic effectiveness in the teaching of foreign language grammar. It focuses on the teaching of English as a second language (ESL) in a formal classroom context. The aim is to ascertain whether a specific teaching order based on…
Upending the Grammar of the Conventional Religious School
ERIC Educational Resources Information Center
Aron, Isa
2014-01-01
This article provides an overview and analysis of a relatively new phenomenon: congregational schools that have altered the conventional grammar of schooling, either through their structural arrangements or through their curricular approaches. Five pre-bar/bat mitzvah models are discussed: family schools, schools as communities,…
Effectiveness of Using Games in Teaching Grammar to Young Learners
ERIC Educational Resources Information Center
Yolageldili, Gulin; Arikan, Arda
2011-01-01
The primary aim of this study was to explore the effectiveness of using games in teaching grammar to young learners from the view points of Turkish EFL teachers working in primary schools. English language teacher' (n = 15) opinions were collected through a questionnaire and the results of this study demonstrated that Turkish EFL teachers have a…
What Should Be Explicit in Explicit Grammar Instruction?
ERIC Educational Resources Information Center
Nagai, Noriko; Ayano, Seiki; Okada, Keiko; Nakanishi, Takayuki
2015-01-01
This article proposes an approach to explicit grammar instruction that seeks to develop metalinguistic knowledge of the L2 and raise L2 learners' awareness of their L1, which is crucial for the success of second language acquisition (Ellis 1997, 2002). If explicit instruction is more effective than implicit instruction (Norris and Ortega 2000),…
Transfer in Artificial Grammar Learning: The Role of Repetition Information
ERIC Educational Resources Information Center
Lotz, Anja; Kinder, Annette
2006-01-01
In this article, the authors report 2 experiments that investigated the sources of information used in transfer and nontransfer tasks in artificial grammar learning. Multiple regression analyses indicated that 2 types of information about repeating elements were crucial for performance in both tasks: information about the repetition of adjacent…
An Organic Approach to the Teaching of Grammar.
ERIC Educational Resources Information Center
Nunan, David
1996-01-01
Examines the relationship between grammar and discourse and explores the implications of this relationship for language education. Suggests that the linear approach to language acquisition is problematic and does not reflect what is known about the process of acquisition. Argues for an "organic" approach. (Author/VWL)
Language Dictionaries and Grammars of Guam and Micronesia.
ERIC Educational Resources Information Center
Goetzfridt, Nicholas J.; Goniwiecha, Mark C.
The study of language reference materials, particularly dictionaries and grammar works, for languages of Guam and Micronesia includes a brief history of their evolution and an annotated bibliography. An introductory section describes the geographic situation of Micronesia and chronicles numerous periods of foreign influence: Spanish Colonization…
"Fire Your Proofreader!" Grammar Correction in the Writing Classroom
ERIC Educational Resources Information Center
Shin, Sang-Keun
2008-01-01
This article critically reviews the usefulness of grammar correction in second language writing instruction through the eyes of five second-language writers. It first examines the validity of four teaching principles that appear to influence how writing instructors approach error correction in classrooms and concludes with discussions as to why…
El Hispanohablante y la Gramatica (The Spanish Speaker and Grammar).
ERIC Educational Resources Information Center
Blanco, George M.
1994-01-01
Studied the grammatical knowledge that undergraduates specializing in bilingual education have of their mother tongue. Data collected from an entrance exam, dialog journals and a simulated oral proficiency exam indicate that these students do not have a formal knowledge of grammatical rules but do have a high level of functional grammar. (24…
What Artificial Grammar Learning Reveals about the Neurobiology of Syntax
ERIC Educational Resources Information Center
Petersson, Karl-Magnus; Folia, Vasiliki; Hagoort, Peter
2012-01-01
In this paper we examine the neurobiological correlates of syntax, the processing of structured sequences, by comparing FMRI results on artificial and natural language syntax. We discuss these and similar findings in the context of formal language and computability theory. We used a simple right-linear unification grammar in an implicit artificial…
Non-context-free grammars generating context-free languages
NASA Technical Reports Server (NTRS)
Baker, B. S.
1974-01-01
If G is a grammar such that in each non-context-free rule of G, the right side contains a string of terminals longer than any terminal string appearing between two nonterminals in the left side, then the language generated by G is context free. Six previous results follow as corollaries of this theorem.
Language Curriculum. Based on Concept Formation and Transformational Grammar.
ERIC Educational Resources Information Center
Hamel, Clara A.
The language curriculum initiated at the Rhode Island School for the Deaf consists of two stated innovations in teaching methods, which are language development through concept formation and application of transformational grammar. Description of the teaching method reveals that aurally handicapped pupils learn to analyze sentence structure by…
A Reference Grammar of Dutch, with Exercises and Key.
ERIC Educational Resources Information Center
Fehringer, Carol
This textbook provides an accessible reference grammar of the Dutch language for English-speaking students of Dutch to help consolidate their knowledge through practical exercises on a whole range of grammatical topics. It is intended both for beginners and intermediate level students. Advanced learners of Dutch wishing to review particular…
Do Null Subjects (Mis-)Trigger Pro-Drop Grammars?
ERIC Educational Resources Information Center
Frazier, Lyn
2015-01-01
Native speakers of English regularly hear sentences without overt subjects. Nevertheless, they maintain a [[superscript -]pro] grammar that requires sentences to have an overt subject. It is proposed that listeners of English recognize that speakers reduce predictable material and thus attribute null subjects to this process, rather than changing…
La nomenclature grammaticale (version 1975) (Grammar Nomenclature 1975 Version]).
ERIC Educational Resources Information Center
Mitterand, Henri
1980-01-01
Reviews a glossary of grammatical terms published by the French government for use in the public schools and finds it lacking both theoretically and pedagogically. A detailed analysis describes its numerous shortcomings and underlines the authors' misconception that progress in teaching grammar depends entirely on standardization of terminology.…
From Grammar-Translation to Direct to Audiolingual to What?
ERIC Educational Resources Information Center
Hammerly, Hector M.
This article on language instruction elaborates on assumptions, procedures, and techniques used in the implementation of various teaching methodologies. Equally critical of the grammar-translation method and the direct method, the author points out the strengths of the audiolingual approach. The lack of controlled, scientific investigation of the…
Mauritanian Arabic. Grammar Handbook. Peace Corps Language Handbook Series.
ERIC Educational Resources Information Center
Francis, Timothy P.; Hanchey, Stephen
A handbook to the grammar of Mauritanian Arabic (Hassaniya) is intended for Peace Corps volunteers, and is designed to focus attention on proper grammatical forms. Lesson topics include the article, personal pronouns, possessive pronouns, negation of the implied verb "to be," noun gender, adjective gender, number, "there is/are and…
Using Webquest in Learning Grammar: Students' Perceptions in Higher Education
ERIC Educational Resources Information Center
Irzawati, Ira
2013-01-01
Webquest is an internet based learning tool that can be used by students in learning English. This study investigates students' perceptions about the use of Webquest to support learning grammar in Higher Education. Seventy-two of second semester students were involved as participants in this study. Questionnaire and interview were used to collect…
Computer-Assisted Writing Revision: Development of a Grammar Checker.
ERIC Educational Resources Information Center
Liou, Hsien-Chin
A computerized grammar checker was developed to assist teachers of English as a Second Language in editing student compositions. The first stage of development consisted of an error analysis of 125 writing samples collected from students. The 1,659 errors found were classified into 14 main types and 93 subtypes. This analysis served as the basis…
The Grammar of Ch'orti' Maya Folktales
ERIC Educational Resources Information Center
Dugan, James Timothy
2014-01-01
This study describes the grammar of the Ch'orti' Maya language as it appears in a collection of oral literature. I collected the stories that form the basis of this study in and around Jocotan, Guatemala, during 2004 and 2005. I worked with bilingual story-tellers to make audio recordings of the original Ch'orti'-language tales, produce textual…
Ewe (for Togo): Grammar Handbook. Peace Corps Language Handbook Series.
ERIC Educational Resources Information Center
Kozelka, Paul R.
This handbook is composed of: (1) 20 grammar lessons; (2) an introduction to the handbook and to the Ewe language; (3) an appendix presenting the most important differences between Ewe and Mina, the lingua franca in the capital and in markets, offices, and work-sites throughout Togo; (4) answers to written summary exercises; (5) an Ewe-English…
Input-Based Grammar Pedagogy: A Comparison of Two Possibilities
ERIC Educational Resources Information Center
Marsden, Emma
2005-01-01
This article presents arguments for using listening and reading activities as an option for techniques in grammar pedagogy. It describes two possible approaches: Processing Instruction (PI) and Enriched Input (EI), and examples of their key features are included in the appendices. The article goes on to report on a classroom based quasi-experiment…
Noam Chomsky Writes to Mrs. Davis about Grammar and Education.
ERIC Educational Resources Information Center
English Education, 1984
1984-01-01
In a personal letter, Chomsky suggests that while the study of grammar has little detectable effect on writing ability, it can, as a branch of science, help students learn how (and why) to think about hard and intriguing questions and to develop natural curiosity. (HOD)
The Story of English Grammar in United States Schools
ERIC Educational Resources Information Center
Kolln, Martha; Hancock, Craig
2005-01-01
This article assumes the value of a scientifically grounded, rhetorically focused, professionally supported, and publicly embraced grammar within the public schools and examines the past century of practices within the United States from that perspective. It describes a brief renaissance in the 50's and early 60's, inspired largely by the…
A STUDENT'S REFERENCE GRAMMAR OF MODERN FORMAL INDONESIAN.
ERIC Educational Resources Information Center
MACDONALD, R. ROSS; SOENJONO, DARJOWIDJOJO
THE INDONESIAN DESCRIBED IN THIS GRAMMAR IS THE FORMAL LANGUAGE USED IN PUBLISHED TEXTS RATHER THAN THE COLLOQUIAL LANGUAGE. ALL OF THE TEXTS USED WERE PUBLISHED BETWEEN 1945 AND 1966 AND THEY INCLUDE POLITICAL SPEECHES, LEGAL DOCUMENTS, AND TEXTBOOKS. SINCE THIS BOOK WAS DESIGNED PRIMARILY FOR GENERAL STUDENTS OF THE INDONESIAN LANGUAGE AND ONLY…
Functional Grammar in the ESL Classroom: Noticing, Exploring and Practicing
ERIC Educational Resources Information Center
Lock, Graham; Jones, Rodney
2011-01-01
A set of easy to use techniques helps students discover for themselves how grammar works in real world contexts and how grammatical choices are not just about form but about meaning. Sample teaching ideas, covering a wide range of grammatical topics including verb tense, voice, reference and the organization of texts, accompanies each procedure.…
UZBEK STRUCTURAL GRAMMAR. URALIC AND ALTAIC SERIES, VOLUME 18.
ERIC Educational Resources Information Center
SJOBERG, ANDREE F.
THIS GRAMMAR OF THE UZBEK LANGUAGES, THE MOST IMPORTANT IN THE SOUTHEASTERN GROUP OF TURKIC LANGUAGES, IS BASED ON THE EDUCATED DIALECT OF TASHKENT IN UZBEKISTAN, USSR. UZBEK IS SPOKEN TODAY BY APPROXIMATELY SEVEN MILLION PEOPLE IN UZBEKISTAN AND ADJOINING REPUBLICS OF SOVIET CENTRAL ASIA, AND IN UZBEK COMMUNITIES SCATTERED THROUGHOUT THE MIDDLE…