Science.gov

Sample records for matrix graph grammars

  1. Mathematical formula recognition using graph grammar

    NASA Astrophysics Data System (ADS)

    Lavirotte, Stephane; Pottier, Loic

    1998-04-01

    This paper describes current results of Ofr, a system for extracting and understanding mathematical expressions in documents. Such a tool could be really useful to be able to re-use knowledge in scientific books which are not available in electronic form. We currently also study use of this system for direct input of formulas with a graphical tablet for computer algebra system softwares. Existing solutions for mathematical recognition have problems to analyze 2D expressions like vectors and matrices. This is because they often try to use extended classical grammar to analyze formulas, relatively to baseline. But a lot of mathematical notations do not respect rules for such a parsing and that is the reason why they fail to extend text parsing technic. We investigate graph grammar and graph rewriting as a solution to recognize 2D mathematical notations. Graph grammar provide a powerful formalism to describe structural manipulations of multi-dimensional data. The main two problems to solve are ambiguities between rules of grammar and construction of graph.

  2. Graphs and Grammars for Histology: An Introduction

    PubMed Central

    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.

  3. An approach to multiscale modelling with graph grammars

    PubMed Central

    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

  4. An approach to multiscale modelling with graph grammars.

    PubMed

    Ong, Yongzhi; Streit, Katarína; Henke, Michael; Kurth, Winfried

    2014-09-01

    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. 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. 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. 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.

  5. Conceptual graph grammar--a simple formalism for sublanguage.

    PubMed

    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.

  6. 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.

  7. Low-Rank Matrix Factorization With Adaptive Graph Regularizer.

    PubMed

    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.

  8. Research on the Top-Down Parsing Method for Context-Sensitive Graph Grammars.

    PubMed

    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.

  9. Graph Regularized Nonnegative Matrix Factorization for Data Representation.

    PubMed

    Cai, Deng; He, Xiaofei; Han, Jiawei; Huang, Thomas S

    2011-08-01

    Matrix factorization techniques have been frequently applied in information retrieval, computer vision, and pattern recognition. Among them, Nonnegative Matrix Factorization (NMF) has received considerable attention due to its psychological and physiological interpretation of naturally occurring data whose representation may be parts based in the human brain. On the other hand, from the geometric perspective, the data is usually sampled from a low-dimensional manifold embedded in a high-dimensional ambient space. One then hopes to find a compact representation,which uncovers the hidden semantics and simultaneously respects the intrinsic geometric structure. In this paper, we propose a novel algorithm, called Graph Regularized Nonnegative Matrix Factorization (GNMF), for this purpose. In GNMF, an affinity graph is constructed to encode the geometrical information and we seek a matrix factorization, which respects the graph structure. Our empirical study shows encouraging results of the proposed algorithm in comparison to the state-of-the-art algorithms on real-world problems.

  10. Automated graph regularized projective nonnegative matrix factorization for document clustering.

    PubMed

    Pei, Xiaobing; Wu, Tao; Chen, Chuanbo

    2014-10-01

    In this paper, a novel projective nonnegative matrix factorization (PNMF) method for enhancing the clustering performance is presented, called automated graph regularized projective nonnegative matrix factorization (AGPNMF). The idea of AGPNMF is to extend the original PNMF by incorporating the automated graph regularized constraint into the PNMF decomposition. The key advantage of this approach is that AGPNMF simultaneously finds graph weights matrix and dimensionality reduction of data. AGPNMF seeks to extract the data representation space that preserves the local geometry structure. This character makes AGPNMF more intuitive and more powerful than the original method for clustering tasks. The kernel trick is used to extend AGPNMF model related to the input space by some nonlinear map. The proposed method has been applied to the problem of document clustering using the well-known Reuters-21578, TDT2, and SECTOR data sets. Our experimental evaluations show that the proposed method enhances the performance of PNMF for document clustering.

  11. Link prediction on evolving graphs using matrix and tensor factorizations.

    SciTech Connect

    Dunlavy, Daniel M.; Acar, Evrim; Kolda, Tamara Gibson

    2010-06-01

    The data in many disciplines such as social networks, web analysis, etc. is link-based, and the link structure can be exploited for many different data mining tasks. In this paper, we consider the problem of temporal link prediction: Given link data for time periods 1 through T, can we predict the links in time period T + 1? Specifically, we look at bipartite graphs changing over time and consider matrix- and tensor-based methods for predicting links. We present a weight-based method for collapsing multi-year data into a single matrix. We show how the well-known Katz method for link prediction can be extended to bipartite graphs and, moreover, approximated in a scalable way using a truncated singular value decomposition. Using a CANDECOMP/PARAFAC tensor decomposition of the data, we illustrate the usefulness of exploiting the natural three-dimensional structure of temporal link data. Through several numerical experiments, we demonstrate that both matrix- and tensor-based techniques are effective for temporal link prediction despite the inherent difficulty of the problem.

  12. Application of Bron-Kerbosch algorithm in graph clustering using complement matrix

    NASA Astrophysics Data System (ADS)

    Antoro, S. C.; Sugeng, K. A.; Handari, B. D.

    2017-07-01

    Maximal clique enumeration is a graph clustering method for finding all vertices that have the most influence in a graph. The Bron-Kerbosch algorithm is one of the fastest algorithms to find all maximal cliques. Hence, this paper will focus on that algorithm to find all maximal cliques. Counting all maximal cliques of a graph usually uses an adjacency matrix of the graph to find all vertices in the graph that have the most influence. But, in this paper, a complement matrix of a graph will be used in counting all maximal cliques. This research uses a graph that represents a domestic flight route of one of the airlines in Indonesia. By using Bron-Kerbosch algorithm, all maximal cliques of the graph will be listed, so that it will come up with the vertices which are the most influential in this graph. The graph will be represented in complement matrix. The result of applying the Bron-Kerbosch algorithm with the complement matrix of graph will determine vertices that have the most influence in the graph. Besides that, by using a complement matrix, the result gives more information on the vertices which are only connected to the vertices that have the most influence.

  13. A review on eigen values of adjacency matrix of graph with cliques

    NASA Astrophysics Data System (ADS)

    Carnia, Ema; Suyudi, Moch.; Aisah, Isah; Supriatna, Asep K.

    2017-08-01

    The paper reviews the applications of eigen value in different areas. One of the area is in the analysis of graphs coming from networks. The development of theory regarding the eigenvalues and its maximum eigenvalue of the adjacency matrix arising from a general graph is already well-established. Here we review some notions from different context, i.e. led by observation of some simple experiments regarding the relation between graph, cliques, and the eigen values of the adjacency matrix. We focus on regular graphs having one or more cliques in their graph structures. We do some numerical experiment on the computation of the eigen values of the adjacency matrix and show some patterns on the relation between the structure of the graph (e.g. the maximum cliques, chromatic number) and the eigen values of the adjacency matrix. By observing these patterns we find some conclusion, such as: i. the maximum clique of a complete graph is given by the largest eigen value plus one; ii. the maximum clique of a cycle graph (simple incomplete regular graph) equals the largest eigen value, in which the value is two; iii. the maximum multiplicity of the eigen values of a cycle graph is two. Future direction of the development is also presented based on the careful analysis of the existing development.

  14. Hermitian-Randić matrix and Hermitian-Randić energy of mixed graphs.

    PubMed

    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.

  15. Tracing retinal blood vessels by matrix-forest theorem of directed graphs.

    PubMed

    Cheng, Li; De, Jaydeep; Zhang, Xiaowei; Lin, Feng; Li, Huiqi

    2014-01-01

    This paper aims to trace retinal blood vessel trees in fundus images. This task is far from being trivial as the crossover of vessels are commonly encountered in image-based vessel networks. Meanwhile it is often crucial to separate the vessel tree structures in applications such as diabetic retinopathy analysis. In this work, a novel directed graph based approach is proposed to cast the task as label propagation over directed graphs, such that the graph is to be partitioned into disjoint sub-graphs, or equivalently, each of the vessel trees is traced and separated from the rest of the vessel network. Then the tracing problem is addressed by making novel usage of the matrix-forest theorem in algebraic graph theory. Empirical experiments on synthetic as well as publicly available fundus image datasets demonstrate the applicability of our approach.

  16. Automated Program Recognition by Graph Parsing

    DTIC Science & Technology

    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

  17. 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.

  18. Complex graph matrix representations and characterizations of proteomic maps and chemically induced changes to proteomes.

    PubMed

    Balasubramanian, Krishnan; Khokhani, Kanan; Basak, Subhash C

    2006-05-01

    We have presented a complex graph matrix representation to characterize proteomics maps obtained from 2D-gel electrophoresis. In this method, each bubble in a 2D-gel proteomics map is represented by a complex number with components which are charge and mass. Then, a graph with complex weights is constructed by connecting the vertices in the relative order of abundance. This yields adjacency matrices and distance matrices of the proteomics graph with complex weights. We have computed the spectra, eigenvectors, and other properties of complex graphs and the Euclidian/graph distance obtained from the complex graphs. The leading eigenvalues and eigenvectors and, likewise, the smallest eigenvalues and eigenvectors, and the entire graph spectral patterns of the complex matrices derived from them yield novel weighted biodescriptors that characterize proteomics maps with information of charge and masses of proteins. We have also applied these eigenvector and eigenvalue maps to contrast the normal cells and cells exposed to four peroxisome proliferators, namely, clofibrate, diethylhexyl phthalate (DEHP), perfluorodecanoic acid (PFDA), and perfluoroctanoic acid (PFOA). Our complex eigenspectra show that the proteomic response induced by DEHP differs from the corresponding responses of other three chemicals consistent with their chemical structures and properties.

  19. A matrix-algebraic formulation of distributed-memory maximal cardinality matching algorithms in bipartite graphs

    DOE PAGES

    Azad, Ariful; Buluç, Aydın

    2016-05-16

    We describe parallel algorithms for computing maximal cardinality matching in a bipartite graph on distributed-memory systems. Unlike traditional algorithms that match one vertex at a time, our algorithms process many unmatched vertices simultaneously using a matrix-algebraic formulation of maximal matching. This generic matrix-algebraic framework is used to develop three efficient maximal matching algorithms with minimal changes. The newly developed algorithms have two benefits over existing graph-based algorithms. First, unlike existing parallel algorithms, cardinality of matching obtained by the new algorithms stays constant with increasing processor counts, which is important for predictable and reproducible performance. Second, relying on bulk-synchronous matrix operations,more » these algorithms expose a higher degree of parallelism on distributed-memory platforms than existing graph-based algorithms. We report high-performance implementations of three maximal matching algorithms using hybrid OpenMP-MPI and evaluate the performance of these algorithm using more than 35 real and randomly generated graphs. On real instances, our algorithms achieve up to 200 × speedup on 2048 cores of a Cray XC30 supercomputer. Even higher speedups are obtained on larger synthetically generated graphs where our algorithms show good scaling on up to 16,384 cores.« less

  20. A matrix-algebraic formulation of distributed-memory maximal cardinality matching algorithms in bipartite graphs

    SciTech Connect

    Azad, Ariful; Buluç, Aydın

    2016-05-16

    We describe parallel algorithms for computing maximal cardinality matching in a bipartite graph on distributed-memory systems. Unlike traditional algorithms that match one vertex at a time, our algorithms process many unmatched vertices simultaneously using a matrix-algebraic formulation of maximal matching. This generic matrix-algebraic framework is used to develop three efficient maximal matching algorithms with minimal changes. The newly developed algorithms have two benefits over existing graph-based algorithms. First, unlike existing parallel algorithms, cardinality of matching obtained by the new algorithms stays constant with increasing processor counts, which is important for predictable and reproducible performance. Second, relying on bulk-synchronous matrix operations, these algorithms expose a higher degree of parallelism on distributed-memory platforms than existing graph-based algorithms. We report high-performance implementations of three maximal matching algorithms using hybrid OpenMP-MPI and evaluate the performance of these algorithm using more than 35 real and randomly generated graphs. On real instances, our algorithms achieve up to 200 × speedup on 2048 cores of a Cray XC30 supercomputer. Even higher speedups are obtained on larger synthetically generated graphs where our algorithms show good scaling on up to 16,384 cores.

  1. Determinant of antiadjacency matrix of union and join operation from two disjoint of several classes of graphs

    NASA Astrophysics Data System (ADS)

    Edwina, M.; Sugeng, K. A.

    2017-07-01

    Let G be a graph with V(G) = {v1, …, vn} and E(G) = {e1, …, .em}. We only consider undirected graphs with no multiple edges in this paper. The adjacency matrix of G, denoted by A(G), is the n × n matrix A = [aij], where aij = 1 if e = vivj ∈ E(G) or otherwise aij = 0. The anti adjacency matrix of G, denoted by B(G), is the n × n matrix B = [bij], where bij = 0 if e = vivj ∈ E(G) or otherwise bij = 1. Properties of the determinant of the adjacency matrix of some simple graphs have been studied by many researchers. However, the determinant of the anti-adjacency matrix has not been explored yet. If G1 and G2 are disjoint graphs, then the joining of two graphs G1 and G2, denoted G1 ∇ G2 is defined by taking copies of G1 and G2 and adding edges so that each vertex in G1 is adjacent to every vertex in G2. In this paper, we show the properties of the determinant of joining two graphs, G1 and G2. Union of two graphs, denote G1 ∪ G2 is a graph formed by taking copies of G1 and G2. The objectives of this paper are to identify some properties of the determinant anti adjacency matrix of joining and union operation from two disjoint graphs. This paper also emphasizes on investigating the determinant of some special graph class formed by joining and unioning operation of two disjoint of several classes of graphs, such as Bipartite graphs, Cycles, Complete graphs, Stars, and Wheels.

  2. Improving the Communication Pattern in Matrix-Vector Operations for Large Scale-Free Graphs by Disaggregation

    SciTech Connect

    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.

  3. Graph-preserving sparse nonnegative matrix factorization with application to facial expression recognition.

    PubMed

    Zhi, Ruicong; Flierl, Markus; Ruan, Qiuqi; Kleijn, W Bastiaan

    2011-02-01

    In this paper, a novel graph-preserving sparse nonnegative matrix factorization (GSNMF) algorithm is proposed for facial expression recognition. The GSNMF algorithm is derived from the original NMF algorithm by exploiting both sparse and graph-preserving properties. The latter may contain the class information of the samples. Therefore, GSNMF can be conducted as an unsupervised or a supervised dimension reduction method. A sparse representation of the facial images is obtained by minimizing the l(1)-norm of the basis images. Furthermore, according to the graph embedding theory, the neighborhood of the samples is preserved by retaining the graph structure in the mapped space. The GSNMF decomposition transforms the high-dimensional facial expression images into a locality-preserving subspace with sparse representation. To guarantee convergence, we use the projected gradient method to calculate the nonnegative solution of GSNMF. Experiments are conducted on the JAFFE database and the Cohn-Kanade database with unoccluded and partially occluded facial images. The results show that the GSNMF algorithm provides better facial representations and achieves higher recognition rates than nonnegative matrix factorization. Moreover, GSNMF is also more robust to partial occlusions than other tested methods.

  4. Genetic algorithm and graph theory based matrix factorization method for online friend recommendation.

    PubMed

    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.

  5. Exact scattering matrix of graphs in magnetic field and quantum noise

    SciTech Connect

    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.

  6. Experimental and numerical investigation of the reflection coefficient and the distributions of Wigner's reaction matrix for irregular graphs with absorption.

    PubMed

    Lawniczak, Michał; Hul, Oleh; Bauch, Szymon; Seba, Petr; Sirko, Leszek

    2008-05-01

    We present the results of an experimental and numerical study of the distribution of the reflection coefficient P(R) and the distributions of the imaginary P(v) and the real P(u) parts of the Wigner reaction K matrix for irregular fully connected hexagon networks (graphs) in the presence of strong absorption. In the experiment we used microwave networks, which were built of coaxial cables and attenuators connected by joints. In the numerical calculations experimental networks were described by quantum fully connected hexagon graphs. The presence of absorption introduced by attenuators was modeled by optical potentials. The distribution of the reflection coefficient P(R) and the distributions of the reaction K matrix were obtained from measurements and numerical calculations of the scattering matrix S of the networks and graphs, respectively. We show that the experimental and numerical results are in good agreement with the exact analytic ones obtained within the framework of random matrix theory.

  7. Graph Theory

    SciTech Connect

    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.

  8. 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.

  9. Teaching Grammar

    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…

  10. Teaching Grammar

    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…

  11. Limited-memory fast gradient descent method for graph regularized nonnegative matrix factorization.

    PubMed

    Guan, Naiyang; Wei, Lei; Luo, Zhigang; Tao, Dacheng

    2013-01-01

    Graph regularized nonnegative matrix factorization (GNMF) decomposes a nonnegative data matrix X[Symbol:see text]R(m x n) to the product of two lower-rank nonnegative factor matrices, i.e.,W[Symbol:see text]R(m x r) and H[Symbol:see text]R(r x n) (r < min {m,n}) and aims to preserve the local geometric structure of the dataset by minimizing squared Euclidean distance or Kullback-Leibler (KL) divergence between X and WH. The multiplicative update rule (MUR) is usually applied to optimize GNMF, but it suffers from the drawback of slow-convergence because it intrinsically advances one step along the rescaled negative gradient direction with a non-optimal step size. Recently, a multiple step-sizes fast gradient descent (MFGD) method has been proposed for optimizing NMF which accelerates MUR by searching the optimal step-size along the rescaled negative gradient direction with Newton's method. However, the computational cost of MFGD is high because 1) the high-dimensional Hessian matrix is dense and costs too much memory; and 2) the Hessian inverse operator and its multiplication with gradient cost too much time. To overcome these deficiencies of MFGD, we propose an efficient limited-memory FGD (L-FGD) method for optimizing GNMF. In particular, we apply the limited-memory BFGS (L-BFGS) method to directly approximate the multiplication of the inverse Hessian and the gradient for searching the optimal step size in MFGD. The preliminary results on real-world datasets show that L-FGD is more efficient than both MFGD and MUR. To evaluate the effectiveness of L-FGD, we validate its clustering performance for optimizing KL-divergence based GNMF on two popular face image datasets including ORL and PIE and two text corpora including Reuters and TDT2. The experimental results confirm the effectiveness of L-FGD by comparing it with the representative GNMF solvers.

  12. Limited-Memory Fast Gradient Descent Method for Graph Regularized Nonnegative Matrix Factorization

    PubMed Central

    Guan, Naiyang; Wei, Lei; Luo, Zhigang; Tao, Dacheng

    2013-01-01

    Graph regularized nonnegative matrix factorization (GNMF) decomposes a nonnegative data matrix to the product of two lower-rank nonnegative factor matrices, i.e., and () and aims to preserve the local geometric structure of the dataset by minimizing squared Euclidean distance or Kullback-Leibler (KL) divergence between X and WH. The multiplicative update rule (MUR) is usually applied to optimize GNMF, but it suffers from the drawback of slow-convergence because it intrinsically advances one step along the rescaled negative gradient direction with a non-optimal step size. Recently, a multiple step-sizes fast gradient descent (MFGD) method has been proposed for optimizing NMF which accelerates MUR by searching the optimal step-size along the rescaled negative gradient direction with Newton's method. However, the computational cost of MFGD is high because 1) the high-dimensional Hessian matrix is dense and costs too much memory; and 2) the Hessian inverse operator and its multiplication with gradient cost too much time. To overcome these deficiencies of MFGD, we propose an efficient limited-memory FGD (L-FGD) method for optimizing GNMF. In particular, we apply the limited-memory BFGS (L-BFGS) method to directly approximate the multiplication of the inverse Hessian and the gradient for searching the optimal step size in MFGD. The preliminary results on real-world datasets show that L-FGD is more efficient than both MFGD and MUR. To evaluate the effectiveness of L-FGD, we validate its clustering performance for optimizing KL-divergence based GNMF on two popular face image datasets including ORL and PIE and two text corpora including Reuters and TDT2. The experimental results confirm the effectiveness of L-FGD by comparing it with the representative GNMF solvers. PMID:24204761

  13. Departure of some parameter-dependent spectral statistics of irregular quantum graphs from random matrix theory predictions.

    PubMed

    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)) .

  14. Group Grammar

    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.

  15. 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.

  16. Grammar Games

    ERIC Educational Resources Information Center

    Brown, Kim

    2004-01-01

    The mere mention of a grammar lesson can set students' eyes rolling. The fun activities described in this article can turn those blank looks into smiles. Here, the author presents grammar games namely: (1) noun tennis; (2) the minister's cat; (3) kids take action; (4) what's my adverb?; (5) and then I saw...; and (6) grammar sing-along.

  17. Mungbam Grammar

    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…

  18. Mungbam Grammar

    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…

  19. Categorial Grammars.

    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…

  20. Random grammars

    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

  1. Graphs, matrices, and the GraphBLAS: Seven good reasons

    DOE PAGES

    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

  2. Graphs, matrices, and the GraphBLAS: Seven good reasons

    SciTech Connect

    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.

  3. The determinant of an antiadjacency matrix of a directed cycle graph with chords

    NASA Astrophysics Data System (ADS)

    Diwyacitta, D.; Putra, A. P.; Sugeng, K. A.; Utama, S.

    2017-07-01

    In graph theory, the robustness of a network measures its resilience (in terms of connectivity) to either removal of network nodes or edges. Using algebraic connectivity is one of the best way to measure the robustness of a network. The higher algebraic connectivity means more robust network. The goal of this work is to improve the robustness of an existing air transportation network. It can be accomplished by adding edges (routes) to the network. However, due to limited budget and aircraft, the routes to be added have to be chosen carefully. The best routes to be added are the routes that will yield the highest algebraic connectivity when they were added to the network. This problem of choosing the best routes to be added is called flight routes addition. In this paper, the flight routes addition is solved using Tabu Search method with the algebraic connectivity component to choose two new lines to strengthening the robustness of the flight routes. We only consider the robustness and do not.

  4. Grammar Matters

    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…

  5. Grammar Matters

    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…

  6. Grammar Myths

    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…

  7. Grammar Myths

    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…

  8. Holistic Grammar.

    ERIC Educational Resources Information Center

    Pierstorff, Don K.

    1981-01-01

    Parodies holistic approaches to education. Explains an educational approach which simultaneously teaches grammar and arithmetic. Lauds the advantages of the approach as high student attrition, ease of grading, and focus on developing the reptilian portion of the brain. Points out common errors made by students. (AYC)

  9. 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…

  10. 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…

  11. Application of matrix-valued integral continued fractions to spectral problems on periodic graphs with defects

    NASA Astrophysics Data System (ADS)

    Kutsenko, Anton A.

    2017-06-01

    We show that spectral problems for periodic operators on lattices with embedded defects of lower dimensions can be solved with the help of matrix-valued integral continued fractions. While these continued fractions are usual in the approximation theory, they are less known in the context of spectral problems. We show that the spectral points can be expressed as zeros of determinants of the continued fractions. They are also useful in the analysis of inverse problems (one-to-one correspondence between spectral data and defects). Finally, the explicit formula for the resolvent in terms of the continued fractions is provided. We apply some of the results to the Schrödinger operator acting on graphene with line and point defects.

  12. Grammars for People.

    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)

  13. Intrinsic graph structure estimation using graph Laplacian.

    PubMed

    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.

  14. 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…

  15. Grammar! A Conference Report.

    ERIC Educational Resources Information Center

    King, Lid, Ed.; Boaks, Peter, Ed.

    Papers from a conference on the teaching of grammar, particularly in second language instruction, include: "Grammar: Acquisition and Use" (Richard Johnstone); "Grammar and Communication" (Brian Page); "Linguistic Progression and Increasing Independence" (Bernardette Holmes); "La grammaire? C'est du bricolage!" ("Grammar? That's Hardware!") (Barry…

  16. 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…

  17. Performance of children with developmental dyslexia on high and low topological entropy artificial grammar learning task.

    PubMed

    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.

  18. Graphing Matters.

    ERIC Educational Resources Information Center

    Paine, Carolyn

    1983-01-01

    An explanation is given of the uses of graphs for conveying information pictorially. Picture, bar, line, and area graphs are illustrated. Graphing projects for science, social studies, mathematics, economics, and language arts are listed, and teaching tips are suggested. (FG)

  19. Completeness and regularity of generalized fuzzy graphs.

    PubMed

    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.

  20. Tree-bank grammars

    SciTech Connect

    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.

  1. Graph Library

    SciTech Connect

    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.

  2. Spectral fluctuations of quantum graphs

    SciTech Connect

    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.

  3. 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…

  4. The Grammar Gallimaufry: Teaching Students to Challenge the Grammar Gods

    ERIC Educational Resources Information Center

    House, Jeff

    2009-01-01

    How a person teaches grammar depends on what he or she believes it does. Some see grammar as a set of rules, inherited from wise forefathers. For them, teaching grammar means making students aware of, and then holding them to, these rules. Others see grammar as an expression of style, an invitation to the writer to explore how to create a…

  5. 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…

  6. The New English Grammar.

    ERIC Educational Resources Information Center

    Thompson, Charles Lamar

    This "new English grammar" textbook blends four systems of grammar: (1) the traditional, providing most of the terminology; (2) the historical, providing the historical background; (3) the structural, providing the sentence patterns; and (4) the transformational, providing the variations of the sentence patterns. The author points out the…

  7. 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)

  8. A Grammar of Belep

    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…

  9. A Papago Grammar.

    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…

  10. 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)

  11. A Grammar of Belep

    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…

  12. Demythifying French Grammar.

    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…

  13. Necessity of Grammar Teaching

    ERIC Educational Resources Information Center

    Zhang, Jianyun

    2009-01-01

    Grammar is often misunderstood in the language teaching field. The misconception lies in the view that grammar is a collection of arbitrary rules about static structures in the language. Further questionable claims are that the structures do not have to be thought, learners will acquire them on their own, or if the structures are taught, the…

  14. 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…

  15. Phonology without universal grammar.

    PubMed

    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.

  16. Phonology without universal grammar

    PubMed Central

    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

  17. Mathematical foundations of the GraphBLAS

    DOE PAGES

    Kepner, Jeremy; Aaltonen, Peter; Bader, David; ...

    2016-12-01

    The GraphBLAS standard (GraphBlas.org) is being developed to bring the potential of matrix-based graph algorithms to the broadest possible audience. Mathematically, the GraphBLAS 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 study provides an introduction to the mathematics of the GraphBLAS. Graphs represent connections between vertices with edges. Matrices can represent a wide range of graphs using adjacency matrices or incidence matrices. Adjacency matrices are often easier to analyze while incidence matrices are often better for representing data. Fortunately, themore » two are easily connected by matrix multiplication. A key feature of matrix mathematics is that a very small number of matrix operations can be used to manipulate a very wide range of graphs. This composability of a small number of operations is the foundation of the GraphBLAS. A standard such as the GraphBLAS can only be effective if it has low performance overhead. Finally, performance measurements of prototype GraphBLAS implementations indicate that the overhead is low.« less

  18. Mathematical foundations of the GraphBLAS

    SciTech Connect

    Kepner, Jeremy; Aaltonen, Peter; Bader, David; Buluc, Aydin; Franchetti, Franz; Gilbert, John; Hutchison, Dylan; Kumar, Manoj; Lumsdaine, Andrew; Meyerhenke, Henning; McMillan, Scott; Yang, Carl; Owens, John D.; Zalewski, Marcin; Mattson, Timothy; Moreira, Jose

    2016-12-01

    The GraphBLAS standard (GraphBlas.org) is being developed to bring the potential of matrix-based graph algorithms to the broadest possible audience. Mathematically, the GraphBLAS 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 study provides an introduction to the mathematics of the GraphBLAS. Graphs represent connections between vertices with edges. Matrices can represent a wide range of graphs using adjacency matrices or incidence matrices. Adjacency matrices are often easier to analyze while incidence matrices are often better for representing data. Fortunately, the two are easily connected by matrix multiplication. A key feature of matrix mathematics is that a very small number of matrix operations can be used to manipulate a very wide range of graphs. This composability of a small number of operations is the foundation of the GraphBLAS. A standard such as the GraphBLAS can only be effective if it has low performance overhead. Finally, performance measurements of prototype GraphBLAS implementations indicate that the overhead is low.

  19. Parsing and translation of (attributed) expansive graph languages for scene analysis.

    PubMed

    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.

  20. 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…

  1. 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…

  2. Comments on Skinner's grammar

    PubMed Central

    Mabry, John H.

    1993-01-01

    The strong tradition of “school room” grammars may have had a negative influence on the reception given a functional analysis of verbal behavior, both within and without the field of behavior analysis. Some of the failings of those traditional grammars, and their largely prescriptive nature were outlined through reference to other critics, and conflicting views. Skinner's own treatment of grammatical issues was presented, emphasizing his view of a functional unit and his use of the autoclitic and intraverbal functions to describe alternatives to a formal or structural analysis. Finally, the relevance of stimulus control variables to some recurring questions about verbal behavior and, specifically grammar, were mentioned. PMID:22477082

  3. Identifying group discriminative and age regressive sub-networks from DTI-based connectivity via a unified framework of non-negative matrix factorization and graph embedding

    PubMed Central

    Ghanbari, Yasser; Smith, Alex R.; Schultz, Robert T.; Verma, Ragini

    2014-01-01

    Diffusion tensor imaging (DTI) offers rich insights into the physical characteristics of white matter (WM) fiber tracts and their development in the brain, facilitating a network representation of brain’s traffic pathways. Such a network representation of brain connectivity has provided a novel means of investigating brain changes arising from pathology, development or aging. The high dimensionality of these connectivity networks necessitates the development of methods that identify the connectivity building blocks or sub-network components that characterize the underlying variation in the population. In addition, the projection of the subject networks into the basis set provides a low dimensional representation of it, that teases apart different sources of variation in the sample, facilitating variation-specific statistical analysis. We propose a unified framework of non-negative matrix factorization and graph embedding for learning sub-network patterns of connectivity by their projective non-negative decomposition into a reconstructive basis set, as well as, additional basis sets representing variational sources in the population like age and pathology. The proposed framework is applied to a study of diffusion-based connectivity in subjects with autism that shows localized sparse sub-networks which mostly capture the changes related to pathology and developmental variations. PMID:25037933

  4. Knowing Chinese character grammar.

    PubMed

    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.

  5. Graph Coarsening for Path Finding in Cybersecurity Graphs

    SciTech Connect

    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.

  6. 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…

  7. 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…

  8. 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)

  9. 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)

  10. Robust (semi) nonnegative graph embedding.

    PubMed

    Zhang, Hanwang; Zha, Zheng-Jun; Yang, Yang; Yan, Shuicheng; Chua, Tat-Seng

    2014-07-01

    Nonnegative matrix factorization (NMF) has received considerable attention in image processing, computer vision, and patter recognition. An important variant of NMF is nonnegative graph embedding (NGE), which encodes the statistical or geometric information of data in the process of matrix factorization. The NGE offers a general framework for unsupervised/supervised settings. However, NGE-like algorithms often suffer from noisy data, unreliable graphs, and noisy labels, which are commonly encountered in real-world applications. To address these issues, in this paper, we first propose a robust nonnegative graph embedding (RNGE) framework, where the joint sparsity in both graph embedding and data reconstruction endues robustness to undesirable noises. Next, we present a robust seminonnegative graph embedding (RsNGE) framework, which only constrains the coefficient matrix to be nonnegative while places no constraint on the base matrix. This extends the applicable range of RNGE to data which are not nonnegative and endows more discriminative power of the learnt base matrix. The RNGE/RsNGE provides a general formulation such that all the algorithms unified within the graph embedding framework can be easily extended to obtain their robust nonnegative/seminonnegative solutions. Further, we develop elegant multiplicative updating solutions that can solve RNGE/RsNGE efficiently and offer a rigorous convergence analysis. We conduct extensive experiments on four real-world data sets and compare the proposed RNGE/RsNGE to other representative NMF variants and data factorization methods. The experimental results demonstrate the robustness and effectiveness of the proposed approaches.

  11. 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.

  12. Graphing Predictions

    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…

  13. Graphing Predictions

    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…

  14. 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…

  15. 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…

  16. 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,…

  17. 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,…

  18. Spectral correlations of individual quantum graphs

    SciTech Connect

    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.

  19. Representational Issues in Systemic Functional Grammar and Systemic Grammar and Functional Unification Grammar. ISI Reprint Series.

    ERIC Educational Resources Information Center

    Matthiessen, Christian; Kasper, Robert

    Consisting of two separate papers, "Representational Issues in Systemic Functional Grammar," by Christian Matthiessen and "Systemic Grammar and Functional Unification Grammar," by Robert Kasper, this document deals with systemic aspects of natural language processing and linguistic theory and with computational applications of…

  20. 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…

  1. Scenario Graphs and Attack Graphs

    DTIC Science & Technology

    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

  2. Single-View 3D Scene Reconstruction and Parsing by Attribute Grammar.

    PubMed

    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.

  3. 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)

  4. 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)

  5. A Grammar of Kurtop

    ERIC Educational Resources Information Center

    Hyslop, Gwendolyn

    2011-01-01

    Kurtop is a Tibeto-Burman language spoken by approximately 15,000 people in Northeastern Bhutan. This dissertation is the first descriptive grammar of the language, based on extensive fieldwork and community-driven language documentation in Bhutan. When possible, analyses are presented in typological and historical/comparative perspectives and…

  6. Studies in Inuktitut Grammar

    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…

  7. A Grammar for Storytelling.

    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…

  8. Literature and Grammar.

    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.…

  9. Teaching Grammar in Context.

    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…

  10. English Transformational Grammar.

    ERIC Educational Resources Information Center

    Jacobs, Roderick A.; Rosenbaum, Peter S.

    The authors present for the undergraduate and graduate linguistics student a transformational approach to the study of English grammar. Their discussion begins with a description of the structure of sentences, outlined according to the transformational grammarian's framework of linguistic universals. This set of principles "makes possible the…

  11. An Amharic Reference Grammar.

    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…

  12. A GUJARATI REFERENCE GRAMMAR.

    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)…

  13. Teaching Grammar in Context.

    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…

  14. THAI, REFERENCE GRAMMAR.

    ERIC Educational Resources Information Center

    NOSS, RICHARD B.

    A REFERENCE GRAMMAR FOR THE THAI LANGUAGE IS PROVIDED. THE MAIN STRUCTURAL FEATURES OF STANDARD SPOKEN THAI ARE OUTLINED AND ELABORATED BY SUBCLASSIFICATION AND EXAMPLE. IN ADDITION, AN INDEX OF MINOR FORM-CLASS MEMBERS IS PROVIDED. THE APPROACH TO CLASSIFICATION OF GRAMMATICAL FEATURES FOLLOWS CURRENT TECHNIQUES OF AMERICAN DESCRIPTIVE…

  15. REEP Grammar Favorites.

    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)

  16. Multiple Grammars and MOGUL

    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…

  17. Studies in Inuktitut Grammar

    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…

  18. Why Not Pivot Grammar?

    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)

  19. A GUJARATI REFERENCE GRAMMAR.

    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)…

  20. A Grammar of Bih

    ERIC Educational Resources Information Center

    Nguyen, Tam Thi Minh

    2013-01-01

    Bih is a Chamic (Austronesian) language spoken by approximately 500 people in the Southern highlands of Vietnam. This dissertation is the first descriptive grammar of the language, based on extensive fieldwork and community-based language documentation in Vietnam and written from a functional/typological perspective. The analysis in this work is…

  1. Multibody graph transformations and analysis

    PubMed Central

    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

  2. Factorized Graph Matching.

    PubMed

    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.

  3. 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.

  4. Attribute And-Or Grammar for Joint Parsing of Human Pose, Parts and Attributes.

    PubMed

    Park, Seyoung; Nie, Xiaohan; Zhu, Song-Chun

    2017-07-25

    This paper presents an attribute and-or grammar (A-AOG) model for jointly inferring human body pose and human attributes in a parse graph with attributes augmented to nodes in the hierarchical representation. In contrast to other popular methods in the current literature that train separate classifiers for poses and individual attributes, our method explicitly represents the decomposition and articulation of body parts, and account for the correlations between poses and attributes. The A-AOG model is an amalgamation of three traditional grammar formulations: (i)Phrase structure grammar representing the hierarchical decomposition of the human body from whole to parts; (ii)Dependency grammar modeling the geometric articulation by a kinematic graph of the body pose; and (iii)Attribute grammar accounting for the compatibility relations between different parts in the hierarchy so that their appearances follow a consistent style. The parse graph outputs human detection, pose estimation, and attribute prediction simultaneously, which are intuitive and interpretable. We conduct experiments on two tasks on two datasets, and experimental results demonstrate the advantage of joint modeling in comparison with computing poses and attributes independently. Furthermore, our model obtains better performance over existing methods for both pose estimation and attribute prediction tasks.

  5. Adjusting protein graphs based on graph entropy.

    PubMed

    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.

  6. Continuous-time quantum walks on star graphs

    SciTech Connect

    Salimi, S.

    2009-06-15

    In this paper, we investigate continuous-time quantum walk on star graphs. It is shown that quantum central limit theorem for a continuous-time quantum walk on star graphs for N-fold star power graph, which are invariant under the quantum component of adjacency matrix, converges to continuous-time quantum walk on K{sub 2} graphs (complete graph with two vertices) and the probability of observing walk tends to the uniform distribution.

  7. 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…

  8. Network Analysis with Stochastic Grammars

    DTIC Science & Technology

    2015-09-17

    a variety of ways on a lower level. For a grammar , each phase is essentially a Task and a network attack is, at the highest level, a five Task...NETIVORK ANALYSIS \\\\’ITH STOCHASTIC GRAMMARS DISSERTATION Alan C. Lin, Maj , USAF AFIT-ENG-DS-15-S-014 DEPARTMENT OF THE AIR FORCE AIR...subject to copyright protection in the United States. AFIT-ENG-DS-15-S-014 NETWORK ANALYSIS WITH STOCHASTIC GRAMMARS DISSERTATION Presented

  9. War’s Second Grammar

    DTIC Science & Technology

    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

  10. Graphing Reality

    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.

  11. Representation Issues in Systemic Functional Grammar and Systemic Grammar and Functional Unification Grammar.

    DTIC Science & Technology

    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

  12. Threshold Graph Limits and Random Threshold Graphs

    PubMed Central

    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

  13. 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,…

  14. 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,…

  15. Graphing Reality

    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…

  16. Graphing Reality

    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…

  17. GraphBench

    SciTech Connect

    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.)

  18. Paperback Grammar for Handbook Haters.

    ERIC Educational Resources Information Center

    Lambert, Dorothy

    1967-01-01

    Students will respond better to grammar instruction if the traditional heavy handbooks are replaced with light-weight paperbacks, each full of practical suggestions and clear examples. Several inexpensive paperbacks are available for instruction in grammar and usage, spelling, vocabulary, reading comprehension, and writing. Unlike the conventional…

  19. What Is a Varieties Grammar?

    ERIC Educational Resources Information Center

    Durmuller, Urs

    A varieties grammar (VG) attempts to provide a unifying apparatus for various kinds of language varieties: diatopic, diastratic, and diatypic. The notion of "family grammar" appears to be especially useful in that process since it permits the postulation of a supergrammar for the whole family as well as that of subgrammars for the individual…

  20. Oral Grammar in the Classroom

    ERIC Educational Resources Information Center

    Taggart, Gilbert

    1975-01-01

    This article compares first and second language acquisition and applies conclusions pertaining to first language acquisition to second language learning, specifically that a command of grammar is essential and this grammar is independent of that associated with the written language. (CLK)

  1. Teachers' Perceptions about Grammar Teaching

    ERIC Educational Resources Information Center

    Thu, Tran Hoang

    2009-01-01

    This study investigates English as a second language (ESL) teachers' beliefs in grammar teaching. A 32-item questionnaire was administered to 11 ESL teachers in a language school in California. The results show that the participants generally believe that the formal study of grammar is essential to the eventual mastery of a foreign or second…

  2. 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…

  3. A Reference Grammar of Bena

    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…

  4. 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…

  5. 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,"…

  6. A Reference Grammar of Bena

    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…

  7. 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…

  8. 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…

  9. Line graphs for fractals

    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.

  10. 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.

  11. Universal spectral statistics in quantum graphs.

    PubMed

    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.

  12. CUDA Enabled Graph Subset Examiner

    SciTech Connect

    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.

  13. Generalized graph states based on Hadamard matrices

    SciTech Connect

    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.

  14. 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…

  15. 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…

  16. Deterministic dense coding and faithful teleportation with multipartite graph states

    SciTech Connect

    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.

  17. Pattern vectors from algebraic graph theory.

    PubMed

    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.

  18. 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)

  19. 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)

  20. 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.

  1. 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.

  2. Developmental Assessment of Spanish Grammar

    ERIC Educational Resources Information Center

    Toronto, Allen S.

    1976-01-01

    Described is the Developmental Assessment of Spanish Grammar, an analysis procedure designed to evaluate the language of American Spanish-speaking children with deficient grammatical skills and to serve as a model for structuring language remediation. (Author/SB)

  3. A SKETCH OF MALAGASY GRAMMAR.

    ERIC Educational Resources Information Center

    GARVEY, CATHERINE J.

    THE RESULTS OF A PROGRAM TO BUILD A MALAGASY GRAMMAR, BASED MAINLY ON THE MERINA DIALECT, ARE PRESENTED. INCLUDED ARE SECTIONS OF PHONOLOGY, MORPHOLOGY, AND SYNTAX. (AN ACCOMPANYING MALAGASY INTRODUCTORY COURSE IS ED 010 482.) (GD)

  4. Dynamic graph system for a semantic database

    DOEpatents

    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.

  5. Dynamic graph system for a semantic database

    DOEpatents

    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.

  6. Synchronizability of random rectangular graphs

    SciTech Connect

    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.

  7. Multi-Centrality Graph Spectral Decompositions and Their Application to Cyber Intrusion Detection

    SciTech Connect

    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.

  8. Universal chaotic scattering on quantum graphs.

    PubMed

    Pluhař, Z; Weidenmüller, H A

    2013-01-18

    We calculate the S-matrix correlation function for chaotic scattering on quantum graphs and show that it agrees with that of random-matrix theory. We also calculate all higher S-matrix correlation functions in the Ericson regime. These, too, agree with random-matrix theory results as far as the latter are known. We conjecture that our results give a universal description of chaotic scattering.

  9. Adjusting protein graphs based on graph entropy

    PubMed Central

    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. PMID:25474347

  10. Cayley Bipolar Fuzzy Graphs

    PubMed Central

    Alshehri, Noura O.

    2013-01-01

    We introduce the concept of Cayley bipolar fuzzy graphs and investigate some of their properties. We present some interesting properties of bipolar fuzzy graphs in terms of algebraic structures. We also discuss connectedness in Cayley bipolar fuzzy graphs. PMID:24453797

  11. An introduction to chordal graphs and clique trees

    SciTech Connect

    Blair, J.R.S. . Dept. of Computer Science); 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.

  12. An introduction to chordal graphs and clique trees

    SciTech Connect

    Blair, J.R.S. . Dept. of Computer Science); Peyton, B.W. )

    1991-01-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.

  13. An introduction to chordal graphs and clique trees

    SciTech Connect

    Blair, J.R.S.; Peyton, B.W.

    1991-12-31

    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.

  14. An introduction to chordal graphs and clique trees

    SciTech Connect

    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.

  15. Differentials on graph complexes II: hairy graphs

    NASA Astrophysics Data System (ADS)

    Khoroshkin, Anton; Willwacher, Thomas; Živković, Marko

    2017-10-01

    We study the cohomology of the hairy graph complexes which compute the rational homotopy of embedding spaces, generalizing the Vassiliev invariants of knot theory. We provide spectral sequences converging to zero whose first pages contain the hairy graph cohomology. Our results yield a way to construct many nonzero hairy graph cohomology classes out of (known) non-hairy classes by studying the cancellations in those sequences. This provide a first glimpse at the tentative global structure of the hairy graph cohomology.

  16. A Learning Algorithm for Multimodal Grammar Inference.

    PubMed

    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.

  17. 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)

  18. Case-Based Plan Recognition Using Action Sequence Graphs

    DTIC Science & Technology

    2014-10-01

    algorithm based on plan tree grammars. Artificial Intelligence, 173(11), 1101-1132. Ghallab,M., Nau, D., & Traverso, P. (2004). Automated planning : Theory ...Case-Based Plan Recognition Using Action Sequence Graphs Swaroop S. Vattam1, David W. Aha2 and Michael Floyd3 1NRC Postdoctoral Fellow; Naval...knexusresearch.com Abstract. We present SET-PR, a novel case-based plan recognition algorithm that is tolerant to missing and misclassified actions in its

  19. Graphing Polar Curves

    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…

  20. Transformational Grammar and the Teacher of English.

    ERIC Educational Resources Information Center

    Thomas, Owen

    This pedagogical approach to transformational grammar describes those aspects of the subject which have the greatest relevance for teachers of English. Following a definition of basic terms and a discussion of the nature and function of grammar, a description of basic English sentence patterns is used to present a model grammar based on the…

  1. 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…

  2. 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…

  3. 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…

  4. 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…

  5. 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…

  6. 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…

  7. Grammar for Teachers: Perspectives and Definitions.

    ERIC Educational Resources Information Center

    Weaver, Constance

    Intended for preservice and inservice teachers at all educational levels, but especially for those in English education classes, this book examines the foundations of grammar instruction and supplies some definitions and examples of grammar usage. Part one of the book explores relevant language research, reasons for teaching grammar, the…

  8. 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…

  9. 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…

  10. 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…

  11. 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…

  12. 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…

  13. 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…

  14. 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…

  15. Teaching Grammar as a Liberating Force

    ERIC Educational Resources Information Center

    Cullen, Richard

    2008-01-01

    The idea of grammar as a "liberating force" comes from a paper by Henry Widdowson (1990) in which grammar is depicted as a resource which liberates the language user from an over-dependency on lexis and context for the expression of meaning. In this paper, I consider the implications for second language teaching of the notion of grammar as a…

  16. 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…

  17. 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…

  18. Matrix trace operators: from spectral moments of molecular graphs and complex networks to perturbations in synthetic reactions, micelle nanoparticles, and drug ADME processes.

    PubMed

    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

  19. Spectral statistics of random geometric graphs

    NASA Astrophysics Data System (ADS)

    Dettmann, C. P.; Georgiou, O.; Knight, G.

    2017-04-01

    We use random matrix theory to study the spectrum of random geometric graphs, a fundamental model of spatial networks. Considering ensembles of random geometric graphs we look at short-range correlations in the level spacings of the spectrum via the nearest-neighbour and next-nearest-neighbour spacing distribution and long-range correlations via the spectral rigidity Δ3 statistic. These correlations in the level spacings give information about localisation of eigenvectors, level of community structure and the level of randomness within the networks. We find a parameter-dependent transition between Poisson and Gaussian orthogonal ensemble statistics. That is the spectral statistics of spatial random geometric graphs fits the universality of random matrix theory found in other models such as Erdős-Rényi, Barabási-Albert and Watts-Strogatz random graphs.

  20. Inverse scattering problem for quantum graph vertices

    SciTech Connect

    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.

  1. 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.

  2. Efficient dynamic graph construction for inductive semi-supervised learning.

    PubMed

    Dornaika, F; Dahbi, R; Bosaghzadeh, A; Ruichek, Y

    2017-10-01

    Most of graph construction techniques assume a transductive setting in which the whole data collection is available at construction time. Addressing graph construction for inductive setting, in which data are coming sequentially, has received much less attention. For inductive settings, constructing the graph from scratch can be very time consuming. This paper introduces a generic framework that is able to make any graph construction method incremental. This framework yields an efficient and dynamic graph construction method that adds new samples (labeled or unlabeled) to a previously constructed graph. As a case study, we use the recently proposed Two Phase Weighted Regularized Least Square (TPWRLS) graph construction method. The paper has two main contributions. First, we use the TPWRLS coding scheme to represent new sample(s) with respect to an existing database. The representative coefficients are then used to update the graph affinity matrix. The proposed method not only appends the new samples to the graph but also updates the whole graph structure by discovering which nodes are affected by the introduction of new samples and by updating their edge weights. The second contribution of the article is the application of the proposed framework to the problem of graph-based label propagation using multiple observations for vision-based recognition tasks. Experiments on several image databases show that, without any significant loss in the accuracy of the final classification, the proposed dynamic graph construction is more efficient than the batch graph construction. Copyright © 2017 Elsevier Ltd. All rights reserved.

  3. Evolutionary graph theory: breaking the symmetry between interaction and replacement

    PubMed Central

    Ohtsuki, Hisashi; Pacheco, Jorge M.; Nowak, Martin A.

    2008-01-01

    We study evolutionary dynamics in a population whose structure is given by two graphs: the interaction graph determines who plays with whom in an evolutionary game; the replacement graph specifies the geometry of evolutionary competition and updating. First, we calculate the fixation probabilities of frequency dependent selection between two strategies or phenotypes. We consider three different update mechanisms: birth-death, death-birth and imitation. Then, as a particular example, we explore the evolution of cooperation. Suppose the interaction graph is a regular graph of degree h, the replacement graph is a regular graph of degree g and the overlap between the two graphs is a regular graph of degree l. We show that cooperation is favored by natural selection if b/c > hg/l. Here, b and c denote the benefit and cost of the altruistic act. This result holds for death-birth updating, weak selection and large population size. Note that the optimum population structure for cooperators is given by maximum overlap between the interaction and the replacement graph (g = h = l), which means that the two graphs are identical. We also prove that a modified replicator equation can describe how the expected values of the frequencies of an arbitrary number of strategies change on replacement and interaction graphs: the two graphs induce a transformation of the payoff matrix. PMID:17350049

  4. The evolutionary dynamics of grammar acquisition.

    PubMed

    Komarova, N L; Niyogi, P; Nowak, M A

    2001-03-07

    Grammar is the computational system of language. It is a set of rules that specifies how to construct sentences out of words. Grammar is the basis of the unlimited expressibility of human language. Children acquire the grammar of their native language without formal education simply by hearing a number of sample sentences. Children could not solve this learning task if they did not have some pre-formed expectations. In other words, children have to evaluate the sample sentences and choose one grammar out of a limited set of candidate grammars. The restricted search space and the mechanism which allows to evaluate the sample sentences is called universal grammar. Universal grammar cannot be learned; it must be in place when the learning process starts. In this paper, we design a mathematical theory that places the problem of language acquisition into an evolutionary context. We formulate equations for the population dynamics of communication and grammar learning. We ask how accurate children have to learn the grammar of their parents' language for a population of individuals to evolve and maintain a coherent grammatical system. It turns out that there is a maximum error tolerance for which a predominant grammar is stable. We calculate the maximum size of the search space that is compatible with coherent communication in a population. Thus, we specify the conditions for the evolution of universal grammar. Copyright 2001 Academic Press.

  5. 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.

  6. Quantum discord of states arising from graphs

    NASA Astrophysics Data System (ADS)

    Dutta, Supriyo; Adhikari, Bibhas; Banerjee, Subhashish

    2017-08-01

    Quantum discord refers to an important aspect of quantum correlations for bipartite quantum systems. In our earlier works, we have shown that corresponding to every graph (combinatorial) there are quantum states whose properties are reflected in the structure of the corresponding graph. Here, we attempt to develop a graph theoretic study of quantum discord that corresponds to a necessary and sufficient condition of zero quantum discord states which says that the blocks of density matrix corresponding to a zero quantum discord state are normal and commute with each other. These blocks have a one-to-one correspondence with some specific subgraphs of the graph which represents the quantum state. We obtain a number of graph theoretic properties representing normality and commutativity of a set of matrices which are indeed arising from the given graph. Utilizing these properties, we define graph theoretic measures for normality and commutativity that results in a formulation of graph theoretic quantum discord. We identify classes of quantum states with zero discord using the developed formulation.

  7. 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…

  8. 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…

  9. 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…

  10. 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.…

  11. 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…

  12. 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…

  13. 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.…

  14. 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…

  15. 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…

  16. 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…

  17. 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…

  18. 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)

  19. 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…

  20. 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…

  1. 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…

  2. Complex Grammar in Williams Syndrome

    ERIC Educational Resources Information Center

    Perovic, Alexandra; Wexler, Ken

    2007-01-01

    This study investigated knowledge of binding and raising in two groups of children with Williams syndrome (WS), 6-12 and 12-16-years-old, compared to typically developing (TD) controls matched on non-verbal MA, verbal MA, and grammar. In typical development, difficulties interpreting pronouns, but not reflexives, persist until the age of around 6,…

  3. 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…

  4. 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…

  5. 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…

  6. Interval Graph Limits

    PubMed Central

    Diaconis, Persi; Holmes, Susan; Janson, Svante

    2015-01-01

    We work out a graph limit theory for dense interval graphs. The theory developed departs from the usual description of a graph limit as a symmetric function W (x, y) on the unit square, with x and y uniform on the interval (0, 1). Instead, we fix a W and change the underlying distribution of the coordinates x and y. We find choices such that our limits are continuous. Connections to random interval graphs are given, including some examples. We also show a continuity result for the chromatic number and clique number of interval graphs. Some results on uniqueness of the limit description are given for general graph limits. PMID:26405368

  7. 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…

  8. The Oriented Graph Complexes

    NASA Astrophysics Data System (ADS)

    Willwacher, Thomas

    2015-03-01

    The oriented graph complexes are complexes of directed graphs without directed cycles. They govern, for example, the quantization of Lie bialgebras and infinite dimensional deformation quantization. Similar to the ordinary graph complexes GC n introduced by Kontsevich they come in two essentially different versions, depending on the parity of n. It is shown that, surprisingly, the oriented graph complex is quasi-isomorphic to the ordinary commutative graph complex of opposite parity GC n-1, up to some known classes. This yields in particular a combinatorial description of the action of on Lie bialgebras, and shows that a cycle-free formality morphism in the sense of Shoikhet can be constructed rationally without reference to configuration space integrals. Curiously, the obstruction class in the oriented graph complex found by Shoikhet corresponds to the well known theta graph in the ordinary graph complex.

  9. Does complexity matter? Meta-analysis of learner performance in artificial grammar tasks.

    PubMed

    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.

  10. Does complexity matter? Meta-analysis of learner performance in artificial grammar tasks

    PubMed Central

    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. PMID:25309495

  11. On molecular graph comparison.

    PubMed

    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.

  12. Programme for drawing line graphs on IBM personal computers.

    PubMed

    Anandhkumar, N; Namasivayam, A

    1993-04-01

    A simple program for drawing line graphs on IBM Personal Computers is described here. This program is written in Basic language and is user friendly. This program allows the operator to plot the line graphs with standard error of each of the observations. After plotting suitable legend can also be added at appropriate places in the graph. In the graphic mode a hard copy can be obtained from a dot matrix printer using print screen command.

  13. Graph-Plotting Routine

    NASA Technical Reports Server (NTRS)

    Kantak, Anil V.

    1987-01-01

    Plotter routine for IBM PC (AKPLOT) designed for engineers and scientists who use graphs as integral parts of their documentation. Allows user to generate graph and edit its appearance on cathode-ray tube. Graph may undergo many interactive alterations before finally dumped from screen to be plotted by printer. Written in BASIC.

  14. Graphs in Scientific Publications.

    ERIC Educational Resources Information Center

    Cleveland, William S.

    Two surveys were carried out to help increase knowledge of current graph usage in science. A detailed analysis of all graphs in one volume of the journal "Science" revealed that 30 percent had errors. Graphs are used more in some disciplines than in others; a survey of 57 journals revealed natural science journals use far more graphs…

  15. 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…

  16. Are Graphs Finally Surfacing?

    ERIC Educational Resources Information Center

    Beineke, Lowell W.

    1989-01-01

    Explored are various aspects of drawing graphs on surfaces. The Euler's formula, Kuratowski's theorem and the drawing of graphs in the plane with as few crossings as possible are discussed. Some applications including embedding of graphs and coloring of maps are included. (YP)

  17. 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…

  18. Graphing Important People

    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…

  19. Graphing Important People

    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…

  20. Defense et illustration de la grammaire philologique (An Example and a Defense of Philological Grammar)

    ERIC Educational Resources Information Center

    Dupont, Louis

    1972-01-01

    Author cites philological grammar" as one of three ways of treating language. The other two approaches to language are traditional grammar and linguistic grammar or transformational generative grammar. Philological grammar stresses the art of reading. (DS)

  1. 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.

  2. Graph distance for complex networks

    PubMed Central

    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

  3. Bipartite graph partitioning and data clustering

    SciTech Connect

    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.

  4. 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…

  5. 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…

  6. Multiword Constructions in the Grammar.

    PubMed

    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.

  7. Methods of visualizing graphs

    DOEpatents

    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.

  8. Flexible processing and the design of grammar.

    PubMed

    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.

  9. Product Grammars for Alignment and Folding.

    PubMed

    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/.

  10. Hyperbolic graph generator

    NASA Astrophysics Data System (ADS)

    Aldecoa, Rodrigo; Orsini, Chiara; Krioukov, Dmitri

    2015-11-01

    Networks representing many complex systems in nature and society share some common structural properties like heterogeneous degree distributions and strong clustering. Recent research on network geometry has shown that those real networks can be adequately modeled as random geometric graphs in hyperbolic spaces. In this paper, we present a computer program to generate such graphs. Besides real-world-like networks, the program can generate random graphs from other well-known graph ensembles, such as the soft configuration model, random geometric graphs on a circle, or Erdős-Rényi random graphs. The simulations show a good match between the expected values of different network structural properties and the corresponding empirical values measured in generated graphs, confirming the accurate behavior of the program.

  11. The minimalist grammar of action

    PubMed Central

    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

  12. Graphing trillions of triangles

    PubMed Central

    Burkhardt, Paul

    2016-01-01

    The increasing size of Big Data is often heralded but how data are transformed and represented is also profoundly important to knowledge discovery, and this is exemplified in Big Graph analytics. Much attention has been placed on the scale of the input graph but the product of a graph algorithm can be many times larger than the input. This is true for many graph problems, such as listing all triangles in a graph. Enabling scalable graph exploration for Big Graphs requires new approaches to algorithms, architectures, and visual analytics. A brief tutorial is given to aid the argument for thoughtful representation of data in the context of graph analysis. Then a new algebraic method to reduce the arithmetic operations in counting and listing triangles in graphs is introduced. Additionally, a scalable triangle listing algorithm in the MapReduce model will be presented followed by a description of the experiments with that algorithm that led to the current largest and fastest triangle listing benchmarks to date. Finally, a method for identifying triangles in new visual graph exploration technologies is proposed. PMID:28690426

  13. Learning a generative probabilistic grammar of experience: a process-level model of language acquisition.

    PubMed

    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. Copyright © 2014 Cognitive Science Society, Inc.

  14. 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…

  15. 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…

  16. 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…

  17. 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…

  18. 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…

  19. 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…

  20. Pratiquer une grammaire textuelle (Practicing Textual Grammar).

    ERIC Educational Resources Information Center

    Bourdet, Jean-Francois

    1992-01-01

    A discussion of textual, as contrasted with traditional, grammar for French second-language instruction argues that textual grammar is essential for acquisition of communicative competence because it identifies grammatical facts relevant to everyday communication and allows the student to experience the construction of meaning through them. (MSE)

  1. What Is Grammar, Who Is She?

    ERIC Educational Resources Information Center

    Heafford, Michael

    1993-01-01

    Attempts to clarify the role of grammar in second-language instruction. It is suggested that changes in language teaching have encouraged the view that grammar is one of several dimensions along which learners need to progress to achieve greater proficiency but that it should not be dominant. (22 references) (CK)

  2. 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).…

  3. A Grammar for Undergraduate Old French.

    ERIC Educational Resources Information Center

    Kelly, Douglas

    Seeking to determine the necessary elements of a grammar for undergraduate students with a strong interest in Old French, the author discusses: (1) sounds, (2) forms, (3) syntax, and (4) poetics. It is felt that the treatment accorded phonology should be different from the traditional approach used in graduate level grammars, since the course is…

  4. Grammar and Usage: History and Myth

    ERIC Educational Resources Information Center

    Watson, Ken

    2010-01-01

    The paper first traces the history of thinking about language from the Greek writers of the fifth century BC to the development of the first Greek grammar in about 100 BC. Since the glories of Ancient Greek literature predate the development of grammar, there is every reason to doubt the received wisdom that one must have an explicit knowledge of…

  5. 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…

  6. 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).…

  7. 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…

  8. 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…

  9. 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,…

  10. 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…

  11. 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…

  12. 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…

  13. 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,…

  14. 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.…

  15. 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…

  16. 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)

  17. 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,…

  18. 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…

  19. 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…

  20. 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…

  1. 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…

  2. 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…

  3. 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…

  4. 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…

  5. Nested Tracking Graphs

    DOE PAGES

    Lukasczyk, Jonas; Weber, Gunther; Maciejewski, Ross; ...

    2017-06-01

    Tracking graphs are a well established tool in topological analysis to visualize the evolution of components and their properties over time, i.e., when components appear, disappear, merge, and split. However, tracking graphs are limited to a single level threshold and the graphs may vary substantially even under small changes to the threshold. To examine the evolution of features for varying levels, users have to compare multiple tracking graphs without a direct visual link between them. We propose a novel, interactive, nested graph visualization based on the fact that the tracked superlevel set components for different levels are related to eachmore » other through their nesting hierarchy. This approach allows us to set multiple tracking graphs in context to each other and enables users to effectively follow the evolution of components for different levels simultaneously. We show the effectiveness of our approach on datasets from finite pointset methods, computational fluid dynamics, and cosmology simulations.« less

  6. Topologies on directed graphs

    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.

  7. Metamodel-Driven Evolution with Grammar Inference

    NASA Astrophysics Data System (ADS)

    Bryant, Barrett R.; Liu, Qichao; Mernik, Marjan

    2010-10-01

    Domain-specific modeling (DSM) has become one of the most popular techniques for incorporating model-driven engineering (MDE) into software engineering. In DSM, domain experts define metamodels to describe the essential problems in a domain. A model conforms to a schema definition represented by a metamodel in a similar manner to a programming language conforms to a grammar. Metamodel-driven evolution is when a metamodel undergoes evolutions to incorporate new concerns in the domain. However, this results in losing the ability to use existing model instances. Grammar inference is the problem of inferring a grammar from sample strings which the grammar should generate. This paper describes our work in solving the problem of metamodel-driven evolution with grammar inference, by inferring the metamodel from model instances.

  8. Online dynamic graph drawing.

    PubMed

    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.

  9. Graph Generator Survey

    SciTech Connect

    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.

  10. 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.

  11. 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.

  12. Robust Spectral Clustering Using Statistical Sub-Graph Affinity Model

    PubMed Central

    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

  13. Very Large Graphs for Information Extraction (VLG). Summary of First-Year Proof-of-Concept Study

    DTIC Science & Technology

    2013-08-20

    vertex . This technique fuses multiple random graph models and provides a exible approach to model graphs of various types with additional side information...strong as a star graph ( vertex with extremely high degree ) with twice as many vertices. The coauthor graph , on the bottom in the gure, contains two...smallest gap between consecutive eigenvalues . For most random graph models, however, the residuals matrix is dense. Thus, for computational tractability, it

  14. 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)

  15. Grammatical Relations in Universal Grammar. Work Papers Volume 23.

    ERIC Educational Resources Information Center

    Frantz, Donald G.

    Relational Grammar, which has evolved from transformational grammar, relies on a "universal grammar" approach. By closely studying this approach, linguists will be able to understand Relational Grammar (RG) well enough to be able to participate in its further development. The basic assumptions of RG are that…

  16. 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)

  17. 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…

  18. 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…

  19. Pourquoi les exercices de grammaire? (Why Grammar Exercises?)

    ERIC Educational Resources Information Center

    Bastuji, Jacqueline

    1977-01-01

    Recent theories and experiementation running the gamut from the absolute necessity of grammar to its uselessness in teaching a language form the basis of this article. Topics covered are: a typology of the grammar exercise; explicit grammar and linguistic competence; grammar exercises responding to real needs. (Text is in French.) (AMH)

  20. A Survey of Grammar Instruction from Scholastic Perspective

    ERIC Educational Resources Information Center

    Peng, Yanghua

    2017-01-01

    The study of grammar has been paid much attention and the grammar instruction becomes an emphasis and key problem in English language teaching and learning. How to instruct students grammar appropriately becomes controversial for some English teachers increasingly. Some linguistics, theorists and teachers hold that the grammar instruction should…

  1. RNA graph partitioning for the discovery of RNA modularity: a novel application of graph partition algorithm to biology.

    PubMed

    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

  2. RNA Graph Partitioning for the Discovery of RNA Modularity: A Novel Application of Graph Partition Algorithm to Biology

    PubMed Central

    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

  3. Description of the human hand grasp using graph theory.

    PubMed

    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.

  4. Eigenvalues of the Laplacian of a graph

    NASA Technical Reports Server (NTRS)

    Anderson, W. N., Jr.; Morley, T. D.

    1971-01-01

    Let G be a finite undirected graph with no loops or multiple edges. The Laplacian matrix of G, Delta(G), is defined by Delta sub ii = degree of vertex i and Delta sub ij = -1 if there is an edge between vertex i and vertex j. The structure of the graph G is related to the eigenvalues of Delta(G); in particular, it is proved that all the eigenvalues of Delta(G) are nonnegative, less than or equal to the number of vertices, and less than or equal to twice the maximum vertex degree. Precise conditions for equality are given.

  5. Algorithms for Regular Tree Grammar Network Search and Their Application to Mining Human-viral Infection Patterns.

    PubMed

    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.

  6. Real World Graph Connectivity

    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…

  7. 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)

  8. Making "Photo" Graphs

    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…

  9. Learning graph matching.

    PubMed

    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.

  10. Walking Out Graphs

    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…

  11. Using Specialized Graph Paper.

    ERIC Educational Resources Information Center

    James, C.

    1988-01-01

    Discusses the use of logarithm and reciprocal graphs in the college physics classroom. Provides examples, such as electrical conductivity, reliability function in the Weibull model, and the Clausius-Clapeyron equation for latent heat of vaporation. Shows graphs with weighting of points. (YP)

  12. ACTIVITIES: Graphs and Games

    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)

  13. Reflections on "The Graph"

    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…

  14. Real World Graph Connectivity

    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…

  15. Exploring Graphs: WYSIWYG.

    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…

  16. ACTIVITIES: Graphs and Games

    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)

  17. Exploring Graphs: WYSIWYG.

    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…

  18. Making "Photo" Graphs

    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…

  19. Three-dimensional object representation by array grammars

    NASA Astrophysics Data System (ADS)

    Wang, Patrick S. P.

    1991-02-01

    A new approach for representing 3-d objects by 3-d array grammar is introduced. The concept of universal array grammar is proposed for 3-d object representation. it uses parallelism for pattern generation. Many interesting 3-d objecis can indeed he represented by this universal 3-d array grammar which paves a ground for 3-d object recognition. description and understanding. Keywords: 3-d array grammars. universal array grammars pattern generation. object representation parallel generation I.

  20. 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.

  1. Modelling dynamics with context-free grammars

    NASA Astrophysics Data System (ADS)

    García-Huerta, Juan-M.; Jiménez-Hernández, Hugo; Herrera-Navarro, Ana-M.; Hernández-Díaz, Teresa; Terol-Villalobos, Ivan

    2014-03-01

    This article presents a strategy to model the dynamics performed by vehicles in a freeway. The proposal consists on encode the movement as a set of finite states. A watershed-based segmentation is used to localize regions with high-probability of motion. Each state represents a proportion of a camera projection in a two-dimensional space, where each state is associated to a symbol, such that any combination of symbols is expressed as a language. Starting from a sequence of symbols through a linear algorithm a free-context grammar is inferred. This grammar represents a hierarchical view of common sequences observed into the scene. Most probable grammar rules express common rules associated to normal movement behavior. Less probable rules express themselves a way to quantify non-common behaviors and they might need more attention. Finally, all sequences of symbols that does not match with the grammar rules, may express itself uncommon behaviors (abnormal). The grammar inference is built with several sequences of images taken from a freeway. Testing process uses the sequence of symbols emitted by the scenario, matching the grammar rules with common freeway behaviors. The process of detect abnormal/normal behaviors is managed as the task of verify if any word generated by the scenario is recognized by the grammar.

  2. Unsupervised grammar induction of clinical report sublanguage.

    PubMed

    Kate, Rohit J

    2012-10-05

    Clinical reports are written using a subset of natural language while employing many domain-specific terms; such a language is also known as a sublanguage for a scientific or a technical domain. Different genres of clinical reports use different sublaguages, and in addition, different medical facilities use different medical language conventions. This makes supervised training of a parser for clinical sentences very difficult as it would require expensive annotation effort to adapt to every type of clinical text. In this paper, we present an unsupervised method which automatically induces a grammar and a parser for the sublanguage of a given genre of clinical reports from a corpus with no annotations. In order to capture sentence structures specific to clinical domains, the grammar is induced in terms of semantic classes of clinical terms in addition to part-of-speech tags. Our method induces grammar by minimizing the combined encoding cost of the grammar and the corresponding sentence derivations. The probabilities for the productions of the induced grammar are then learned from the unannotated corpus using an instance of the expectation-maximization algorithm. Our experiments show that the induced grammar is able to parse novel sentences. Using a dataset of discharge summary sentences with no annotations, our method obtains 60.5% F-measure for parse-bracketing on sentences of maximum length 10. By varying a parameter, the method can induce a range of grammars, from very specific to very general, and obtains the best performance in between the two extremes.

  3. Evolutionary stability on graphs.

    PubMed

    Ohtsuki, Hisashi; Nowak, Martin A

    2008-04-21

    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.

  4. Quantum causal graph dynamics

    NASA Astrophysics Data System (ADS)

    Arrighi, Pablo; Martiel, Simon

    2017-07-01

    Consider a graph having quantum systems lying at each node. Suppose that the whole thing evolves in discrete time steps, according to a global, unitary causal operator. By causal we mean that information can only propagate at a bounded speed, with respect to the distance given by the graph. Suppose, moreover, that the graph itself is subject to the evolution, and may be driven to be in a quantum superposition of graphs—in accordance to the superposition principle. We show that these unitary causal operators must decompose as a finite-depth circuit of local unitary gates. This unifies a result on quantum cellular automata with another on reversible causal graph dynamics. Along the way we formalize a notion of causality which is valid in the context of quantum superpositions of time-varying graphs, and has a number of good properties. We discuss some of the implications for quantum gravity.

  5. Evolutionary stability on graphs

    PubMed Central

    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

  6. Discrimination Power of Polynomial-Based Descriptors for Graphs by Using Functional Matrices.

    PubMed

    Dehmer, Matthias; Emmert-Streib, Frank; Shi, Yongtang; Stefu, Monica; Tripathi, Shailesh

    2015-01-01

    In this paper, we study the discrimination power of graph measures that are based on graph-theoretical matrices. The paper generalizes the work of [M. Dehmer, M. Moosbrugger. Y. Shi, Encoding structural information uniquely with polynomial-based descriptors by employing the Randić matrix, Applied Mathematics and Computation, 268(2015), 164-168]. We demonstrate that by using the new functional matrix approach, exhaustively generated graphs can be discriminated more uniquely than shown in the mentioned previous work.

  7. 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.

  8. Abstract Expression Grammar Symbolic Regression

    NASA Astrophysics Data System (ADS)

    Korns, Michael F.

    This chapter examines the use of Abstract Expression Grammars to perform the entire Symbolic Regression process without the use of Genetic Programming per se. The techniques explored produce a symbolic regression engine which has absolutely no bloat, which allows total user control of the search space and output formulas, which is faster, and more accurate than the engines produced in our previous papers using Genetic Programming. The genome is an all vector structure with four chromosomes plus additional epigenetic and constraint vectors, allowing total user control of the search space and the final output formulas. A combination of specialized compiler techniques, genetic algorithms, particle swarm, aged layered populations, plus discrete and continuous differential evolution are used to produce an improved symbolic regression sytem. Nine base test cases, from the literature, are used to test the improvement in speed and accuracy. The improved results indicate that these techniques move us a big step closer toward future industrial strength symbolic regression systems.

  9. Cognitive grammar and aphasic discourse.

    PubMed

    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.

  10. The grammar of transcriptional regulation

    PubMed Central

    Weingarten-Gabbay, Shira; Segal, Eran

    2014-01-01

    Eukaryotes employ combinatorial strategies to generate a variety of expression patterns from a relatively small set of regulatory DNA elements. As in any other language, deciphering the mapping between DNA and expression requires an understanding of the set of rules that govern basic principles in transcriptional regulation, the functional elements involved, and the ways in which they combine to orchestrate a transcriptional output. Here, we review current understanding of various grammatical rules, including the effect on expression of the number of transcription factor binding-sites, their location, orientation, affinity and activity; co-association with different factors; and intrinsic nucleosome organization. We review different methods that are used to study the grammar of transcription regulation, highlight gaps in current understanding, and discuss how recent technological advances may be utilized to bridge them. PMID:24390306

  11. Developmental assessment of Spanish grammar.

    PubMed

    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.

  12. Asymptotic inequalities on the parameters of a strongly regular graph

    NASA Astrophysics Data System (ADS)

    Vieira, Luís António de Almeida

    2017-07-01

    We first consider a strongly regular G whose adjacency matrix is A, next we associate a real three dimensional Euclidean Jordan algebra 𝒜 with rank three to the matrix A. Finally, from the analyze of the spectra of a binomial Hadamard Series of an element of 𝒜 we establish asymptotical inequalities on the parameters of a strongly regular graph.

  13. 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…

  14. 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…

  15. Estimating Grammar Parameters using Bounded Memory

    DTIC Science & Technology

    2002-01-01

    algorithm, called HOLA , for estimating the parameters of SCFGs that computes summary statis- tics for each string as it is observed and then discards...the string. The memory used by HOLA is bounded by the size of the grammar, not by the amount of training data. Empirical results show that HOLA ...of the grammar improves monotonically as more computation is allocated to learning. This paper introduces an algorithm called HOLA that satisfies

  16. Grammar Alive! A Guide for Teachers.

    ERIC Educational Resources Information Center

    Haussamen, Brock

    Designed to be a resource for the myriad K-12 teachers who wonder what to do about grammar--how to teach it, how to apply it, how to learn what they themselves were never taught---this book offers an informal, hands-on approach to grammar in the classroom. The book presents teachers with ways to negotiate the often conflicting goals of testing,…

  17. Tailored Random Graph Ensembles

    NASA Astrophysics Data System (ADS)

    Roberts, E. S.; Annibale, A.; Coolen, A. C. C.

    2013-02-01

    Tailored graph ensembles are a developing bridge between biological networks and statistical mechanics. The aim is to use this concept to generate a suite of rigorous tools that can be used to quantify and compare the topology of cellular signalling networks, such as protein-protein interaction networks and gene regulation networks. We calculate exact and explicit formulae for the leading orders in the system size of the Shannon entropies of random graph ensembles constrained with degree distribution and degree-degree correlation. We also construct an ergodic detailed balance Markov chain with non-trivial acceptance probabilities which converges to a strictly uniform measure and is based on edge swaps that conserve all degrees. The acceptance probabilities can be generalized to define Markov chains that target any alternative desired measure on the space of directed or undirected graphs, in order to generate graphs with more sophisticated topological features.

  18. Reaction spreading on graphs.

    PubMed

    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.

  19. A Semantic Graph Query Language

    SciTech Connect

    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.

  20. Speed of evolution on graphs.

    PubMed

    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.

  1. Speed of evolution on 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.

  2. 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.

  3. Commuting projections on graphs

    SciTech Connect

    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 QH 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 QH commute with the discrete divergence operator, i.e., we have div π H = QH 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.

  4. Comparing dynamical systems by a graph matching method

    NASA Astrophysics Data System (ADS)

    Zheng, Jiongxuan; Skufca, Joseph D.; Bollt, Erik M.

    2013-07-01

    In this paper, we consider comparing dynamical systems by using a method of graph matching, either between the graphs representing the underlying symbolic dynamics, or between the graphs approximating the action of the systems on a fine but otherwise non-generating partition. For conjugate systems, the graphs are isomorphic and we show that the permutation matrices that relate the adjacency matrices coincide with the solution of Monge’s mass transport problem. We use the underlying earth mover’s distance (EMD) to generate the “approximate” matching matrix to illustrate the association of graphs which are derived from equal-distance partitioning of the phase spaces of systems. In addition, for one system which embeds into the other, we show that the comparison of these two systems by our method is an issue of subgraph matching.

  5. 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.

  6. Conceptualisations of "Grammar Teaching": L1 English Teachers' Beliefs about Teaching Grammar for Writing

    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…

  7. Learning English Grammar with a Corpus: Experimenting with Concordancing in a University Grammar Course

    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…

  8. Conceptualisations of "Grammar Teaching": L1 English Teachers' Beliefs about Teaching Grammar for Writing

    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…

  9. Learning English Grammar with a Corpus: Experimenting with Concordancing in a University Grammar Course

    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…

  10. 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.…

  11. 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.

  12. 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.

  13. Universality in spectral statistics of open quantum graphs.

    PubMed

    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.

  14. Program for drawing bar graphs on IBM Personal computers.

    PubMed

    Anandhkumar, N; Namasivayam, A

    1990-04-01

    A simple program for drawing Bar graphs on IBM Personal computers is described here. This program is written in BASIC language and is user friendly. The program allows the operator to plot the bars with standard error, adjust the spacing between the bars and save the 'bar in a floppy disk. Legend can also be added at appropriate places in the graph. In the graphic mode, a hard copy can be obtained from a dot matrix printer using print screen command.

  15. 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.

  16. Proxy Graph: Visual Quality Metrics of Big Graph Sampling.

    PubMed

    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.

  17. 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.

  18. 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.

  19. Spectral properties of the hierarchical product of graphs.

    PubMed

    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.

  20. The Graph Laplacian and the Dynamics of Complex Networks

    SciTech Connect

    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.

  1. 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.

  2. Unsupervised grammar induction of clinical report sublanguage

    PubMed Central

    2012-01-01

    Background Clinical reports are written using a subset of natural language while employing many domain-specific terms; such a language is also known as a sublanguage for a scientific or a technical domain. Different genres of clinical reports use different sublaguages, and in addition, different medical facilities use different medical language conventions. This makes supervised training of a parser for clinical sentences very difficult as it would require expensive annotation effort to adapt to every type of clinical text. Methods In this paper, we present an unsupervised method which automatically induces a grammar and a parser for the sublanguage of a given genre of clinical reports from a corpus with no annotations. In order to capture sentence structures specific to clinical domains, the grammar is induced in terms of semantic classes of clinical terms in addition to part-of-speech tags. Our method induces grammar by minimizing the combined encoding cost of the grammar and the corresponding sentence derivations. The probabilities for the productions of the induced grammar are then learned from the unannotated corpus using an instance of the expectation-maximization algorithm. Results Our experiments show that the induced grammar is able to parse novel sentences. Using a dataset of discharge summary sentences with no annotations, our method obtains 60.5% F-measure for parse-bracketing on sentences of maximum length 10. By varying a parameter, the method can induce a range of grammars, from very specific to very general, and obtains the best performance in between the two extremes. PMID:23046834

  3. 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.

  4. Quel Eclectisme en grammaire? (What Eclecticism in Grammar?)

    ERIC Educational Resources Information Center

    Beacco, Jean-Claude

    1987-01-01

    The teaching of grammar provides more options for teacher strategies than almost any other area of language teaching, but because of the nature of grammar and classroom language instruction, using a variety of approaches is a more appropriate strategy. (MSE)

  5. 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.

  6. Filtering Random Graph Processes Over Random Time-Varying Graphs

    NASA Astrophysics Data System (ADS)

    Isufi, Elvin; Loukas, Andreas; Simonetto, Andrea; Leus, Geert

    2017-08-01

    Graph filters play a key role in processing the graph spectra of signals supported on the vertices of a graph. However, despite their widespread use, graph filters have been analyzed only in the deterministic setting, ignoring the impact of stochastic- ity in both the graph topology as well as the signal itself. To bridge this gap, we examine the statistical behavior of the two key filter types, finite impulse response (FIR) and autoregressive moving average (ARMA) graph filters, when operating on random time- varying graph signals (or random graph processes) over random time-varying graphs. Our analysis shows that (i) in expectation, the filters behave as the same deterministic filters operating on a deterministic graph, being the expected graph, having as input signal a deterministic signal, being the expected signal, and (ii) there are meaningful upper bounds for the variance of the filter output. We conclude the paper by proposing two novel ways of exploiting randomness to improve (joint graph-time) noise cancellation, as well as to reduce the computational complexity of graph filtering. As demonstrated by numerical results, these methods outperform the disjoint average and denoise algorithm, and yield a (up to) four times complexity redution, with very little difference from the optimal solution.

  7. 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.

  8. Associating semantic grammars with the SNOMED: processing medical language and representing clinical facts into a language-independent frame.

    PubMed

    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.

  9. Algebraic distance on graphs.

    SciTech Connect

    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.

  10. Subdominant pseudoultrametric on graphs

    SciTech Connect

    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.

  11. Quantum ergodicity on graphs.

    PubMed

    Gnutzmann, S; Keating, J P; Piotet, F

    2008-12-31

    We investigate the equidistribution of the eigenfunctions on quantum graphs in the high-energy limit. Our main result is an estimate of the deviations from equidistribution for large well-connected graphs. We use an exact field-theoretic expression in terms of a variant of the supersymmetric nonlinear sigma model. Our estimate is based on a saddle-point analysis of this expression and leads to a criterion for when equidistribution emerges asymptotically in the limit of large graphs. Our theory predicts a rate of convergence that is a significant refinement of previous estimates, long assumed to be valid for quantum chaotic systems, agreeing with them in some situations but not all. We discuss specific examples for which the theory is tested numerically.

  12. Quantum Ergodicity on Graphs

    SciTech Connect

    Gnutzmann, S.; Keating, J. P.; Piotet, F.

    2008-12-31

    We investigate the equidistribution of the eigenfunctions on quantum graphs in the high-energy limit. Our main result is an estimate of the deviations from equidistribution for large well-connected graphs. We use an exact field-theoretic expression in terms of a variant of the supersymmetric nonlinear {sigma} model. Our estimate is based on a saddle-point analysis of this expression and leads to a criterion for when equidistribution emerges asymptotically in the limit of large graphs. Our theory predicts a rate of convergence that is a significant refinement of previous estimates, long assumed to be valid for quantum chaotic systems, agreeing with them in some situations but not all. We discuss specific examples for which the theory is tested numerically.

  13. 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…

  14. 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…

  15. Pupils' Word Choices and the Teaching of Grammar

    ERIC Educational Resources Information Center

    Wyse, Dominic

    2006-01-01

    The idea that formal grammar teaching leads to improvements in school pupils' writing has been a popular one. However, the robust and extensive evidence base shows that this is not the case. Despite this, policy initiatives have continued to suggest that grammar teaching does improve pupils' writing: the "Grammar for Writing" resource is…

  16. 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…

  17. 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…

  18. Grammar Handbook for Home and School. Using Your Language Series.

    ERIC Educational Resources Information Center

    Smith, Carl B.

    Intended as a home resource book for children, this grammar handbook is a quick reference source for questions on grammar and punctuation. The book provides information, as well as sentences to illustrate each definition and guideline, about the most frequently used terms in grammar and punctuation. The book's information is organized…

  19. 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…

  20. Playful Explicitness with Grammar: A Pedagogy for Writing

    ERIC Educational Resources Information Center

    Myhill, Debra; Jones, Susan; Watson, Annabel; Lines, Helen

    2013-01-01

    The place of grammar within the teaching of writing has long been contested and successive research studies have indicated no correlation between grammar teaching and writing attainment. However, a recent study has shown a significant positive impact on writing outcomes when the grammar input is intrinsically linked to the demands of the writing…

  1. Teaching Grammar and Testing Grammar in the English Primary School: The Impact on Teachers and Their Teaching of the Grammar Element of the Statutory Test in Spelling, Punctuation and Grammar (SPaG)

    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…

  2. 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…

  3. 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…

  4. Indirect Positive Evidence in the Acquisition of a Subset Grammar

    ERIC Educational Resources Information Center

    Schwartz, Misha; Goad, Heather

    2017-01-01

    This article proposes that second language learners can use indirect positive evidence (IPE) to acquire a phonological grammar that is a subset of their L1 grammar. IPE is evidence from errors in the learner's L1 made by native speakers of the learner's L2. It has been assumed that subset grammars may be acquired using direct or indirect negative…

  5. 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…

  6. 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…

  7. 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…

  8. 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…

  9. Teaching Grammar and Testing Grammar in the English Primary School: The Impact on Teachers and Their Teaching of the Grammar Element of the Statutory Test in Spelling, Punctuation and Grammar (SPaG)

    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…

  10. 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.

  11. Graph ensemble boosting for imbalanced noisy graph stream classification.

    PubMed

    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.

  12. Understanding Grammars through Diachronic Change

    PubMed Central

    Madariaga, Nerea

    2017-01-01

    In this paper, I will vindicate the importance of syntactic change for the study of synchronic stages of natural languages, according to the following outline. First, I will analyze the relationship between the diachrony and synchrony of grammars, introducing some basic concepts: the notions of I-language/E-language, the role of Chomsky's (2005) three factors in language change, and some assumptions about language acquisition. I will briefly describe the different approaches to syntactic change adopted in generative accounts, as well as their assumptions and implications (Lightfoot, 1999, 2006; van Gelderen, 2004; Biberauer et al., 2010; Roberts, 2012). Finally, I will illustrate the convenience of introducing the diachronic dimension into the study of at least certain synchronic phenomena with the help of a practical example: variation in object case marking of several verbs in Modern Russian, namely, the verbs denoting avoidance and the verbs slušat'sja “obey” and dožidat'sja “expect,” which show two object case-marking patterns, genitive case in standard varieties and accusative case in colloquial varieties. To do so, I will review previous descriptive and/or functionalist accounts on this or equivalent phenomena (Jakobson, 1984 [1936]; Clancy, 2006; Nesset and Kuznetsova, 2015a,b). Then, I will present a formal—but just synchronic—account, applying Sigurðsson (2011) hypothesis on the expression of morphological case to this phenomenon. Finally, I will show that a formal account including the diachronic dimension is superior (i.e., more explanative) than purely synchronic accounts. PMID:28824474

  13. Line Graph Learning

    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…

  14. Cookies and Graphs

    ERIC Educational Resources Information Center

    Cooper, Carol

    1975-01-01

    Teachers of an integrated elementary classroom used cookie-sharing time as a learning experience for students. Responsible for dividing varying amounts of cookies daily, the students learned to translate their experiences to graphs of differing sophistication and analyses. Further interpretation and application were done by individual students…

  15. Body Motion and Graphing.

    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…

  16. Straight Line Graphs

    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…

  17. Hidden Behavior in Graphs.

    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)

  18. Line Graph Learning

    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…

  19. GraphLib

    SciTech Connect

    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

  20. Graph-theoretical exorcism

    SciTech Connect

    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.

  1. Coloring geographical threshold graphs

    SciTech Connect

    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.

  2. Introduction to Graphing.

    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…

  3. Straight Line Graphs

    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…

  4. Quantum walks on quotient graphs

    SciTech Connect

    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.

  5. Temporal Representation in Semantic Graphs

    SciTech Connect

    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.

  6. Reproducibility of graph metrics of human brain structural networks.

    PubMed

    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.

  7. Dynamic graph of an oxy-fuel combustion system using autocatalytic set model

    NASA Astrophysics Data System (ADS)

    Harish, Noor Ainy; Bakar, Sumarni Abu

    2017-08-01

    Evaporation process is one of the main processes besides combustion process in an oxy-combustion boiler system. An Autocatalytic Set (ASC) Model has successfully applied in developing graphical representation of the chemical reactions that occurs in the evaporation process in the system. Seventeen variables identified in the process are represented as nodes and the catalytic relationships are represented as edges in the graph. In addition, in this paper graph dynamics of ACS is further investigated. By using Dynamic Autocatalytic Set Graph Algorithm (DAGA), the adjacency matrix for each of the graphs and its relations to Perron-Frobenius Theorem is investigated. The dynamic graph obtained is further investigated where the connection of the graph to fuzzy graph Type 1 is established.

  8. A Clustering Graph Generator

    SciTech Connect

    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.

  9. 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.…

  10. Recursive Feature Extraction in Graphs

    SciTech Connect

    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.

  11. 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.…

  12. Topic Model for Graph Mining.

    PubMed

    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.

  13. Kevin Bacon and Graph Theory

    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…

  14. A Note on Hamiltonian Graphs

    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…

  15. A Note on Hamiltonian Graphs

    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…

  16. Kevin Bacon and Graph Theory

    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…

  17. 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.

  18. 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.

  19. What is a complex graph?

    NASA Astrophysics Data System (ADS)

    Kim, Jongkwang; Wilhelm, Thomas

    2008-04-01

    Many papers published in recent years show that real-world graphs G(n,m) ( n nodes, m edges) are more or less “complex” in the sense that different topological features deviate from random graphs. Here we narrow the definition of graph complexity and argue that a complex graph contains many different subgraphs. We present different measures that quantify this complexity, for instance C1e, the relative number of non-isomorphic one-edge-deleted subgraphs (i.e. DECK size). However, because these different subgraph measures are computationally demanding, we also study simpler complexity measures focussing on slightly different aspects of graph complexity. We consider heuristically defined “product measures”, the products of two quantities which are zero in the extreme cases of a path and clique, and “entropy measures” quantifying the diversity of different topological features. The previously defined network/graph complexity measures Medium Articulation and Offdiagonal complexity ( OdC) belong to these two classes. We study OdC measures in some detail and compare it with our new measures. For all measures, the most complex graph G has a medium number of edges, between the edge numbers of the minimum and the maximum connected graph n-1graph complexity measures are characterized with the help of different example graphs. For all measures the corresponding time complexity is given. Finally, we discuss the complexity of 33 real-world graphs of different biological, social and economic systems with the six computationally most simple measures (including OdC). The complexities of the real graphs are compared with average complexities of two different random graph versions: complete random graphs (just fixed n,m) and rewired graphs with fixed node degrees.

  20. Cell-graph mining for breast tissue modeling and classification.

    PubMed

    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.

  1. A Glossary of Grammar and Linguistics.

    ERIC Educational Resources Information Center

    MacLeish, Andrew

    A guide to linguistic analysis and to the three co-existing grammars--conventional, structural, and transformational--this glossary, which is directed to the beginning student, provides descriptions of terms and topics as they are used in their most frequent and familiar senses. Encyclopedic descriptions and information about the referent are…

  2. 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.…

  3. 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…

  4. 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…

  5. 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…

  6. Common Sense in Teaching FL Grammar.

    ERIC Educational Resources Information Center

    Zucker, George K.

    This essay considers three areas in Spanish grammar that generally cause difficulty to English-speaking learners: the use of "ser" and "estar," the difference in use between the preterite and imperfect tenses, and the use of the subjunctive. Like most problematic grammatical elements in any language, these points are difficult for non-native…

  7. 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…

  8. 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…

  9. 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…

  10. 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…

  11. 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…

  12. 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…

  13. 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…

  14. 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…

  15. 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…

  16. 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…

  17. 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…

  18. 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…

  19. 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…

  20. 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…

  1. 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…

  2. 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…

  3. 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…

  4. Grammaire et communication (Grammar and Communication).

    ERIC Educational Resources Information Center

    Stirman-Langlois, Martine

    1994-01-01

    A technique for teaching French grammar that involves reading, rereading, and analyzing the language in authentic materials is discussed. The student is led to recognition and generalization of structures in the text. Text examples used here include a comic strip and a publicity blurb for a French city. (MSE)

  5. 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…

  6. 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…

  7. 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…

  8. 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…

  9. 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…

  10. A Reference Grammar of the Kanuri Language.

    ERIC Educational Resources Information Center

    Hutchison, John P.

    This study presents a grammatical analysis of the Kanuri language as it is spoken in Yerwa, the capital of Borno State in Nigeria. The material is organized in such a way as to be useful to students of the Kanuri language, to linguists, and to Kanuri people interested in the grammar of their language. The text is organized in pedagogical order…

  11. Arbitrary grammars generating context-free languages

    NASA Technical Reports Server (NTRS)

    Baker, B. S.

    1972-01-01

    If G is a grammar such that in each noncontext-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 simple corollaries of this theorem.

  12. What Research Tells Us about Teaching Grammar

    ERIC Educational Resources Information Center

    Smith, Michael W.; Wilhelm, Jeff

    2006-01-01

    The authors offer research studies and other documented evidence that teaching grammar without a meaningful context does not improve student writing, largely because that approach does not address the root causes of errors. Several resources that support this position and offer more productive strategies are summarized, including the authors'…

  13. The Grammar of Psychotherapy. A descriptive account.

    PubMed

    Cobb, J P; Lieberman, S

    1987-11-01

    The Grammar of Psychotherapy is a method of teaching both communication skills and the elements of psychotherapy. Supervised training is supplemented by self-monitored tasks. The course is economical in terms of tutors' time, and is particularly suitable for trainees in general psychiatry.

  14. 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…

  15. Eye Movements in Implicit Artificial Grammar Learning

    ERIC Educational Resources Information Center

    Silva, Susana; Inácio, Filomena; Folia, Vasiliki; Petersson, Karl Magnus

    2017-01-01

    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…

  16. The Restoration and the Grammar Schools

    ERIC Educational Resources Information Center

    d'l. Oakeshott, A. M.

    1973-01-01

    Argues that grammar and secondary schools did not suffer greatly during the period immediately after the restoration of the English monarchy in 1660. The author provides figures to show that, contrary to popular opinion, few dissenting teachers were dismissed during that period. (JF)

  17. What Is a Rule of Grammar?

    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,…

  18. 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…

  19. 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.

  20. Constructing splits graphs.

    PubMed

    Dress, Andreas W M; Huson, Daniel H

    2004-01-01

    Phylogenetic trees correspond one-to-one to compatible systems of splits and so splits play an important role in theoretical and computational aspects of phylogeny. Whereas any tree reconstruction method can be thought of as producing a compatible system of splits, an increasing number of phylogenetic algorithms are available that compute split systems that are not necessarily compatible and, thus, cannot always be represented by a tree. Such methods include the split decomposition, Neighbor-Net, consensus networks, and the Z-closure method. A more general split system of this kind can be represented graphically by a so-called splits graph, which generalizes the concept of a phylogenetic tree. This paper addresses the problem of computing a splits graph for a given set of splits. We have implemented all presented algorithms in a new program called SplitsTree4.

  1. An Unusual Exponential Graph

    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…

  2. Optical tomography on graphs

    NASA Astrophysics Data System (ADS)

    Chung, Francis J.; Gilbert, Anna C.; Hoskins, Jeremy G.; Schotland, John C.

    2017-05-01

    We present an algorithm for solving inverse problems on graphs analogous to those arising in diffuse optical tomography for continuous media. In particular, we formulate and analyze a discrete version of the inverse Born series, proving estimates characterizing the domain of convergence, approximation errors, and stability of our approach. We also present a modification which allows additional information on the structure of the potential to be incorporated, facilitating recovery for a broader class of problems.

  3. An Unusual Exponential Graph

    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…

  4. Convex Graph Invariants

    DTIC Science & Technology

    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

  5. Combined Grammar for the Modeling of Building Interiors

    NASA Astrophysics Data System (ADS)

    Becker, S.; Peter, M.; Fritsch, D.; Philipp, D.; Baier, P.; Dibak, C.

    2013-11-01

    As spatial grammars have proven successful and efficient to deliver LOD3 models, the next challenge is their extension to indoor applications, leading to LOD4 models. Therefore, a combined indoor grammar for the automatic generation of indoor models from erroneous and incomplete observation data is presented. In building interiors where inaccurate observation data is available, the grammar can be used to make the reconstruction process robust, and verify the reconstructed geometries. In unobserved building interiors, the grammar can generate hypotheses about possible indoor geometries matching the style of the rest of the building. The grammar combines concepts from L-systems and split grammars. It is designed in such way that it can be derived from observation data fully automatically. Thus, manual predefinitions of the grammar rules usually required to tune the grammar to a specific building style, become obsolete. The potential benefit of using our grammar as support for indoor modeling is evaluated based on an example where the grammar has been applied to automatically generate an indoor model from erroneous and incomplete traces gathered by foot-mounted MEMS/IMU positioning systems.

  6. 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.

  7. Exploring and Making Sense of Large Graphs

    DTIC Science & Technology

    2015-08-01

    number of its neighbors. In a directed graph, the in-degree of a vertex is the number of incoming edges, and its out-degree is the number of outgoing...upper bound for hh is obtained by considering the Frobenius norm of matrix W and 66 solving the inequality ‖W ‖F= √√√√ n∑ i=1 n∑ j=1 |Wij|2 < 1 with...and heterophily. Concretely, if H(i, i) > H(j, i) for all i 6= j, we say homophily is present. If the opposite inequality is true for all i, then

  8. Evaluation of Graph Pattern Matching Workloads in Graph Analysis Systems

    SciTech Connect

    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.

  9. Fast Robust PCA on Graphs

    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.

  10. Schulgrammatik und Fachgrammatiken: Fuer eine differenzierte Konzeption der didaktischen Grammatik (School Grammar and Scientific Grammar: Toward a Differentiated Concept of Didactic Grammar).

    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)

  11. Intentional control based on familiarity in artificial grammar learning.

    PubMed

    Wan, Lulu; Dienes, Zoltán; Fu, Xiaolan

    2008-12-01

    It is commonly held that implicit learning is based largely on familiarity. It is also commonly held that familiarity is not affected by intentions. It follows that people should not be able to use familiarity to distinguish strings from two different implicitly learned grammars. In two experiments, subjects were trained on two grammars and then asked to endorse strings from only one of the grammars. Subjects also rated how familiar each string felt and reported whether or not they used familiarity to make their grammaticality judgment. We found subjects could endorse the strings of just one grammar and ignore the strings from the other. Importantly, when subjects said they were using familiarity, the rated familiarity for test strings consistent with their chosen grammar was greater than that for strings from the other grammar. Familiarity, subjectively defined, is sensitive to intentions and can play a key role in strategic control.

  12. On Edge Exchangeable Random Graphs

    NASA Astrophysics Data System (ADS)

    Janson, Svante

    2017-06-01

    We study a recent model for edge exchangeable random graphs introduced by Crane and Dempsey; in particular we study asymptotic properties of the random simple graph obtained by merging multiple edges. We study a number of examples, and show that the model can produce dense, sparse and extremely sparse random graphs. One example yields a power-law degree distribution. We give some examples where the random graph is dense and converges a.s. in the sense of graph limit theory, but also an example where a.s. every graph limit is the limit of some subsequence. Another example is sparse and yields convergence to a non-integrable generalized graphon defined on (0,∞).

  13. Approximating centrality in evolving graphs: toward sublinearity

    NASA Astrophysics Data System (ADS)

    Priest, Benjamin W.; Cybenko, George

    2017-05-01

    The identification of important nodes is a ubiquitous problem in the analysis of social networks. Centrality indices (such as degree centrality, closeness centrality, betweenness centrality, PageRank, and others) are used across many domains to accomplish this task. However, the computation of such indices is expensive on large graphs. Moreover, evolving graphs are becoming increasingly important in many applications. It is therefore desirable to develop on-line algorithms that can approximate centrality measures using memory sublinear in the size of the graph. We discuss the challenges facing the semi-streaming computation of many centrality indices. In particular, we apply recent advances in the streaming and sketching literature to provide a preliminary streaming approximation algorithm for degree centrality utilizing CountSketch and a multi-pass semi-streaming approximation algorithm for closeness centrality leveraging a spanner obtained through iteratively sketching the vertex-edge adjacency matrix. We also discuss possible ways forward for approximating betweenness centrality, as well as spectral measures of centrality. We provide a preliminary result using sketched low-rank approximations to approximate the output of the HITS algorithm.

  14. 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.

  15. Flow graphs: interweaving dynamics and structure.

    PubMed

    Lambiotte, R; Sinatra, R; Delvenne, J-C; Evans, T S; Barahona, M; Latora, V

    2011-07-01

    The behavior of complex systems is determined not only by the topological organization of their interconnections but also by the dynamical processes taking place among their constituents. A faithful modeling of the dynamics is essential because different dynamical processes may be affected very differently by network topology. A full characterization of such systems thus requires a formalization that encompasses both aspects simultaneously, rather than relying only on the topological adjacency matrix. To achieve this, we introduce the concept of flow graphs, namely weighted networks where dynamical flows are embedded into the link weights. Flow graphs provide an integrated representation of the structure and dynamics of the system, which can then be analyzed with standard tools from network theory. Conversely, a structural network feature of our choice can also be used as the basis for the construction of a flow graph that will then encompass a dynamics biased by such a feature. We illustrate the ideas by focusing on the mathematical properties of generic linear processes on complex networks that can be represented as biased random walks and their dual consensus dynamics, and show how our framework improves our understanding of these processes.

  16. Role of selective attention in artificial grammar learning.

    PubMed

    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.

  17. Implementation of a Natural Language Processor Using Functional Grammar.

    DTIC Science & Technology

    1985-12-01

    in a completely different manner. [Ref. 5:pp. 81-883 ; "C. CASE GRAMMAR When Chomsky published his Aspects of the Theory of Syntax, 0 many linguists ...Grammar is a radical approach to linguistic theory when looked at from the Chomsky point of view. However, it compares favorably with the traditional...an explicit algorithm fcor constructing sentences. B. TRANSFORMATIONAL GRAMMAR The break from the traditionalists came in the 1950~’ s . Linguists were

  18. Potts model and graph theory

    NASA Astrophysics Data System (ADS)

    Wu, F. Y.

    1988-07-01

    Elementary exposition is given of some recent developments in studies of graphtheoretic aspects of the Potts model. Topics discussed include graphical expansions of the Potts partition function and correlation functions and their relationships with the chromatic, dichromatic, and flow polynomials occurring in graph theory. It is also shown that the Potts model realization of these classic graph-theoretic problems provides alternate and direct proofs of properties established heretofore only in the context of formal graph theory.

  19. Goal relevance and artificial grammar learning.

    PubMed

    Eitam, Baruch; Schul, Yaacov; Hassin, Ran R

    2009-02-01

    This investigation used a newly developed artificial grammar learning (AGL) paradigm in which participants were exposed to sequences of stimuli that varied in two dimensions (colours and letters) that were superimposed on each other. Variation within each dimension was determined by a different grammar. The results of two studies strongly suggest that implicit learning in AGL depends on the goal relevance of the to-be-learned dimension. Specifically, when only one of the two stimulus dimensions was relevant for their task (Experiment 1) participants learned the structure underlying the relevant, but not that of the irrelevant dimension. However, when both dimensions were relevant, both structures were learned (Experiment 2). These findings suggest that implicit learning occurs only in dimensions to which we are attuned. Based on the present results and on those of Eitam, Hassin, and Schul (2008) we suggest that focusing on goal relevance may provide new insights into the mechanisms underlying implicit learning.

  20. Exact numerical calculation of fixation probability and time on graphs.

    PubMed

    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.

  1. Parameter-dependent spectral statistics of chaotic quantum graphs: Neumann versus circular orthogonal ensemble boundary conditions.

    PubMed

    Hul, Oleh; Sirko, Leszek

    2011-06-01

    The parameter-dependent spectral statistics of totally connected quantum graphs with n = 4-30 vertices, such as the parametric velocities correlation functions and the distribution of curvatures, are studied. The inverse participation ratio (IPR), an important measure of localization effects, was also numerically investigated. In the calculations, we successfully used two different theoretical approaches. The first approach was based on the graphs' eigenenergies and wave functions calculations, while the second one used the eigenphases and the eigenvectors of the bond scattering matrix S(k). We considered graphs with Neumann and circular orthogonal ensemble (COE) boundary conditions. We show that in contrast to large Neumann graphs, for which the departure of many parameter-dependent spectral statistics from the random matrix theory (RMT) predictions is observed, for large COE graphs, the spectral statistics and IPR are in good agreement with the RMT predictions.

  2. Contact Graph Routing

    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

  3. 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.

  4. Strongly Regular Graphs,

    DTIC Science & Technology

    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

  5. Systemic Grammar in Computation. The Nigel Case.

    DTIC Science & Technology

    1984-02-01

    features and functions like SUBJECT. ACTOR, and THEME Features are the building blocks of the paradigmatic organization of gramma e. of grammar as choice...Halliday, Learning How to Mean. Edward Arnold, 1975. 16 lHalliday 76a] Halliday, M. A. K., System and Function in Language. Oxford University Press...London, 1976. [Halliday 76b] Halliday, M.A.K., "The English verbal group," in Kress, G. (ed.). Halliday: System and Function in Language, Oxford University

  6. Nigel: A Systemic Grammar for Text Generation.

    DTIC Science & Technology

    1983-02-01

    in the logical component). Henrici [ Henrici 811 observes that "linear recursion is rather more troublesome" than recursion through embedding (which...notation defined by Henrici [ Henrici 81]. However, we have neither exhausted the grammar nor reached the lexicon. This section will present how the...Halliday, M. A. K., Language as Social Semiotic, University Park Press, Baltimore, 1978 [ Henrici 81] Henrici , A., "Some notes on the systemic generation of

  7. Graph Theory of Tower Tasks

    PubMed Central

    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

  8. 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.

  9. Spectral partitioning in equitable graphs

    NASA Astrophysics Data System (ADS)

    Barucca, Paolo

    2017-06-01

    Graph partitioning problems emerge in a wide variety of complex systems, ranging from biology to finance, but can be rigorously analyzed and solved only for a few graph ensembles. Here, an ensemble of equitable graphs, i.e., random graphs with a block-regular structure, is studied, for which analytical results can be obtained. In particular, the spectral density of this ensemble is computed exactly for a modular and bipartite structure. Kesten-McKay's law for random regular graphs is found analytically to apply also for modular and bipartite structures when blocks are homogeneous. An exact solution to graph partitioning for two equal-sized communities is proposed and verified numerically, and a conjecture on the absence of an efficient recovery detectability transition in equitable graphs is suggested. A final discussion summarizes results and outlines their relevance for the solution of graph partitioning problems in other graph ensembles, in particular for the study of detectability thresholds and resolution limits in stochastic block models.

  10. An incremental interactive algorithm for regular grammar inference

    SciTech Connect

    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.

  11. Generating graphs for visual analytics through interactive sketching.

    PubMed

    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.

  12. 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.

  13. 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.

  14. Graph Visualization for RDF Graphs with SPARQL-EndPoints

    SciTech Connect

    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.

  15. Quantum Graph Analysis

    SciTech Connect

    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%.

  16. Comparing pedigree graphs.

    PubMed

    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.

  17. 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.

  18. Quantization of gauge fields, graph polynomials and graph homology

    SciTech Connect

    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.

  19. Matrix computations on mesh arrays

    SciTech Connect

    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.

  20. 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.