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

  3. Generative Graph Grammar of Neo-Vaiśeṣika Formal Ontology (NVFO)

    NASA Astrophysics Data System (ADS)

    Tavva, Rajesh; Singh, Navjyoti

    NLP applications for Sanskrit so far work within computational paradigm of string grammars. However, to compute 'meanings', as in traditional śā bdabodha prakriyā-s, there is a need to develop suitable graph grammars. Ontological structures are fundamentally graphs. We work within the formal framework of Neo-Vaiśeṣika Formal Ontology (NVFO) to propose a generative graph grammar. The proposed formal grammar only produces well-formed graphs that can be readily interpreted in accordance with Vaiśeṣ ika Ontology. We show that graphs not permitted by Vaiśeṣ ika ontology are not generated by the proposed grammar. Further, we write Interpreter of these graphical structures. This creates computational environment which can be deployed for writing computational applications of Vaiśeṣ ika ontology. We illustrate how this environment can be used to create applications like computing śā bdabodha of sentences.

  4. Matrix Equations and Normal Forms for Context-Free Grammars

    NASA Astrophysics Data System (ADS)

    Rosenkrantz, Daniel J.

    The relationship between the set of productions of a context-free grammar and the corresponding set of defining equations is first pointed out. The closure operation on a matrix of strings is defined and this concept is used to formalize the solution to a set of linear equations. A procedure is then given for rewriting a context-free grammar in Greibach normal form, where the replacement string of each production begins with a terminal symbol. An additional procedure is given for rewriting the grammar so that each replacement string both begins and ends with a terminal symbol. Neither procedure requires the evaluation of regular expressions over the total vocabulary of the grammar, as is required by Greibach’s procedure.

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

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

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

    PubMed Central

    Wang, Yi

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

  8. The uniqueness of DMAX-matrix graph invariants.

    PubMed

    Dehmer, Matthias; Shi, Yongtang

    2014-01-01

    In this paper, we examine the uniqueness (discrimination power) of a newly proposed graph invariant based on the matrix DMAX defined by Randić et al. In order to do so, we use exhaustively generated graphs instead of special graph classes such as trees only. Using these graph classes allow us to generalize the findings towards complex networks as they usually do not possess any structural constraints. We obtain that the uniqueness of this newly proposed graph invariant is approximately as low as the uniqueness of the Balaban J index on exhaustively generated (general) graphs. PMID:24392099

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

  10. Unfolding Grammars in Adhesive Categories

    NASA Astrophysics Data System (ADS)

    Baldan, Paolo; Corradini, Andrea; Heindel, Tobias; König, Barbara; Sobociński, Paweł

    We generalize the unfolding semantics, previously developed for concrete formalisms such as Petri nets and graph grammars, to the abstract setting of (single pushout) rewriting over adhesive categories. The unfolding construction is characterized as a coreflection, i.e. the unfolding functor arises as the right adjoint to the embedding of the category of occurrence grammars into the category of grammars.

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

  12. Graph-based simulation of quantum computation in the density matrix representation

    NASA Astrophysics Data System (ADS)

    Viamontes, George F.; Markov, Igor L.; Hayes, John P.

    2004-08-01

    Quantum-mechanical phenomena are playing an increasing role in information processing, as transistor sizes approach the nanometer level, and quantum circuits and data encoding methods appear in the securest forms of communication. Simulating such phenomena efficiently is exceedingly difficult because of the vast size of the quantum state space involved. A major complication is caused by errors (noise) due to unwanted interactions between the quantum states and the environment. Consequently, simulating quantum circuits and their associated errors using the density matrix representation is potentially significant in many applications, but is well beyond the computational abilities of most classical simulation techniques in both time and memory resources. The size of a density matrix grows exponentially with the number of qubits simulated, rendering array-based simulation techniques that explicitly store the density matrix intractable. In this work, we propose a new technique aimed at efficiently simulating quantum circuits that are subject to errors. In particular, we describe new graph-based algorithms implemented in the simulator QuIDDPro/D. While previously reported graph-based simulators operate in terms of the state-vector representation, these new algorithms use the density matrix representation. To gauge the improvements offered by QuIDDPro/D, we compare its simulation performance with an optimized array-based simulator called QCSim. Empirical results, generated by both simulators on a set of quantum circuit benchmarks involving error correction, reversible logic, communication, and quantum search, show that the graph-based approach far outperforms the array-based approach.

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

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

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

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

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

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

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

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

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

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

  3. Sexist Grammar.

    ERIC Educational Resources Information Center

    Stanley, Julia P.

    From the beginnings of English grammar in the early sixteenth century, our language has been described by men, and the usage promulgated as the "standard" has been that of men. Because men have been able to effectively control English through their control of the communications media and educational institutions, they have made our language an…

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

    DOE PAGES

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

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

  6. Evolution of Universal Grammar

    NASA Astrophysics Data System (ADS)

    Nowak, Martin A.; Komarova, Natalia L.; Niyogi, Partha

    2001-01-01

    Universal grammar specifies the mechanism of language acquisition. It determines the range of grammatical hypothesis that children entertain during language learning and the procedure they use for evaluating input sentences. How universal grammar arose is a major challenge for evolutionary biology. We present a mathematical framework for the evolutionary dynamics of grammar learning. The central result is a coherence threshold, which specifies the condition for a universal grammar to induce coherent communication within a population. We study selection of grammars within the same universal grammar and competition between different universal grammars. We calculate the condition under which natural selection favors the emergence of rule-based, generative grammars that underlie complex language.

  7. Universal Quantum Graphs

    NASA Astrophysics Data System (ADS)

    Pluhař, Z.; Weidenmüller, H. A.

    2014-04-01

    For time-reversal invariant graphs we prove the Bohigas-Giannoni-Schmit conjecture in its most general form: For graphs that are mixing in the classical limit, all spectral correlation functions coincide with those of the Gaussian orthogonal ensemble of random matrices. For open graphs, we derive the analogous identities for all S-matrix correlation functions.

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

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

  10. [Local population of Eritrichium caucasicum as an object of mathematical modelling. I. Life cycle graph and a nonautonomous matrix model].

    PubMed

    Logofet, D O; Belova, I N; Kazantseva, E S; Onipchenko, V G

    2016-01-01

    For the plant species, which is considered a short-lived perennial, we have composed a scale of ontogenetic stages and the life cycle graph (LCG) according to annual observations on permanent sample plots in an Alpine lichen heath during the 2009-2014 period. The LCG that reflects seed reproduction has been reduced to the one that avoids the stage of soil seed bank, yet preserves the arcs of annual recruitment. The corresponding matrix model of stage-structured population dynamics has four stages: juvenile plants (including seedlings), virginal, generative, and 'terminally generative' (the plants die after seed production). Model calibration reduces to directly calculating the rates of transition between stages and those of delays within stages from the data of only one time step, while keeping the two reproduction rates uncertain, yet confined to the quantitative bounds of observed recruitment. This has enabled us to determine a feasible range for the dominant eigenvalue of the model matrix, i.e., the quantitative bounds for the measure of how the local population adapts to its environment, at each of the five time steps, resulting in aformally nonautonomous model. To obtain 'age-specific parameters' from a stage-classified model, we have applied the technique that constructs a virtual absorbing Markov chain and calculates its fundamental matrix. In a nonautonomous model, the estimates of life expectancy also depend on the time of observation (that fixes certain environmental conditions), and vary from two to nearly seven years. The estimates reveal how specifically short lives the short-lived perennial, while their range motivates the task to average the model matrices over the whole period of observation. The model indicates that Eritrichium caucasicum plants spend the most part of their life span in the virginal stage under each of the environment conditions observed, thus revealing the place retention strategy by C. K6rner (2003), or the delayed

  11. [Local population of Eritrichium caucasicum as an object of mathematical modelling. I. Life cycle graph and a nonautonomous matrix model].

    PubMed

    Logofet, D O; Belova, I N; Kazantseva, E S; Onipchenko, V G

    2016-01-01

    For the plant species, which is considered a short-lived perennial, we have composed a scale of ontogenetic stages and the life cycle graph (LCG) according to annual observations on permanent sample plots in an Alpine lichen heath during the 2009-2014 period. The LCG that reflects seed reproduction has been reduced to the one that avoids the stage of soil seed bank, yet preserves the arcs of annual recruitment. The corresponding matrix model of stage-structured population dynamics has four stages: juvenile plants (including seedlings), virginal, generative, and 'terminally generative' (the plants die after seed production). Model calibration reduces to directly calculating the rates of transition between stages and those of delays within stages from the data of only one time step, while keeping the two reproduction rates uncertain, yet confined to the quantitative bounds of observed recruitment. This has enabled us to determine a feasible range for the dominant eigenvalue of the model matrix, i.e., the quantitative bounds for the measure of how the local population adapts to its environment, at each of the five time steps, resulting in aformally nonautonomous model. To obtain 'age-specific parameters' from a stage-classified model, we have applied the technique that constructs a virtual absorbing Markov chain and calculates its fundamental matrix. In a nonautonomous model, the estimates of life expectancy also depend on the time of observation (that fixes certain environmental conditions), and vary from two to nearly seven years. The estimates reveal how specifically short lives the short-lived perennial, while their range motivates the task to average the model matrices over the whole period of observation. The model indicates that Eritrichium caucasicum plants spend the most part of their life span in the virginal stage under each of the environment conditions observed, thus revealing the place retention strategy by C. K6rner (2003), or the delayed

  12. Why Revitalize Grammar?

    ERIC Educational Resources Information Center

    Dunn, Patricia A.; Lindblom, Kenneth

    2003-01-01

    Challenges some problematic issues of grammar instruction. Transforms inconsequential discussion of nouns, adverbs, and past participles to more significant discussion about writing, access, and improving the world. Explores four activities to do with student writing other than correct grammar. (SG)

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

  14. Role and Reference Grammar.

    ERIC Educational Resources Information Center

    Van Valin, Robert D., Jr.

    This paper discusses Role and Reference Grammar (RRG), which is a structuralist-formalist theory of grammar. RRG grew out of an attempt to answer two fundamental questions: (1) what would linguistic theory look like if it were based on the analysis of Lakhota, Tagalog, and Dyirbal, rather than on the analysis of English?; and (2) how can the…

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

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

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

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

  19. 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 relies on such devices…

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

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

  2. 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. PMID:26388791

  3. Graph Library

    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 abilitymore » to export graphs into various open formats such as DOT and GML.« less

  4. Grammar and the Language Arts.

    ERIC Educational Resources Information Center

    Faulkner, Janice H.

    This book introduces a specific approach to sentence analysis by comparing traditional grammar with newer methods, including transformational grammar. The first chapter discusses the teaching of grammar and language skills and the use of standard and nonstandard dialects. Traditional grammar is defined and discussed in chapter 2. The other…

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

  6. Spectral fluctuations of quantum graphs

    NASA Astrophysics Data System (ADS)

    Pluhař, Z.; Weidenmüller, H. A.

    2014-10-01

    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.

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

  8. Context-Free Categorical Grammars

    NASA Astrophysics Data System (ADS)

    Bauderon, Michel; Chen, Rui; Ly, Olivier

    We define generic categorical notions of rewriting and grammar, using two basic operations, pullback and pushout, and show that these categorical grammars are intrinsically context-free in the sense of Courcelle. We then specialise to various settings, including classical word grammars, hyperedge replacement grammars or node-replacement grammars. We show that some languages which are classical counter-example to context-freeness become context-free within this new framework.

  9. 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. PMID:26684059

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

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

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

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

  12. Swahili Learners' Reference Grammar. African Language Learners' Reference Grammar Series.

    ERIC Educational Resources Information Center

    Thompson, Katrina Daly; Schleicher, Antonia Folarin

    This reference grammar is written for speakers of English who are learning Swahili. Because many language learners are not familiar with the grammatical terminology, this book explains the basic terminology and concepts of English grammar that are necessary for understanding the grammar of Swahili. It assumes no formal knowledge of English grammar…

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

  14. Graph characterization via Ihara coefficients.

    PubMed

    Ren, Peng; Wilson, Richard C; Hancock, Edwin R

    2011-02-01

    The novel contributions of this paper are twofold. First, we demonstrate how to characterize unweighted graphs in a permutation-invariant manner using the polynomial coefficients from the Ihara zeta function, i.e., the Ihara coefficients. Second, we generalize the definition of the Ihara coefficients to edge-weighted graphs. For an unweighted graph, the Ihara zeta function is the reciprocal of a quasi characteristic polynomial of the adjacency matrix of the associated oriented line graph. Since the Ihara zeta function has poles that give rise to infinities, the most convenient numerically stable representation is to work with the coefficients of the quasi characteristic polynomial. Moreover, the polynomial coefficients are invariant to vertex order permutations and also convey information concerning the cycle structure of the graph. To generalize the representation to edge-weighted graphs, we make use of the reduced Bartholdi zeta function. We prove that the computation of the Ihara coefficients for unweighted graphs is a special case of our proposed method for unit edge weights. We also present a spectral analysis of the Ihara coefficients and indicate their advantages over other graph spectral methods. We apply the proposed graph characterization method to capturing graph-class structure and clustering graphs. Experimental results reveal that the Ihara coefficients are more effective than methods based on Laplacian spectra.

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

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

  17. Grammar and the Spoken Language.

    ERIC Educational Resources Information Center

    Carter, Ronald; McCarthy, Michael

    1995-01-01

    Argues that second language teaching that aims to foster speaking skills and natural spoken interaction should be based upon the grammar of spoken language, not on grammars that mainly reflect written norms. Using evidence from a mini-corpus of conversational English, it is shown that popular pedagogical grammars are deficient in conversational…

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

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

  20. Campaign graphs

    SciTech Connect

    Simmons, G.J.

    1988-01-01

    We define a class of geometrical constructions in the plane in which each (unextended) line lies on (precisely) k points, and every point is an endpoint of (precisely) one line. We will refer to any construction satisfying these conditions as a campaign graph, or as a k-campaign graph if the value of k isn't clear from the context. A k-campaign graph, G, is said to be critical if no subgraph of G is also a k-campaign graph. 11 figs.

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

  2. 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 M. A. K. Halliday's…

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

  4. Teaching Grammar for Proficiency.

    ERIC Educational Resources Information Center

    Higgs, Theodore V.

    1985-01-01

    Discusses a foreign language pedagogy that facilitates teaching for communication and teaching grammar, which is defined as a system for converting meaning into language. The teacher is advised to do in the classroom only what cannot be done elsewhere. Four instructional tactics are described. (SED)

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

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

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

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

  9. GPS (Grammar Positioning System)

    ERIC Educational Resources Information Center

    Blaauw-Hara, Mark; Anderson, Andy

    2007-01-01

    In this Cross Talk, Mark Blaauw-Hara, the author of "Mapping the Frontier: A Survey of Twenty Years of Grammar Articles in 'TETYC,'" and one of the manuscript's reviewers, Andy Anderson, engage in a brief conversation about the essay, its content, and the processes of writing, reviewing, and revising. This article is presented in three sections:…

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

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

  12. A GRAMMAR OF SANGO.

    ERIC Educational Resources Information Center

    SAMARIN, WILLIAM J.

    THE GRAMMAR OF SANGO (THE LINGUA-FRANCA OF THE CENTRAL AFRICAN REPUBLIC) IS DESCRIBED IN THREE PARTS OF THIS TEXT. TWO ADDITIONAL PARTS ARE DEVOTED TO RELATED INFORMATION AND ILLUSTRATION. PART ONE, PHONOLOGY, IS CONCERNED WITH A DESCRIPTION AND EXEMPLIFICATION OF THE PHONEMES OF SANGO, A DISCUSSION OF THE VARIATIONS BETWEEN WORDS WHICH RESULT…

  13. Spectral correlations of individual quantum graphs.

    PubMed

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

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

  15. On the Generative Power of Multiple Context-Free Grammars and Macro Grammars

    NASA Astrophysics Data System (ADS)

    Seki, Hiroyuki; Kato, Yuki

    Several grammars of which generative power is between context-free grammar and context-sensitive grammar were proposed. Among them are macro grammar and tree adjoining grammar. Multiple context-free grammar is also a natural extension of context-free grammars, and is known to be stronger in its generative power than tree adjoining grammar and yet to be recognizable in polynomial time. In this paper, the generative power of several subclasses of variable-linear macro grammars and that of multiple context-free grammars are compared in details.

  16. Semantic graphs and associative memories.

    PubMed

    Pomi, Andrés; Mizraji, Eduardo

    2004-12-01

    Graphs have been increasingly utilized in the characterization of complex networks from diverse origins, including different kinds of semantic networks. Human memories are associative and are known to support complex semantic nets; these nets are represented by graphs. However, it is not known how the brain can sustain these semantic graphs. The vision of cognitive brain activities, shown by modern functional imaging techniques, assigns renewed value to classical distributed associative memory models. Here we show that these neural network models, also known as correlation matrix memories, naturally support a graph representation of the stored semantic structure. We demonstrate that the adjacency matrix of this graph of associations is just the memory coded with the standard basis of the concept vector space, and that the spectrum of the graph is a code invariant of the memory. As long as the assumptions of the model remain valid this result provides a practical method to predict and modify the evolution of the cognitive dynamics. Also, it could provide us with a way to comprehend how individual brains that map the external reality, almost surely with different particular vector representations, are nevertheless able to communicate and share a common knowledge of the world. We finish presenting adaptive association graphs, an extension of the model that makes use of the tensor product, which provides a solution to the known problem of branching in semantic nets.

  17. Semantic graphs and associative memories

    NASA Astrophysics Data System (ADS)

    Pomi, Andrés; Mizraji, Eduardo

    2004-12-01

    Graphs have been increasingly utilized in the characterization of complex networks from diverse origins, including different kinds of semantic networks. Human memories are associative and are known to support complex semantic nets; these nets are represented by graphs. However, it is not known how the brain can sustain these semantic graphs. The vision of cognitive brain activities, shown by modern functional imaging techniques, assigns renewed value to classical distributed associative memory models. Here we show that these neural network models, also known as correlation matrix memories, naturally support a graph representation of the stored semantic structure. We demonstrate that the adjacency matrix of this graph of associations is just the memory coded with the standard basis of the concept vector space, and that the spectrum of the graph is a code invariant of the memory. As long as the assumptions of the model remain valid this result provides a practical method to predict and modify the evolution of the cognitive dynamics. Also, it could provide us with a way to comprehend how individual brains that map the external reality, almost surely with different particular vector representations, are nevertheless able to communicate and share a common knowledge of the world. We finish presenting adaptive association graphs, an extension of the model that makes use of the tensor product, which provides a solution to the known problem of branching in semantic nets.

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

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

  20. Grammar and the Spoken Language.

    ERIC Educational Resources Information Center

    Carter, Ronald; McCarthy, Michael

    This paper argues that second language instruction that aims to foster speaking skills and natural spoken interaction should be based upon the grammar of the spoken language, and not on grammars that reflect written norms. Using evidence from a corpus of conversational English, this examination focuses on how four grammatical features that occur…

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

  2. Entity grammar systems: a grammatical tool for studying the hierarchical structures of biological systems.

    PubMed

    Wang, Yun

    2004-05-01

    The hierarchical structures of biological systems are the typical complex hierarchical dynamical structures in the physical world, the effective investigations on which could not be performed with the existing formal grammar systems. To meet the needs of the investigation on these kinds of systems, especially the emerging field of system biology, a grammatical tool was proposed in the present article. Because the grammatical tool mainly deals with the systems composed of structured entities, they are called entity grammar systems (EGSs). The structure of entities in EGSs have the general form of the objects in the physical world, which means EGSs could be used as a tool to study the complex system composed of many objects with different structures, just like the biological systems. The article contains the formal definition of EGSs and the hierarchy of EGSs, which is congruent with the Chomsky hierarchy. The relationship between EGSs and array grammar systems, graph grammar systems, tree grammar systems, multi-set grammar systems are discussed to show the generative power of EGSs. At the end of the present article, the steps to define new grammar systems with the form of EGS are provided and the possible applicable fields of EGSs are discussed. PMID:15006443

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

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

  5. Universal spectral statistics in quantum graphs.

    PubMed

    Gnutzmann, Sven; Altland, Alexander

    2004-11-01

    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.

  6. Technology Helps Students Learn Grammar.

    ERIC Educational Resources Information Center

    Bowen, Candace Perkins

    1999-01-01

    Describes several recent approaches on college campuses that use technology (including both Web sites and CD-ROM virtual environments) to help journalism students learn grammar. Notes successes and problems. (SR)

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

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

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

  10. A Similarity Search Using Molecular Topological Graphs

    PubMed Central

    Fukunishi, Yoshifumi; Nakamura, Haruki

    2009-01-01

    A molecular similarity measure has been developed using molecular topological graphs and atomic partial charges. Two kinds of topological graphs were used. One is the ordinary adjacency matrix and the other is a matrix which represents the minimum path length between two atoms of the molecule. The ordinary adjacency matrix is suitable to compare the local structures of molecules such as functional groups, and the other matrix is suitable to compare the global structures of molecules. The combination of these two matrices gave a similarity measure. This method was applied to in silico drug screening, and the results showed that it was effective as a similarity measure. PMID:20037730

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

  12. Understanding Graphs & Charts.

    ERIC Educational Resources Information Center

    Cleary, John J.; Gravely, Mary Liles

    Developed by educators from the Emily Griffith Opportunity School, this teacher's guide was developed for a 4-hour workshop to teach employees how to read the charts and graphs they need in the workplace. The unit covers four types of graphs: pictographs, bar graphs, line graphs, and circle graphs. The guide is divided into four sections: reading…

  13. Area law for random graph states

    NASA Astrophysics Data System (ADS)

    Collins, Benoît; Nechita, Ion; Życzkowski, Karol

    2013-08-01

    Random pure states of multi-partite quantum systems, associated with arbitrary graphs, are investigated. Each vertex of the graph represents a generic interaction between subsystems, described by a random unitary matrix distributed according to the Haar measure, while each edge of the graph represents a bipartite, maximally entangled state. For any splitting of the graph into two parts we consider the corresponding partition of the quantum system and compute the average entropy of entanglement. First, in the special case where the partition does not cross any vertex of the graph, we show that the area law is satisfied exactly. In the general case, we show that the entropy of entanglement obeys an area law on average, this time with a correction term that depends on the topologies of the graph and of the partition. The results obtained are applied to the problem of distribution of quantum entanglement in a quantum network with prescribed topology.

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

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

  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. Dynamic graph system for a semantic database

    SciTech Connect

    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.

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

  19. Ezekiel graphs

    SciTech Connect

    Simmons, G.J.

    1991-01-01

    In spite of the old adage that No finite sequence of symbols is random,'' there are many instances in which it is desirable to quantify how random'' a finite sequence is. Pseudorandom number generators and cryptographic key generators typically expand a short, randomly chosen, seed sequence into a much longer sequence which should appear random to anyone ignorant of the seed. Unique initiating signals chosen to minimize the likelihood of an accidental initiation of an important action should be random'' to lessen the chance of their natural occurrence, etc. Consequently, numerous tests for the randomness of finite sequences have been proposed. John Milnor argued that if a binary sequence is random then the fraction of 1's, r{sub 1}, should be very nearly 1/2 in it and in all of what he called its derivatives. Since every sequence has a unique derivative this defines a natural family of digraphs, G{sub n}, on 2{sup n} vertices in which vertices are labeled with n-bit binary sequences and an edge is directed from the vertex labeled with the sequence A to the vertex labeled with the sequence B if B is the derivative of A. Each component of G{sub n} is eventually cyclic. This paper is concerned with a special case in which the sequences in a cycle are all cyclic shifts of a single sequence -- hence the name of Ezekiel graphs. Surprising, there are Ezekiel graphs for which r{sub 1} is as close to 1/2 as is numerically possible, i.e., that satisfy Milnor's test for randomness as closely as it can be satisfied, even though the sequence of sequences are about as far from random as is conceivable. In this paper the existence and properties of Ezekiel sequences are investigated from an algebraic standpoint.

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

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

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

  3. Welcoming Grammar Back into the Writing Classroom.

    ERIC Educational Resources Information Center

    Devet, Bonnie

    2002-01-01

    Describes three approaches with which grammar may be welcomed back into the composition classroom. Considers how the teaching of grammar is making a comeback, with scholars acknowledging that the objections raised by process theories were valid but also investigating how to use grammar in writing classrooms, how to answer old process objections,…

  4. Treacherous Allies: Foreign Language Grammar Checkers.

    ERIC Educational Resources Information Center

    Jacobs, Gabriel; Rodgers, Catherine

    1999-01-01

    Discusses the use of a French computerized grammar checker as a learning and teaching resource. Presents the results of a controlled series of experiments in which groups of students were given the task of correcting French texts containing grammatical, lexical, and orthographical errors using an on-screen grammar checker or grammar books and…

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

  7. 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 THE TESTER AND…

  8. The evolutionary dynamics of grammar acquisition.

    PubMed

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

    2001-03-01

    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.

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

  10. Graphing for Any Grade.

    ERIC Educational Resources Information Center

    Nibbelink, William

    1982-01-01

    An instructional sequence for teaching graphing that has been extensively field tested in kindergarten through grade six is detailed. The material begins with point graphs, employs a movable y-axis to begin with minimal clutter, and has graphs constructed before reading graphs is required. (MP)

  11. Teachers' Theories in Grammar Teaching.

    ERIC Educational Resources Information Center

    Borg, Simon

    1999-01-01

    Considers how research into researchers' theories in English language teaching (ELT) can enhance our understanding of instruction and provide the basis of effective teacher-development work. The nature of teachers' theories is illustrated with examples from classroom research on grammar teaching. Discusses a study conducted with five…

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

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

  14. A Lifetime of Grammar Teaching

    ERIC Educational Resources Information Center

    Ellis, Rod

    2012-01-01

    The author has worked as a language teacher, teacher educator, and second language acquisition (SLA) researcher for over forty years. During this time grammar has figured largely in his thinking, in part because it has traditionally been so central to language pedagogy and in part because he became fascinated with how the human mind grapples with…

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

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

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

  18. A REFERENCE GRAMMAR OF PANJABI.

    ERIC Educational Resources Information Center

    GILL, HARJEET S.; GLEASON, HENRY A., JR.

    A REFERENCE GRAMMAR WAS PREPARED FOR STUDENTS OF PANJABI. THE INTENTION OF THE COMPILERS WAS TO MAKE IT USEFUL TO THOSE PREPARING TEACHING MATERIALS FOR PANJABI, THOSE TEACHING THE LANGUAGE BY MODERN AURAL-LINGUAL METHODS, OR OTHER USERS (NOT NECESSARILY PROFESSIONAL LINGUISTS) WHO WISH A DESCRIPTION BASED EQUALLY ON THE SPOKEN AND THE WRITTEN…

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

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

  1. Grammar on the Information Superhighway: Proceed with Caution.

    ERIC Educational Resources Information Center

    Perrin, Robert

    2003-01-01

    Describes six categories of websites on grammar. Considers the advantages and disadvantages that Internet grammar provides. Presents an annotated list of 15 web sites on grammar. Suggests adopting a positive but cautious approach to grammar on the Internet. Concludes that grammar on the Internet is a potentially helpful resource to use in addition…

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

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

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

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

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

  7. The minimalist grammar of action.

    PubMed

    Pastra, Katerina; Aloimonos, Yiannis

    2012-01-12

    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.

  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. On the Spectral Gap of a Quantum Graph

    NASA Astrophysics Data System (ADS)

    Kennedy, James B.; Kurasov, Pavel; Malenová, Gabriela; Mugnolo, Delio

    2016-09-01

    We consider the problem of finding universal bounds of "isoperimetric" or "isodiametric" type on the spectral gap of the Laplacian on a metric graph with natural boundary conditions at the vertices, in terms of various analytical and combinatorial properties of the graph: its total length, diameter, number of vertices and number of edges. We investigate which combinations of parameters are necessary to obtain non-trivial upper and lower bounds and obtain a number of sharp estimates in terms of these parameters. We also show that, in contrast to the Laplacian matrix on a combinatorial graph, no bound depending only on the diameter is possible. As a special case of our results on metric graphs, we deduce estimates for the normalised Laplacian matrix on combinatorial graphs which, surprisingly, are sometimes sharper than the ones obtained by purely combinatorial methods in the graph theoretical literature.

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

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

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

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

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

  16. Graphing with "LogoWriter."

    ERIC Educational Resources Information Center

    Yoder, Sharon K.

    This book discusses four kinds of graphs that are taught in mathematics at the middle school level: pictographs, bar graphs, line graphs, and circle graphs. The chapters on each of these types of graphs contain information such as starting, scaling, drawing, labeling, and finishing the graphs using "LogoWriter." The final chapter of the book…

  17. Methods of visualizing graphs

    SciTech Connect

    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.

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

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

  20. Developing Students' Textual Intelligence through Grammar.

    ERIC Educational Resources Information Center

    Burke, Jim

    2001-01-01

    Discusses "textual intelligence": knowledge of how texts of all kinds work. Describes how the author uses grammar in his classroom to help students understand how to read and write better and how to think with greater clarity. Describes activities used before and after students read or write. Argues that grammar is a process that helps students…

  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. Second Language Acquisition and Universal Grammar.

    ERIC Educational Resources Information Center

    White, Lydia

    1990-01-01

    Discusses the motivation for Universal Grammar (UG), as assumed in the principles and parameters framework of generative grammar (Chomsky, 1981), focusing on the logical problem of first-language acquisition and the potential role of UG in second-language acquisition. Recent experimental research regarding the second-language status of the…

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

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

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

  6. TRANSFORMATIONAL GRAMMAR--A GUIDE FOR TEACHERS.

    ERIC Educational Resources Information Center

    AURBACH, JOSEPH; AND OTHERS

    THE AUTHORS HAVE DESIGNED THIS GUIDE FOR NON-LINGUISTICALLY ORIENTED ENGLISH AND LANGUAGE ARTS TEACHERS WHO ARE FACED WITH THE PROBLEM OF TEACHING "THE NEW GRAMMAR." THE INTRODUCTION PRESENTS A RATIONALE FOR THE TEACHING OF LINGUISTICS IN THE CLASSROOM--"THE NEW GRAMMARS, INTELLIGENTLY APPLIED, MAY HELP CHILDREN NOT ONLY UNDERSTAND THE SYNTAX OF…

  7. Romanian Grammar Workbook for Peace Corps Volunteers.

    ERIC Educational Resources Information Center

    Peace Corps (Moldova).

    Designed as a reference tool for continued language learning beyond the beginning level, this workbook provides explanations and sets of exercises for learning, practicing, and understanding the major points of Romanian grammar. The manual contains 11 units on certain grammar problems for use with a tutor or under self-guided learning…

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

  9. Space Grammar, Analysability, and the English Passive.

    ERIC Educational Resources Information Center

    Langacker, Ronald W.

    1982-01-01

    Discusses alternatives to a number of assumptions fundamental to established linguistic theory which lead to a coherent view of linguistic structure that treats grammar as a symbolic phenomenon and emphasizes importance of analyzability to grammatical structure. Outlines descriptive framework called Space Grammar and its approach to semantic…

  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…

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

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

  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. Studying Grammar in the Technological Age

    ERIC Educational Resources Information Center

    Ediger, Marlow

    2012-01-01

    When being a student in grade school as well as in high school (1934-1946), grammar was heavily emphasized in English/language arts classes, particularly in grades four through the senior year in high school. Evidently, teachers and school administrators then saw a theoretical way to assist pupils in writing achievement. Grammar and writing were…

  15. Grammar-Guided Writing for AAC Users

    ERIC Educational Resources Information Center

    Hunnicutt, Sheri; Magnuson, Tina

    2007-01-01

    A method of grammar-guided writing has been devised to guide graphic sign users through the construction of text messages for use in e-mail and other applications with a remote receiver. The purpose is to promote morphologically and syntactically correct sentences. The available grammatical structures in grammar-guided writing are the highest…

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

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

  18. Chamorro Reference Grammar. Pali Language Texts: Micronesia.

    ERIC Educational Resources Information Center

    Topping, Donald M.; Dungca, Bernadita C.

    This detailed reference grammar of Chamorro, the native Malayo-Polynesian language spoken in Guam and the other Mariana Islands (Saipan, Rota, Tinian), differs from earlier grammars of the language in that: (1) it includes new data; (2) it offers a different interpretation of some of the data based on more recent linguistic concepts; and (3) it is…

  19. Hyperspectral image segmentation using spatial-spectral graphs

    NASA Astrophysics Data System (ADS)

    Gillis, David B.; Bowles, Jeffrey H.

    2012-06-01

    Spectral graph theory has proven to be a useful tool in the analysis of high-dimensional data sets. Recall that, mathematically, a graph is a collection of objects (nodes) and connections between them (edges); a weighted graph additionally assigns numerical values (weights) to the edges. Graphs are represented by their adjacency whose elements are the weights between the nodes. Spectral graph theory uses the eigendecomposition of the adjacency matrix (or, more generally, the Laplacian of the graph) to derive information about the underlying graph. In this paper, we develop a spectral method based on the 'normalized cuts' algorithm to segment hyperspectral image data (HSI). In particular, we model an image as a weighted graph whose nodes are the image pixels, and edges defined as connecting spatial neighbors; the edge weights are given by a weighted combination of the spatial and spectral distances between nodes. We then use the Laplacian of the graph to recursively segment the image. The advantages of our approach are that, first, the graph structure naturally incorporates both the spatial and spectral information present in HSI; also, by using only spatial neighbors, the adjacency matrix is highly sparse; as a result, it is possible to apply our technique to much larger images than previous techniques. In the paper, we present the details of our algorithm, and include experimental results from a variety of hyperspectral images.

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

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

  2. Competitive exclusion and coexistence of universal grammars.

    PubMed

    Mitchener, W Garrett; Nowak, Martin A

    2003-01-01

    Universal grammar (UG) is a list of innate constraints that specify the set of grammars that can be learned by the child during primary language acquisition. UG of the human brain has been shaped by evolution. Evolution requires variation. Hence, we have to postulate and study variation of UG. We investigate evolutionary dynamics and language acquisition in the context of multiple UGs. We provide examples for competitive exclusion and stable coexistence of different UGs. More specific UGs admit fewer candidate grammars, and less specific UGs admit more candidate grammars. We will analyze conditions for more specific UGs to outcompete less specific UGs and vice versa. An interesting finding is that less specific UGs can resist invasion by more specific UGs if learning is more accurate. In other words, accurate learning stabilizes UGs that admit large numbers of candidate grammars.

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

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

  5. College Handbooks and Early Practical Grammars: A Question of Genre.

    ERIC Educational Resources Information Center

    Sklar, Elizabeth S.

    An examination of the history of the practical grammar, of which the college handbook is the modern reflex, reveals why the grammar handbook is so stubbornly resistant to changes in linguistic theory, usage, or ideology. First, codifying English grammar and producing texts for teaching English grammar to school children during the eighteenth…

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

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

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

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

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

  11. mpiGraph

    2007-05-22

    MpiGraph consists of an MPI application called mpiGraph written in C to measure message bandwidth and an associated crunch_mpiGraph script written in Perl to process the application output into an HTMO report. The mpiGraph application is designed to inspect the health and scalability of a high-performance interconnect while under heavy load. This is useful to detect hardware and software problems in a system, such as slow nodes, links, switches, or contention in switch routing. Itmore » is also useful to characterize how interconnect performance changes with different settings or how one interconnect type compares to another.« less

  12. 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. PMID:26900999

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

  14. Theories of artificial grammar learning.

    PubMed

    Pothos, Emmanuel M

    2007-03-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 with relevant human experimental and neuroscience data. The author concludes that satisfactory understanding of AGL requires (a) an understanding of implicit knowledge as knowledge that is not consciously activated at the time of a cognitive operation; this could be because the corresponding representations are impoverished or they cannot be concurrently supported in working memory with other representations or operations, and (b) adopting a frequency-independent view of rule knowledge and contrasting rule knowledge with specific similarity and associative learning (co-occurrence) knowledge.

  15. Universal Grammar, statistics or both?

    PubMed

    Yang, Charles D

    2004-10-01

    Recent demonstrations of statistical learning in infants have reinvigorated the innateness versus learning debate in language acquisition. This article addresses these issues from both computational and developmental perspectives. First, I argue that statistical learning using transitional probabilities cannot reliably segment words when scaled to a realistic setting (e.g. child-directed English). To be successful, it must be constrained by knowledge of phonological structure. Then, turning to the bona fide theory of innateness--the Principles and Parameters framework--I argue that a full explanation of children's grammar development must abandon the domain-specific learning model of triggering, in favor of probabilistic learning mechanisms that might be domain-general but nevertheless operate in the domain-specific space of syntactic parameters.

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

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

  18. Measuring strategic control in artificial grammar learning.

    PubMed

    Norman, Elisabeth; Price, Mark C; Jones, Emma

    2011-12-01

    In response to concerns with existing procedures for measuring strategic control over implicit knowledge in artificial grammar learning (AGL), we introduce a more stringent measurement procedure. After two separate training blocks which each consisted of letter strings derived from a different grammar, participants either judged the grammaticality of novel letter strings with respect to only one of these two grammars (pure-block condition), or had the target grammar varying randomly from trial to trial (novel mixed-block condition) which required a higher degree of conscious flexible control. Random variation in the colour and font of letters was introduced to disguise the nature of the rule and reduce explicit learning. Strategic control was observed both in the pure-block and mixed-block conditions, and even among participants who did not realise the rule was based on letter identity. This indicated detailed strategic control in the absence of explicit learning.

  19. Grammar-guided writing for AAC users.

    PubMed

    Hunnicutt, Sheri; Magnuson, Tina

    2007-01-01

    A method of grammar-guided writing has been devised to guide graphic sign users through the construction of text messages for use in e-mail and other applications with a remote receiver. The purpose is to promote morphologically and syntactically correct sentences. The available grammatical structures in grammar-guided writing are the highest frequency phrase and sentence types in a database of tagged and parsed e-mail messages. A companion learning path allows users to begin with simple grammatical structures, advancing in steps to more complex structures as their language skills develop. In order to give further support during e-mail composition, grammar-guided writing has been augmented with two complementary text input methods. One is a quick and easy method of choosing preprogrammed messages and e-mail phrases. The other is a more traditional method of selecting graphic signs freely without grammar guidance.

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

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

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

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

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

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

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

  7. Equitable random graphs

    NASA Astrophysics Data System (ADS)

    Newman, M. E. J.; Martin, Travis

    2014-11-01

    Random graph models have played a dominant role in the theoretical study of networked systems. The Poisson random graph of Erdős and Rényi, in particular, as well as the so-called configuration model, have served as the starting point for numerous calculations. In this paper we describe another large class of random graph models, which we call equitable random graphs and which are flexible enough to represent networks with diverse degree distributions and many nontrivial types of structure, including community structure, bipartite structure, degree correlations, stratification, and others, yet are exactly solvable for a wide range of properties in the limit of large graph size, including percolation properties, complete spectral density, and the behavior of homogeneous dynamical systems, such as coupled oscillators or epidemic models.

  8. Grammar Instruction for Writing Skills: Do Students Perceive Grammar as Useful?

    ERIC Educational Resources Information Center

    Manley, Joan M.; Calk, Linda

    1997-01-01

    Examines second language students' perceptions of grammar instruction, with specific reference to writing skill. Discusses issues involved in defining a role for grammar study and presents excerpts from student essays and explanations of classroom lessons. Results indicate that the instruction provided helped to improve students' ability to use…

  9. Overcoming the Grammar Deficit: The Role of Information Technology in Teaching German Grammar to Undergraduates.

    ERIC Educational Resources Information Center

    Hall, Christopher

    1998-01-01

    Examines how application of computer-assisted language learning (CALL) and information technology can be used to overcome "grammar deficit" seen in many British undergraduate German students. A combination of explicit, implicit, and exploratory grammar teaching approaches uses diverse resources, including word processing packages, electronic…

  10. Syntactic Functions in Functional Discourse Grammar and Role and Reference Grammar: An Evaluative Comparison

    ERIC Educational Resources Information Center

    Butler, Christopher S.

    2012-01-01

    The aim of this paper is to compare the treatment of syntactic functions, and more particularly those traditionally labelled as Subject and Object, in Functional Discourse Grammar and Role and Reference Grammar. Relevant aspects of the overall structure of the two theories are briefly described. The concept of alignment between levels of the…

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

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

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

  14. Reaction spreading on graphs

    NASA Astrophysics Data System (ADS)

    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 ds, the important quantity for reaction spreading is found to be the connectivity dimension dl. Numerical data, in agreement with analytical estimates based on the features of n independent random walkers on the graph, show that M(t)˜tdl. 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, where is the average degree of the graph.

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

  16. A study on vague graphs.

    PubMed

    Rashmanlou, Hossein; Samanta, Sovan; Pal, Madhumangal; Borzooei, R A

    2016-01-01

    The main purpose of this paper is to introduce the notion of vague h-morphism on vague graphs and regular vague graphs. The action of vague h-morphism on vague strong regular graphs are studied. Some elegant results on weak and co weak isomorphism are derived. Also, [Formula: see text]-complement of highly irregular vague graphs are defined. PMID:27536517

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

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

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

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

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

  2. Grammar in Teacher Education: The Role of a Corpus.

    ERIC Educational Resources Information Center

    Hunston, Susan

    1995-01-01

    Argues for the use of computer-stored corpora in courses in grammar awareness for teachers of mother-tongue English. It is suggested that the ability to do grammar entails a set of skills rather than a body of knowledge and that corpora provide excellent data for doing grammar. Questions regarding the comparison of different methodologies are…

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

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

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

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

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

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

  9. From Sentence to Discourse: Discourse Grammar and English Language Teaching.

    ERIC Educational Resources Information Center

    McCarthy, Michael; Hughes, Rebecca

    1998-01-01

    Argues that there are very good reasons for developing discourse grammars for second-language (L2) teaching. Exemplifies the criteria for moving from sentence-based grammar to the discourse level. The criteria are based on pedagogical and descriptive problems in grammar that sentence-based approaches cannot adequately deal with. (Author/VWL)

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

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

  12. Ways of Knowing: Writing with Grammar in Mind

    ERIC Educational Resources Information Center

    Myhill, Debra

    2005-01-01

    In the international context of concerns about standards in writing, this article addresses the role of grammar in the teaching of writing. It considers both current and historical perspectives on the teaching of grammar and offers a critique of research which attempts to determine the impact of grammar teaching on writing, but which does not…

  13. When Is a Verb? Using Functional Grammar to Teach Writing

    ERIC Educational Resources Information Center

    Fearn, Leif; Farnan, Nancy

    2007-01-01

    While evidence shows that grammar study focused on identification, description, and definition (IDD) fails to enhance writing performance, the grammar most students study remains focused on the IDD tradition. We taught a functional grammar that featured what words do in sentences, rather than what words are called and how they are defined, to two…

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

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

  16. Parallel Communicating Grammar Systems with Regular Control

    NASA Astrophysics Data System (ADS)

    Pardubská, Dana; Plátek, Martin; Otto, Friedrich

    Parallel communicating grammar systems with regular control (RPCGS, for short) are introduced, which are obtained from returning regular parallel communicating grammar systems by restricting the derivations that are executed in parallel by the various components through a regular control language. For the class of languages that are generated by RPCGSs with constant communication complexity we derive a characterization in terms of a restricted type of freely rewriting restarting automaton. From this characterization we obtain that these languages are semi-linear, and that centralized RPCGSs with constant communication complexity are of the same generative power as non-centralized RPCGSs with constant communication complexity.

  17. LL Leftmost k-Linear Scattered Context Grammars

    NASA Astrophysics Data System (ADS)

    Meduna, Alexander; Vrábel, Lukáš; Zemek, Petr

    2011-09-01

    The present paper introduces a new variant of a scattered context grammar, called an LL leftmost k-linear scattered context grammar. It is an ordinary scattered context grammar without erasing rules, where (1) every scattered context rule is composed of k-linear rules, (2) if we take the first components of every rule, the resulting context-free grammar is an LL grammar, and (3) every rule is applied in a leftmost way. We study the generative power of this variant and its parsing properties, including time and space complexity. In the conclusion, several remarks regarding the achieved results are made.

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

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

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

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

  2. Abstraction processes in artificial grammar learning.

    PubMed

    Shanks, D R; Johnstone, T; Staggs, L

    1997-02-01

    Four experiments explored the extent the extent to which abstract knowledge may underlie subjects' performance when asked to judge the grammaticality of letter strings generated from an artificial grammar. In Experiment 1 and 2 subjects studied grammatical strings instantiated with one set of letters and were then tested on grammatical and ungrammatical strings formed either from the same or a changed letter-set. Even with a change of letter-set, subjects were found to be sensitive to a variety of violation of the grammar. In Experiments 3 and 4, the critical manipulation involved the way in which the training strings were studied: an incidental learning procedure was used for some subjects, and others engaged in an explicit code-breaking task to try to learn the rules of the grammar. When strings were generated from a biconditional (Experiment 4) but not from a standard finite-state grammar (Experiment 3), grammaticality judgements for test strings were independent of their surface similarity to specific studied strings. Overall, the results suggest that transfer in this simple memory task is mediated at least to some extent by abstract knowledge.

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

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

  5. Standard Albanian. A Reference Grammar for Students.

    ERIC Educational Resources Information Center

    Newmark, Leonard; And Others

    This book is intended as a reference grammar for English-speaking students of present-day Albanian. The introductory chapter provides information on the country and its people, the Albanian language and dialects, phonology, and morphology. The other chapters contain grammatical explanations in English and examples. (AMH)

  6. Grammar and the English National Curriculum

    ERIC Educational Resources Information Center

    Paterson, Laura Louise

    2010-01-01

    In 1998 the regulatory body for the National Curriculum, the Qualifications and Curriculum Authority, acknowledged that there was "widespread uncertainty" over the grammar requirements of the English Curriculum. In this paper I argue that the QCA still has not addressed this uncertainty. I analyse the 1999 and 2011 Primary English Curricula,…

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

  8. A Traditionalist Looks at Generative Grammar.

    ERIC Educational Resources Information Center

    Long, Ralph B.

    1964-01-01

    Strengths and weaknesses of generative grammar are examined by an apologist for the traditionalists. Criticism is directed toward difficulties encountered by the layman in comprehending texts on linguistic theories, linguists' use of jargon and pet formulas, and unwieldy amounts of terminology constantly being developed. Special attention is…

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

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

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

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

  13. Caught'Ya! Grammar with a Giggle.

    ERIC Educational Resources Information Center

    Kiester, Jane Bell

    Helping students in grades 3 through 11 to master the mechanics of language, this book describes the "Caught'ya" approach to teaching grammar, in which students correct error-filled sentences that form an ongoing humorous plot. The book notes that the sentences are presented 3 to 5 times a week at the start of class and take less than 10 minutes…

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

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

  16. Towards Teaching a "Grammar of Culture."

    ERIC Educational Resources Information Center

    Marsh, David

    It is proposed that for second language learners to develop communicative competence, their instruction must address the sociolinguistic, discourse, and strategic aspects of target language use. These three aspects of communicative competence are termed the "grammar of culture," and they are essential to understanding what is appropriate in…

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

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

  19. Robustness of random graphs based on graph spectra

    NASA Astrophysics Data System (ADS)

    Wu, Jun; Barahona, Mauricio; Tan, Yue-jin; Deng, Hong-zhong

    2012-12-01

    It has been recently proposed that the robustness of complex networks can be efficiently characterized through the natural connectivity, a spectral property of the graph which corresponds to the average Estrada index. The natural connectivity corresponds to an average eigenvalue calculated from the graph spectrum and can also be interpreted as the Helmholtz free energy of the network. In this article, we explore the use of this index to characterize the robustness of Erdős-Rényi (ER) random graphs, random regular graphs, and regular ring lattices. We show both analytically and numerically that the natural connectivity of ER random graphs increases linearly with the average degree. It is also shown that ER random graphs are more robust than the corresponding random regular graphs with the same number of vertices and edges. However, the relative robustness of ER random graphs and regular ring lattices depends on the average degree and graph size: there is a critical graph size above which regular ring lattices are more robust than random graphs. We use our analytical results to derive this critical graph size as a function of the average degree.

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

  1. Corona graphs as a model of small-world networks

    NASA Astrophysics Data System (ADS)

    Lv, Qian; Yi, Yuhao; Zhang, Zhongzhi

    2015-11-01

    We introduce recursive corona graphs as a model of small-world networks. We investigate analytically the critical characteristics of the model, including order and size, degree distribution, average path length, clustering coefficient, and the number of spanning trees, as well as Kirchhoff index. Furthermore, we study the spectra for the adjacency matrix and the Laplacian matrix for the model. We obtain explicit results for all the quantities of the recursive corona graphs, which are similar to those observed in real-life networks.

  2. Graph for locked rotor current

    NASA Technical Reports Server (NTRS)

    Peck, R. R.

    1972-01-01

    Graph determines effect of stalled motor on a distribution system and eliminates hand calculation of amperage in emergencies. Graph is useful to any manufacturer, contractor, or maintenance department involved in electrical technology.

  3. GraphLib

    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

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

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

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

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

  8. Physics on Graphs

    NASA Astrophysics Data System (ADS)

    Schrader, Robert

    This is an extended version of the talk given at the Nato Advanced Research Workshop: New Challenges in Complex System Physics, May 20-24, 2013 in Samarkand (Uzbekistan). We report on results on three topics in joint work with V. Kostrykin (Mainz, Germany) and J. Potthoff (Mannheim, Germany): Propagation of waves on graphs,

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

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

  11. New Conic Graph Paper

    ERIC Educational Resources Information Center

    Rose, Kenneth

    1974-01-01

    Two new types of graph paper are described; focus-focus conic paper and focus-directrix paper. Both types make it easier to draw families of conics. Suggestions for further work are given as is a method for establishing a connection with other ways of looking at the conic sections. (LS)

  12. The Role of Grammar Teaching in Writing in Second Language Acquisition

    ERIC Educational Resources Information Center

    Lin, Li-Li

    2008-01-01

    "Grammar is the sound, structure, and meaning system of language. All languages have grammar, and each language has its own grammar" (Beverly, 2007, p.1). People who speak the same language are able to communicate with each other because they all know the grammar system and structure of that language, that is, the meaningful rules of grammar.…

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

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

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

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

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

  18. Editing graphs for maximum effect

    SciTech Connect

    Murphy, P.W.; Rhiner, R.W.

    1991-01-08

    The paper contains over eighty rules for editing graphs, arranged under nine major headings in a logical sequence for editing all the graphs in a manuscript. It is excerpted from a monograph used at the Lawrence Livermore National Laboratory to train beginning technical editors in editing graphs; a corresponding Hypercard stack is also used in this training. 6 refs., 4 figs.

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

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

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

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

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

  4. Random graph states, maximal flow and Fuss-Catalan distributions

    NASA Astrophysics Data System (ADS)

    Collins, Benoît; Nechita, Ion; Życzkowski, Karol

    2010-07-01

    For any graph consisting of k vertices and m edges we construct an ensemble of random pure quantum states which describe a system composed of 2m subsystems. Each edge of the graph represents a bipartite, maximally entangled state. Each vertex represents a random unitary matrix generated according to the Haar measure, which describes the coupling between subsystems. Dividing all subsystems into two parts, one may study entanglement with respect to this partition. A general technique to derive an expression for the average entanglement entropy of random pure states associated with a given graph is presented. Our technique relies on Weingarten calculus and flow problems. We analyze the statistical properties of spectra of such random density matrices and show for which cases they are described by the free Poissonian (Marchenko-Pastur) distribution. We derive a discrete family of generalized, Fuss-Catalan distributions and explicitly construct graphs which lead to ensembles of random states characterized by these novel distributions of eigenvalues.

  5. xREI: a phylo-grammar visualization webserver.

    PubMed

    Barquist, Lars; Holmes, Ian

    2008-07-01

    Phylo-grammars, probabilistic models combining Markov chain substitution models with stochastic grammars, are powerful models for annotating structured features in multiple sequence alignments and analyzing the evolution of those features. In the past, these methods have been cumbersome to implement and modify. xrate provides means for the rapid development of phylo-grammars (using a simple file format) and automated parameterization of those grammars from training data (via the Expectation Maximization algorithm). xREI (pron. 'X-ray') is an intuitive, flexible AJAX (Asynchronous Javascript And XML) web interface to xrate providing grammar visualization tools as well as access to xrate's training and annotation functionality. It is hoped that this application will serve as a valuable tool to those developing phylo-grammars, and as a means for the exploration and dissemination of such models. xREI is available at http://harmony.biowiki.org/xrei/

  6. Spectral theory and spectral gaps for periodic Schrödinger operators on product graphs

    NASA Astrophysics Data System (ADS)

    Carlson, Robert

    2004-01-01

    Floquet theory and its applications to spectral theory are developed for periodic Schrödinger operators on product graphs {\\mathbb {G}} \\times {\\mathbb {Z}} , where {\\mathbb {G}} is a finite graph. The resolvent and the spectrum have detailed descriptions which involve the eigenvalues and singularities of the meromorphic Floquet matrix function. Existence and size estimates for sequences of spectral gaps are established.

  7. Visual feature learning in artificial grammar classification.

    PubMed

    Chang, Grace Y; Knowlton, Barbara J

    2004-05-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 visual features of the exemplars. When a change in the font and case occurred between study and test, there was no effect on sensitivity to grammatical rules in classification judgments. However, such a change did virtually eliminate sensitivity to training frequencies of letter bigrams and trigrams (chunk strength) in classification judgments. Performance of a secondary task during study eliminated this font sensitivity and generally reduced the contribution of chunk strength knowledge. The results are consistent with the idea that perceptual fluency makes a contribution to artificial grammar judgments.

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

  9. Astronomy at Torquay Boys' Grammar School

    NASA Astrophysics Data System (ADS)

    Reid, David; Lintott, Chris

    1996-10-01

    TBGS Observatory is owned and run by Torquay Boys' Grammar School in South Devon. The school itself encompasses a wide curriculum from sports to academic studies, ranging from the arts to humanities and science. Due to a high interest from pupils and staff the school has a special focus upon Astronomy. Resulting from this TBGS owns one of the largest, best equipped school observatories in the UK. It is now a minor centre for research and studies at GCSE and higher levels.

  10. A graph theoretical approach to states and unitary operations

    NASA Astrophysics Data System (ADS)

    Dutta, Supriyo; Adhikari, Bibhas; Banerjee, Subhashish

    2016-05-01

    Building upon our previous work, on graphical representation of a quantum state by signless Laplacian matrix, we pose the following question. If a local unitary operation is applied to a quantum state, represented by a signless Laplacian matrix, what would be the corresponding graph and how does one implement local unitary transformations graphically? We answer this question by developing the notion of local unitary equivalent graphs. We illustrate our method by a few, well known, local unitary transformations implemented by single-qubit Pauli and Hadamard gates. We also show how graph switching can be used to implement the action of the C_NOT gate, resulting in a graphical description of Bell state generation.

  11. Extensible User-Based XML Grammar Matching

    NASA Astrophysics Data System (ADS)

    Tekli, Joe; Chbeir, Richard; Yetongnon, Kokou

    XML grammar matching has found considerable interest recently due to the growing number of heterogeneous XML documents on the web and the increasing need to integrate, and consequently search and retrieve XML data originated from different data sources. In this paper, we provide an approach for automatic XML grammar matching and comparison aiming to minimize the amount of user effort required to perform the match task. We propose an open framework based on the concept of tree edit distance, integrating different matching criterions so as to capture XML grammar element semantic and syntactic similarities, cardinality and alternativeness constraints, as well as data-type correspondences and relative ordering. It is flexible, enabling the user to chose mapping cardinality (1:1, 1:n, n:1, n:n), in comparison with existing static methods (constrained to 1:1), and considers user feedback to adjust matching results to the user's perception of correct matches. Conducted experiments demonstrate the efficiency of our approach, in comparison with alternative methods.

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

    SciTech Connect

    Hong, Seokyong; 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.

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

  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. The construction of semantic memory: grammar-based representations learned from relational episodic information.

    PubMed

    Battaglia, Francesco P; Pennartz, Cyriel M A

    2011-01-01

    After acquisition, memories underlie a process of consolidation, making them more resistant to interference and brain injury. Memory consolidation involves systems-level interactions, most importantly between the hippocampus and associated structures, which takes part in the initial encoding of memory, and the neocortex, which supports long-term storage. This dichotomy parallels the contrast between episodic memory (tied to the hippocampal formation), collecting an autobiographical stream of experiences, and semantic memory, a repertoire of facts and statistical regularities about the world, involving the neocortex at large. Experimental evidence points to a gradual transformation of memories, following encoding, from an episodic to a semantic character. This may require an exchange of information between different memory modules during inactive periods. We propose a theory for such interactions and for the formation of semantic memory, in which episodic memory is encoded as relational data. Semantic memory is modeled as a modified stochastic grammar, which learns to parse episodic configurations expressed as an association matrix. The grammar produces tree-like representations of episodes, describing the relationships between its main constituents at multiple levels of categorization, based on its current knowledge of world regularities. These regularities are learned by the grammar from episodic memory information, through an expectation-maximization procedure, analogous to the inside-outside algorithm for stochastic context-free grammars. We propose that a Monte-Carlo sampling version of this algorithm can be mapped on the dynamics of "sleep replay" of previously acquired information in the hippocampus and neocortex. We propose that the model can reproduce several properties of semantic memory such as decontextualization, top-down processing, and creation of schemata.

  16. The Construction of Semantic Memory: Grammar-Based Representations Learned from Relational Episodic Information

    PubMed Central

    Battaglia, Francesco P.; Pennartz, Cyriel M. A.

    2011-01-01

    After acquisition, memories underlie a process of consolidation, making them more resistant to interference and brain injury. Memory consolidation involves systems-level interactions, most importantly between the hippocampus and associated structures, which takes part in the initial encoding of memory, and the neocortex, which supports long-term storage. This dichotomy parallels the contrast between episodic memory (tied to the hippocampal formation), collecting an autobiographical stream of experiences, and semantic memory, a repertoire of facts and statistical regularities about the world, involving the neocortex at large. Experimental evidence points to a gradual transformation of memories, following encoding, from an episodic to a semantic character. This may require an exchange of information between different memory modules during inactive periods. We propose a theory for such interactions and for the formation of semantic memory, in which episodic memory is encoded as relational data. Semantic memory is modeled as a modified stochastic grammar, which learns to parse episodic configurations expressed as an association matrix. The grammar produces tree-like representations of episodes, describing the relationships between its main constituents at multiple levels of categorization, based on its current knowledge of world regularities. These regularities are learned by the grammar from episodic memory information, through an expectation-maximization procedure, analogous to the inside–outside algorithm for stochastic context-free grammars. We propose that a Monte-Carlo sampling version of this algorithm can be mapped on the dynamics of “sleep replay” of previously acquired information in the hippocampus and neocortex. We propose that the model can reproduce several properties of semantic memory such as decontextualization, top-down processing, and creation of schemata. PMID:21887143

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

  18. Dynamic Systems Theory and Universal Grammar: Holding up a Turbulent Mirror to Development in Grammars

    ERIC Educational Resources Information Center

    Plaza-Pust, Carolina

    2008-01-01

    Research over the last decades has shown that language development in its multiple forms is characterized by a succession of stable and unstable states. However, the variation observed is neither expected nor can it be accounted for on the basis of traditional learning concepts conceived of within the Universal Grammar (UG) paradigm. In this…

  19. The Multiple Grammars Theory and the Nature of L2 Grammars

    ERIC Educational Resources Information Center

    Liceras, Juana M.

    2014-01-01

    This article offers the author's commentary on the Multiple Grammar (MG) language acquisition theory proposed by Luiz Amaral and Tom Roeper in the present issue and touches on other second language acquisition research. Topics discussed include the concept of second language (L2) optionality, a hypothesis regarding the acquisition of the…

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

    PubMed Central

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

  1. 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. PMID:26479495

  2. Effect of Direct Grammar Instruction on Student Writing Skills

    ERIC Educational Resources Information Center

    Robinson, Lisa; Feng, Jay

    2016-01-01

    Grammar Instruction has an important role to play in helping students to speak and write more effectively. The purpose of this study was to examine the effects of direct grammar instruction on the quality of student's writing skills. The participants in this study included 18 fifth grade students and two fifth grade teachers. Based on the results…

  3. Assessing Grammar Teaching Methods Using a Metacognitive Framework.

    ERIC Educational Resources Information Center

    Burkhalter, Nancy

    A study examined 3 grammar teaching methods to understand why some methods may carry over into writing better than others. E. Bialystok and E. B. Ryan's (1985) metacognitive model of language skills was adapted to plot traditional grammar, sentence combining, and the functional/inductive approach according to the amount of analyzed knowledge and…

  4. Can Students Apply Grammar Rules for Reading Textbook Explanations?

    ERIC Educational Resources Information Center

    Scott, Virginia M.; Randall, Sarah A.

    1992-01-01

    Given the lack of guidance for teachers regarding the role of explicit grammar instruction in the proficiency-oriented classroom, an experiment investigated how well students are able to read, learn, and use targeted grammar structures on their own. Results suggest they can learn certain kinds of linguistic structures anonymously, but others…

  5. Understanding the Role of Grammar in Proficiency-Oriented Instruction.

    ERIC Educational Resources Information Center

    Ruiz-Funes, Marcela

    The role of grammar instruction in proficiency-oriented second language instruction (POI) is examined, drawing on research and theory on second language use and instruction. Several premises are stated: (1) formal grammar has an important role in POI, while focus on form and communicative practice should be maintained; (2) in POI, a syllabus that…

  6. Issues in the Teaching of Grammar in a Foreign Language.

    ERIC Educational Resources Information Center

    Weatherford, H. Jarold

    A number of issues in classroom second language instruction, particularly as they relate to grammar instruction, are considered in the context of recent research and theory. Discussion begins with a review of the nature and role of second language grammar instruction. Following this, these issues are explored: whether the native or target language…

  7. The Case against Grammar Correction in L2 Writing Classes.

    ERIC Educational Resources Information Center

    Truscott, John

    1996-01-01

    Argues that grammar correction in second-language writing classes should be abandoned because it is ineffective, harmful, and unhelpful in any interesting sense for theoretical and practical reasons. The article also considers and rejects a number of arguments previously offered in favor of grammar correction. (122 references) (Author/CK)

  8. ncRNA consensus secondary structure derivation using grammar strings.

    PubMed

    Achawanantakun, Rujira; Sun, Yanni; Takyar, Seyedeh Shohreh

    2011-04-01

    Many noncoding RNAs (ncRNAs) function through both their sequences and secondary structures. Thus, secondary structure derivation is an important issue in today's RNA research. The state-of-the-art structure annotation tools are based on comparative analysis, which derives consensus structure of homologous ncRNAs. Despite promising results from existing ncRNA aligning and consensus structure derivation tools, there is a need for more efficient and accurate ncRNA secondary structure modeling and alignment methods. In this work, we introduce a consensus structure derivation approach based on grammar string, a novel ncRNA secondary structure representation that encodes an ncRNA's sequence and secondary structure in the parameter space of a context-free grammar (CFG) and a full RNA grammar including pseudoknots. Being a string defined on a special alphabet constructed from a grammar, grammar string converts ncRNA alignment into sequence alignment. We derive consensus secondary structures from hundreds of ncRNA families from BraliBase 2.1 and 25 families containing pseudoknots using grammar string alignment. Our experiments have shown that grammar string-based structure derivation competes favorably in consensus structure quality with Murlet and RNASampler. Source code and experimental data are available at http://www.cse.msu.edu/~yannisun/grammar-string. PMID:21523935

  9. Concept-Based Grammar Teaching: An Academic Responds to Azar

    ERIC Educational Resources Information Center

    Hill, Kent

    2007-01-01

    This response to Azar (this volume) intends to discuss from an academic's perspective the main points raised in her paper (i.e., grammar-based instruction and its relation to focus on form and error correction) and, to encourage a more concept-based approach to grammar instruction (CBT). A CBT approach to language development argues that the…

  10. Where Is She? Gender Occurrences in Online Grammar Guides

    ERIC Educational Resources Information Center

    Amare, Nicole

    2007-01-01

    This article examines seven online grammar guides for instances of linguistic sexism. The grammar sentences from .edu Websites were analyzed based on NCTE's "Guidelines for Gender-Fair Use of Language" (2002) using the criteria of generic he and man; titles, labels, and names; gender stereotypes; order of mention (firstness); and ratio of male to…

  11. A Grammar of Northern Mao (Mawes Aas'e)

    ERIC Educational Resources Information Center

    Ahland, Michael Bryan

    2012-01-01

    Northern Mao is an endangered Afroasiatic-Omotic language of western Ethiopia with fewer than 5,000 speakers. This study is a comprehensive grammar of the language, written from a functional/typological perspective which embraces historical change as an explanation for synchronic structure. The grammar introduces the Northern Mao people, aspects…

  12. The Constituent Ordering Process in Functional Discourse Grammar

    ERIC Educational Resources Information Center

    Connolly, John H.

    2012-01-01

    An essential task for the morphosyntactic level within the grammatical component of Functional Discourse Grammar (FDG) is the handling of constituent ordering. This area of grammar, which is known as positional syntax, constitutes the subject of the present paper, in which the ordering of constituents is examined within the framework of a dynamic…

  13. Rules of the Game: Grammar through Discovery 1.

    ERIC Educational Resources Information Center

    Page, Mary; And Others

    Designed to encourage students to discover that grammar merely represents the patterns that exist in language, this book presents lessons on 19 grammar points: nouns; pronouns; verbs; subjects; capitalization; end punctuation; commas; sentence fragments; run-on sentences; contractions; possessives; quotation marks; adjectives; adverbs;…

  14. Towards More Context and Discourse in Grammar Instruction

    ERIC Educational Resources Information Center

    Celce-Murcia, Marianne

    2007-01-01

    This paper first discusses why the sentence-level drills still being used extensively in the teaching of grammar to second language learners have not been successful. What follows is a presentation of an innovative approach; namely, using context and discourse to present and practice grammar in more authentic and effective ways.

  15. The Effects of Using Online Concordancers on Teaching Grammar

    ERIC Educational Resources Information Center

    Türkmen, Yasemin; Aydin, Selami

    2016-01-01

    Studies conducted so far have mainly focused on the effects of online concordancers on teaching vocabulary, while there is a lack of research focusing on the effects of online concordancers on teaching and learning grammar. Thus, this study aims to review the studies on the effects of online concordancers on teaching and learning grammar and how…

  16. ncRNA consensus secondary structure derivation using grammar strings.

    PubMed

    Achawanantakun, Rujira; Sun, Yanni; Takyar, Seyedeh Shohreh

    2011-04-01

    Many noncoding RNAs (ncRNAs) function through both their sequences and secondary structures. Thus, secondary structure derivation is an important issue in today's RNA research. The state-of-the-art structure annotation tools are based on comparative analysis, which derives consensus structure of homologous ncRNAs. Despite promising results from existing ncRNA aligning and consensus structure derivation tools, there is a need for more efficient and accurate ncRNA secondary structure modeling and alignment methods. In this work, we introduce a consensus structure derivation approach based on grammar string, a novel ncRNA secondary structure representation that encodes an ncRNA's sequence and secondary structure in the parameter space of a context-free grammar (CFG) and a full RNA grammar including pseudoknots. Being a string defined on a special alphabet constructed from a grammar, grammar string converts ncRNA alignment into sequence alignment. We derive consensus secondary structures from hundreds of ncRNA families from BraliBase 2.1 and 25 families containing pseudoknots using grammar string alignment. Our experiments have shown that grammar string-based structure derivation competes favorably in consensus structure quality with Murlet and RNASampler. Source code and experimental data are available at http://www.cse.msu.edu/~yannisun/grammar-string.

  17. Spoken Grammar: An Urgent Necessity in the EFL Context

    ERIC Educational Resources Information Center

    Al-wossabi, Sami A.

    2014-01-01

    Recent studies in corpus linguistics have revealed apparent inconsistencies between the prescriptive grammar presented in EFL textbooks and the type of grammar used in the speech of native speakers. Such variations and learning gaps deprive EFL learners of the actual use of English and delay their oral/aural developmental processes. The focus of…

  18. Yemeni Teachers' Beliefs of Grammar Teaching and Classroom Practices

    ERIC Educational Resources Information Center

    Ezzi, Nemah Abdullah Ayash

    2012-01-01

    Beliefs of in-service English teachers about grammar learning/teaching and the influence of such beliefs on their classroom practices remain relatively unexplored. More precisely, this study explores English teachers' beliefs about grammar learning and teaching. It throws light on the teachers' actual practices in the classrooms of 7th -12th…

  19. Environmental Peace Education in Foreign Language Learners' English Grammar Lessons

    ERIC Educational Resources Information Center

    Arikan, Arda

    2009-01-01

    English language teachers create contexts to teach grammar so that meaningful learning occurs. In this study, English grammar is contextualized through environmental peace education activities to raise students' awareness of global issues. Two sources provided data to evaluate the success of this instructional process. Fourth-year pre-service…

  20. Functional Grammar and Its Implications for English Teaching and Learning

    ERIC Educational Resources Information Center

    Feng, Zhiwen

    2013-01-01

    Functional grammar has received more and more attention from domestic scholars in the world of linguistics since 1970s, but it is still new to most EFL teachers. In spite of controversies about its applications into classroom teaching, this new grammar model has its own advantages and can facilitate EFL students to achieve academic success. This…

  1. Investigating Effects of Computer-Based Grammar Tutorials

    ERIC Educational Resources Information Center

    Kolesnikova, Anna

    2011-01-01

    This dissertation study examined a broad question of whether computer-based grammar tutorials are effective and welcome tools to review grammar for language learners by investigating effects of three different modes of such tutorials on learners' knowledge and satisfaction. For this study, I developed experimental tutorials in three different…

  2. Effect of Jigsaw I Technique on Teaching Turkish Grammar

    ERIC Educational Resources Information Center

    Arslan, Akif

    2016-01-01

    The purpose of this study is to find out the effect of Jigsaw I technique on students' academic success and attitude towards the course in teaching Turkish grammar. For that purpose, three grammar topics (spelling and punctuation marks rules) were determined and an experimental study conforming to "control group preliminary-testing final…

  3. Current Issues in the Teaching of Grammar: An SLA Perspective

    ERIC Educational Resources Information Center

    Ellis, Rod

    2006-01-01

    The study of how learners acquire a second language (SLA) has helped to shape thinking about how to teach the grammar of a second language. There remain, however, a number of controversial issues. This paper considers eight key questions relating to grammar pedagogy in the light of findings from SLA. As such, this article complements…

  4. Grammar for College Writing: A Sentence-Composing Approach

    ERIC Educational Resources Information Center

    Killgallon, Don; Killgallon, Jenny

    2010-01-01

    Across America, in thousands of classrooms, from elementary school to high school, the time-tested sentence-composing approach has given students tools to become better writers. Now the authors present a much anticipated sentence-composing grammar worktext for college writing. This book presents a new and easier way to understand grammar: (1) Noun…

  5. Towards a Rationale for Research into Grammar Teaching in Schools

    ERIC Educational Resources Information Center

    Fontich, Xavier; Camps, Anna

    2014-01-01

    This article hopes to bring new insights to the debate about the effect of grammar knowledge on language use, especially writing. It raises the question of the need to look more closely at the following three questions: (1) What is the aim of grammar teaching?; (2) How capable are students of conceptualising about language and how is their…

  6. The Grammar of Action and Reversal Errors in Children's Printing.

    ERIC Educational Resources Information Center

    Simner, Marvin L.

    1984-01-01

    Studies predictions about letter reversals made by Goodnow's "grammar of action." Two samples of right- and left-handed children in nursery school through first grade printed from memory immediately after exposure to each of 41 reversible letters and numbers. Results challenge "grammar of action" proposals about the inappropriate applications of…

  7. SPECIFICATION AND UTILIZATION OF A TRANSFORMATIONAL GRAMMAR. FINAL REPORT.

    ERIC Educational Resources Information Center

    BLAIR, FRED; ROSENBAUM, PETER S.

    RESEARCH IN THREE AREAS OF COMPUTATIONAL LINGUISTICS IS DESCRIBED--(1) THE DESIGN AND DEVELOPMENT OF A TRANSFORMATIONAL GRAMMAR FOR A SUBSET TO GRAMMATICAL SENTENCES IN ENGLISH, (2) THE IMPLEMENTATION OF THIS GRAMMAR IN TERMS OF A SENTENCE SYNTHESIZING PROGRAM WRITTEN IN LISP 1.5, AND (3) THE USE OF SENTENCE SYNTHESIZING PROGRAMS FOR…

  8. On the Equivalence of Formal Grammars and Machines.

    ERIC Educational Resources Information Center

    Lund, Bruce

    1991-01-01

    Explores concepts of formal language and automata theory underlying computational linguistics. A computational formalism is described known as a "logic grammar," with which computational systems process linguistic data, with examples in declarative and procedural semantics and definite clause grammars. (13 references) (CB)

  9. Detecting alternative graph clusterings.

    PubMed

    Mandala, Supreet; Kumara, Soundar; Yao, Tao

    2012-07-01

    The problem of graph clustering or community detection has enjoyed a lot of attention in complex networks literature. A quality function, modularity, quantifies the strength of clustering and on maximization yields sensible partitions. However, in most real world networks, there are an exponentially large number of near-optimal partitions with some being very different from each other. Therefore, picking an optimal clustering among the alternatives does not provide complete information about network topology. To tackle this problem, we propose a graph perturbation scheme which can be used to identify an ensemble of near-optimal and diverse clusterings. We establish analytical properties of modularity function under the perturbation which ensures diversity. Our approach is algorithm independent and therefore can leverage any of the existing modularity maximizing algorithms. We numerically show that our methodology can systematically identify very different partitions on several existing data sets. The knowledge of diverse partitions sheds more light into the topological organization and helps gain a more complete understanding of the underlying complex network.

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

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

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

  13. [The genetic language: grammar, semantics, evolution].

    PubMed

    Ratner, V A

    1993-05-01

    The genetic language is a collection of rules and regularities of genetic information coding for genetic texts. It is defined by alphabet, grammar, collection of punctuation marks and regulatory sites, semantics. There is a review of these general attributes of genetic language, including also the problems of synonymy and evolution. The main directions of theoretical investigations of genetic language and neighbouring questions are formulated: (1) cryptographic problems, (2) analysis of genetic texts, (3) theoretical-linguistic problems, (4) evolutionary linguistic questions. The problem of genetic language becomes one of the key ones of molecular genetics, molecular biology and gene engineering.

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

  15. Graph theory - recent developments of its application in geomorphology

    NASA Astrophysics Data System (ADS)

    Heckmann, Tobias; Schwanghart, Wolfgang; Pillips, Jonathan

    2014-05-01

    Graph theory has been widely applied across a range of disciplines as different as population and landscape ecology, sociology, economic and transportation geography, informatics and climatology - yet these disciplines have in common that they deal with systems consisting of multiple subsystems or compartments that are coupled by relations. Although geomorphic systems lend themselves to network representations (see e.g. Chorley and Kennedy's systems approach to physical geography, 1971), the application of the conceptional and methodological toolbox of graph theory has been quite rare and restricted. In the 1960ies, graph theory was used to study the topology of river networks; since the 1970ies, studies in geomorphometry have employed it to model the topological structure of topographic surfaces. The recent re-discovery and development of graph theory applications in geomorphology run on two lines. (a) The spatially explicit analysis of sediment cascades in geomorphic systems where nodes represent their compartments (depending on the spatial scale of the study the latter can be single landforms or larger terrain subunits up to whole catchments), and edges represent the linkage of system components through water or sediment flux. This approach is closely related to the analysis of hydrological and/or sediment connectivity. (b) The analysis of geomorphic systems whose properties are represented by graph nodes, and the relations between them by graph edges. Graph theoretical measures, derived e.g. by eigenvalue analysis of the adjacency matrix, have been shown to reflect system properties such as synchronization and scale relations. Our contribution reports on these recent developments. We present case studies and discuss future applications in geomorphology that could benefit from graph theory.

  16. Thermodynamic characterization of networks using graph polynomials

    NASA Astrophysics Data System (ADS)

    Ye, Cheng; Comin, César H.; Peron, Thomas K. DM.; Silva, Filipi N.; Rodrigues, Francisco A.; Costa, Luciano da F.; Torsello, Andrea; Hancock, Edwin R.

    2015-09-01

    In this paper, we present a method for characterizing the evolution of time-varying complex networks by adopting a thermodynamic representation of network structure computed from a polynomial (or algebraic) characterization of graph structure. Commencing from a representation of graph structure based on a characteristic polynomial computed from the normalized Laplacian matrix, we show how the polynomial is linked to the Boltzmann partition function of a network. This allows us to compute a number of thermodynamic quantities for the network, including the average energy and entropy. Assuming that the system does not change volume, we can also compute the temperature, defined as the rate of change of entropy with energy. All three thermodynamic variables can be approximated using low-order Taylor series that can be computed using the traces of powers of the Laplacian matrix, avoiding explicit computation of the normalized Laplacian spectrum. These polynomial approximations allow a smoothed representation of the evolution of networks to be constructed in the thermodynamic space spanned by entropy, energy, and temperature. We show how these thermodynamic variables can be computed in terms of simple network characteristics, e.g., the total number of nodes and node degree statistics for nodes connected by edges. We apply the resulting thermodynamic characterization to real-world time-varying networks representing complex systems in the financial and biological domains. The study demonstrates that the method provides an efficient tool for detecting abrupt changes and characterizing different stages in network evolution.

  17. An Exploration of the Relationship between Vietnamese Students' Knowledge of L1 Grammar and Their English Grammar Proficiency

    ERIC Educational Resources Information Center

    Tran, Tammie M.

    2010-01-01

    The problem. This research study explores an important issue in the field of TESOL (Teaching English to Speakers of Other Languages) and second language acquisition (SLA). Its purpose is to examine the relationship between Vietnamese students' L1 grammar knowledge and their English grammar proficiency. Furthermore, it investigates the extent to…

  18. Making Grammar Instruction More Empowering: An Exploratory Case Study of Corpus Use in the Learning/Teaching of Grammar

    ERIC Educational Resources Information Center

    Liu, Dilin

    2011-01-01

    Despite a long debate and the accompanying call for changes in the past few decades, grammar instruction in college English classes, according to some scholars, has remained largely "disempowering,""decontextualized," and "remedial" (Micciche, 2004, p. 718). To search for more effective and empowering grammar teaching, this study explores the use…

  19. Grammar for Writing? An Investigation of the Effects of Contextualised Grammar Teaching on Students' Writing

    ERIC Educational Resources Information Center

    Jones, Susan; Myhill, Debra; Bailey, Trevor

    2013-01-01

    The role of grammar instruction in the teaching of writing is contested in most Anglophone countries, with several robust meta-analyses finding no evidence of any beneficial effect. However, existing research is limited in that it only considers isolated grammar instruction and offers no theorisation of an instructional relationship between…

  20. Grammar, Writing, and Technology: A Sample Technology-Supported Approach to Teaching Grammar and Improving Writing for ESL Learners

    ERIC Educational Resources Information Center

    Hegelheimer, Volker; Fisher, David

    2006-01-01

    English language learners are frequently unable to benefit from the prevailing process-writing approaches due to a lack of grammar and vocabulary knowledge relevant to academic writing. This paper describes how the need for explicit grammar instruction as part of preparing students to write can be addressed by using a collection of learner texts…

  1. Graphs and Zero-Divisors

    ERIC Educational Resources Information Center

    Axtell, M.; Stickles, J.

    2010-01-01

    The last ten years have seen an explosion of research in the zero-divisor graphs of commutative rings--by professional mathematicians "and" undergraduates. The objective is to find algebraic information within the geometry of these graphs. This topic is approachable by anyone with one or two semesters of abstract algebra. This article gives the…

  2. A PVS Graph Theory Library

    NASA Technical Reports Server (NTRS)

    Butler, Ricky W.; Sjogren, Jon A.

    1998-01-01

    This paper documents the NASA Langley PVS graph theory library. The library provides fundamental definitions for graphs, subgraphs, walks, paths, subgraphs generated by walks, trees, cycles, degree, separating sets, and four notions of connectedness. Theorems provided include Ramsey's and Menger's and the equivalence of all four notions of connectedness.

  3. Graphs as Statements of Belief.

    ERIC Educational Resources Information Center

    Lake, David

    2002-01-01

    Identifies points where beliefs are important when making decisions about how graphs are drawn. Describes a simple case of the reaction between 'bicarb soda' and orange or lemon juice and discusses how drawing a graph becomes a statement of belief. (KHR)

  4. Weighted graph based ordering techniques for preconditioned conjugate gradient methods

    NASA Technical Reports Server (NTRS)

    Clift, Simon S.; Tang, Wei-Pai

    1994-01-01

    We describe the basis of a matrix ordering heuristic for improving the incomplete factorization used in preconditioned conjugate gradient techniques applied to anisotropic PDE's. Several new matrix ordering techniques, derived from well-known algorithms in combinatorial graph theory, which attempt to implement this heuristic, are described. These ordering techniques are tested against a number of matrices arising from linear anisotropic PDE's, and compared with other matrix ordering techniques. A variation of RCM is shown to generally improve the quality of incomplete factorization preconditioners.

  5. Understanding the Complex Processes in Developing Student Teachers' Knowledge about Grammar

    ERIC Educational Resources Information Center

    Svalberg, Agneta M.-L.

    2015-01-01

    This article takes the view that grammar is driven by user choices and is therefore complex and dynamic. This has implications for the teaching of grammar in language teacher education and how teachers' cognitions about grammar, and hence their own grammar teaching, might change. In this small, interpretative study, the participants--students on…

  6. The Effects of Communicative Grammar Teaching on Students' Achievement of Grammatical Knowledge and Oral Production

    ERIC Educational Resources Information Center

    Ho, Pham Vu Phi; The Binh, Nguyen

    2014-01-01

    So far the students of Le Hong Phong Junior High School have been taught grammar with GTM (Grammar-Translation Method), which just prepares learners for conventional grammar-paper tests. Despite their considerable knowledge of grammar, the students fail to use the language they have learnt to communicate in real-life situations. The purpose of…

  7. The Effectiveness of Teaching Traditional Grammar on Writing Composition at the High School Level

    ERIC Educational Resources Information Center

    Jaeger, Gina

    2011-01-01

    Traditional grammar instruction is a challenging element of the English curriculum; both students and teachers struggle with the rules and dull nature of grammar. However, understanding grammar is important because students need to understand the language they speak in order to be effective communicators, and teachers provide grammar instruction…

  8. A Collection of Features for Semantic Graphs

    SciTech Connect

    Eliassi-Rad, T; Fodor, I K; Gallagher, B

    2007-05-02

    Semantic graphs are commonly used to represent data from one or more data sources. Such graphs extend traditional graphs by imposing types on both nodes and links. This type information defines permissible links among specified nodes and can be represented as a graph commonly referred to as an ontology or schema graph. Figure 1 depicts an ontology graph for data from National Association of Securities Dealers. Each node type and link type may also have a list of attributes. To capture the increased complexity of semantic graphs, concepts derived for standard graphs have to be extended. This document explains briefly features commonly used to characterize graphs, and their extensions to semantic graphs. This document is divided into two sections. Section 2 contains the feature descriptions for static graphs. Section 3 extends the features for semantic graphs that vary over time.

  9. Graph Partitioning and Sequencing Software

    1995-09-19

    Graph partitioning is a fundemental problem in many scientific contexts. CHACO2.0 is a software package designed to partition and sequence graphs. CHACO2.0 allows for recursive application of several methods for finding small edge separators in weighted graphs. These methods include inertial, spectral, Kernighan Lin and multilevel methods in addition to several simpler strategies. Each of these approaches can be used to partition the graph into two, four, or eight pieces at each level of recursion.more » In addition, the Kernighan Lin method can be used to improve partitions generated by any of the other algorithms. CHACO2.0 can also be used to address various graph sequencing problems, with applications to scientific computing, database design, gene sequencing and other problems.« less

  10. Semi-Markov Graph Dynamics

    PubMed Central

    Raberto, Marco; Rapallo, Fabio; Scalas, Enrico

    2011-01-01

    In this paper, we outline a model of graph (or network) dynamics based on two ingredients. The first ingredient is a Markov chain on the space of possible graphs. The second ingredient is a semi-Markov counting process of renewal type. The model consists in subordinating the Markov chain to the semi-Markov counting process. In simple words, this means that the chain transitions occur at random time instants called epochs. The model is quite rich and its possible connections with algebraic geometry are briefly discussed. Moreover, for the sake of simplicity, we focus on the space of undirected graphs with a fixed number of nodes. However, in an example, we present an interbank market model where it is meaningful to use directed graphs or even weighted graphs. PMID:21887245

  11. Path similarity skeleton graph matching.

    PubMed

    Bai, Xiang; Latecki, Longin Jan

    2008-07-01

    This paper presents a novel framework to for shape recognition based on object silhouettes. The main idea is to match skeleton graphs by comparing the shortest paths between skeleton endpoints. In contrast to typical tree or graph matching methods, we completely ignore the topological graph structure. Our approach is motivated by the fact that visually similar skeleton graphs may have completely different topological structures. The proposed comparison of shortest paths between endpoints of skeleton graphs yields correct matching results in such cases. The skeletons are pruned by contour partitioning with Discrete Curve Evolution, which implies that the endpoints of skeleton branches correspond to visual parts of the objects. The experimental results demonstrate that our method is able to produce correct results in the presence of articulations, stretching, and occlusion.

  12. Style grammars for interactive visualization of architecture.

    PubMed

    Aliaga, Daniel G; Rosen, Paul A; Bekins, Daniel R

    2007-01-01

    Interactive visualization of architecture provides a way to quickly visualize existing or novel buildings and structures. Such applications require both fast rendering and an effortless input regimen for creating and changing architecture using high-level editing operations that automatically fill in the necessary details. Procedural modeling and synthesis is a powerful paradigm that yields high data amplification and can be coupled with fast-rendering techniques to quickly generate plausible details of a scene without much or any user interaction. Previously, forward generating procedural methods have been proposed where a procedure is explicitly created to generate particular content. In this paper, we present our work in inverse procedural modeling of buildings and describe how to use an extracted repertoire of building grammars to facilitate the visualization and quick modification of architectural structures and buildings. We demonstrate an interactive application where the user draws simple building blocks and, using our system, can automatically complete the building "in the style of" other buildings using view-dependent texture mapping or nonphotorealistic rendering techniques. Our system supports an arbitrary number of building grammars created from user subdivided building models and captured photographs. Using only edit, copy, and paste metaphors, the entire building styles can be altered and transferred from one building to another in a few operations, enhancing the ability to modify an existing architectural structure or to visualize a novel building in the style of the others.

  13. Visual Matrix Clustering of Social Networks

    SciTech Connect

    Wong, Pak C.; Mackey, Patrick S.; Foote, Harlan P.; May, Richard A.

    2013-07-01

    The prevailing choices to graphically represent a social network in today’s literature are a node-link graph layout and an adjacency matrix. Both visualization techniques have unique strengths and weaknesses when applied to different domain applications. In this article, we focus our discussion on adjacency matrix and how to turn the matrix-based visualization technique from merely showing pairwise associations among network actors (or graph nodes) to depicting clusters of a social network. We also use node-link layouts to supplement the discussion.

  14. A New Graph-Based Molecular Descriptor Using the Canonical Representation of the Molecule

    PubMed Central

    Hentabli, Hamza; Abdo, Ammar; Salim, Naomie

    2014-01-01

    Molecular similarity is a pervasive concept in drug design. The basic idea underlying molecular similarity is the similar property principle, which states that structurally similar molecules will exhibit similar physicochemical and biological properties. In this paper, a new graph-based molecular descriptor (GBMD) is introduced. The GBMD is a new method of obtaining a rough description of 2D molecular structure in textual form based on the canonical representations of the molecule outline shape and it allows rigorous structure specification using small and natural grammars. Simulated virtual screening experiments with the MDDR database show clearly the superiority of the graph-based descriptor compared to many standard descriptors (ALOGP, MACCS, EPFP4, CDKFP, PCFP, and SMILE) using the Tanimoto coefficient (TAN) and the basic local alignment search tool (BLAST) when searches were carried. PMID:25140330

  15. A new graph-based molecular descriptor using the canonical representation of the molecule.

    PubMed

    Hentabli, Hamza; Saeed, Faisal; Abdo, Ammar; Salim, Naomie

    2014-01-01

    Molecular similarity is a pervasive concept in drug design. The basic idea underlying molecular similarity is the similar property principle, which states that structurally similar molecules will exhibit similar physicochemical and biological properties. In this paper, a new graph-based molecular descriptor (GBMD) is introduced. The GBMD is a new method of obtaining a rough description of 2D molecular structure in textual form based on the canonical representations of the molecule outline shape and it allows rigorous structure specification using small and natural grammars. Simulated virtual screening experiments with the MDDR database show clearly the superiority of the graph-based descriptor compared to many standard descriptors (ALOGP, MACCS, EPFP4, CDKFP, PCFP, and SMILE) using the Tanimoto coefficient (TAN) and the basic local alignment search tool (BLAST) when searches were carried. PMID:25140330

  16. Role Discovery in Graphs

    SciTech Connect

    2014-08-14

    RolX takes the features from Re-FeX or any other feature matrix as input and outputs role assignments (clusters). The output of RolX is a csv file containing the node-role memberships and a csv file containing the role-feature definitions.

  17. NEWCAT: Parsing natural language using left-associative grammar

    SciTech Connect

    Hausser, R.

    1986-01-01

    This book shows that constituent structure analysis induces an irregular order of linear composition which is the direct cause of extreme computational inefficiency. It proposes an alternative left-associative grammar which operates with a regular order of linear compositions. Left-associative grammar is based on building up and cancelling valencies. Left-associative parsers differ from all other systems in that the history of the parse doubles as the linguistic analysis. Left-associative grammar is illustrated with two left-associative natural language parsers: one for German and one for English.

  18. Two-Dimensional Grammars And Their Applications To Artificial Intelligence

    NASA Astrophysics Data System (ADS)

    Lee, Edward T.

    1987-05-01

    During the past several years, the concepts and techniques of two-dimensional grammars1,2 have attracted growing attention as promising avenues of approach to problems in picture generation as well as in picture description3 representation, recognition, transformation and manipulation. Two-dimensional grammar techniques serve the purpose of exploiting the structure or underlying relationships in a picture. This approach attempts to describe a complex picture in terms of their components and their relative positions. This resembles the way a sentence is described in terms of its words and phrases, and the terms structural picture recognition, linguistic picture recognition, or syntactic picture recognition are often used. By using this approach, the problem of picture recognition becomes similar to that of phrase recognition in a language. However, describing pictures using a string grammar (one-dimensional grammar), the only relation between sub-pictures and/or primitives is the concatenation; that is each picture or primitive can be connected only at the left or right. This one-dimensional relation has not been very effective in describing two-dimensional pictures. A natural generaliza-tion is to use two-dimensional grammars. In this paper, two-dimensional grammars and their applications to artificial intelligence are presented. Picture grammars and two-dimensional grammars are introduced and illustrated by examples. In particular, two-dimensional grammars for generating all possible squares and all possible rhombuses are presented. The applications of two-dimensional grammars to solving region filling problems are discussed. An algorithm for region filling using two-dimensional grammars is presented together with illustrative examples. The advantages of using this algorithm in terms of computation time are also stated. A high-level description of a two-level picture generation system is proposed. The first level is the picture primitive generation using two

  19. Multigraph: Reusable Interactive Data Graphs

    NASA Astrophysics Data System (ADS)

    Phillips, M. B.

    2010-12-01

    There are surprisingly few good software tools available for presenting time series data on the internet. The most common practice is to use a desktop program such as Excel or Matlab to save a graph as an image which can be included in a web page like any other image. This disconnects the graph from the data in a way that makes updating a graph with new data a cumbersome manual process, and it limits the user to one particular view of the data. The Multigraph project defines an XML format for describing interactive data graphs, and software tools for creating and rendering those graphs in web pages and other internet connected applications. Viewing a Multigraph graph is extremely simple and intuitive, and requires no instructions; the user can pan and zoom by clicking and dragging, in a familiar "Google Maps" kind of way. Creating a new graph for inclusion in a web page involves writing a simple XML configuration file. Multigraph can read data in a variety of formats, and can display data from a web service, allowing users to "surf" through large data sets, downloading only those the parts of the data that are needed for display. The Multigraph XML format, or "MUGL" for short, provides a concise description of the visual properties of a graph, such as axes, plot styles, data sources, labels, etc, as well as interactivity properties such as how and whether the user can pan or zoom along each axis. Multigraph reads a file in this format, draws the described graph, and allows the user to interact with it. Multigraph software currently includes a Flash application for embedding graphs in web pages, a Flex component for embedding graphs in larger Flex/Flash applications, and a plugin for creating graphs in the WordPress content management system. Plans for the future include a Java version for desktop viewing and editing, a command line version for batch and server side rendering, and possibly Android and iPhone versions. Multigraph is currently in use on several web

  20. TAGMEMIC AND MATRIX LINGUISTICS APPLIED TO SELECTED AFRICAN LANGUAGES. FINAL REPORT.

    ERIC Educational Resources Information Center

    PIKE, KENNETH L.

    THE APPLICATION OF TAGMEMIC AND MATRIX TECHNIQUES TO SOME PROBLEMS IN AFRICAN DESCRIPTIVE LINGUISTICS, AND THE ILLUSTRATION OF THIS APPLICATION WITH DATA SOURCES (RESTATED IN TAGMEMIC TERMS) WERE PRESENTED. (TAGMEMIC AND MATRIX TECHNIQUES REFER, RESPECTIVELY, TO THE STUDY OF (1) ONE-WORD OR MULTIWORD GRAMMAR UNITS AND THE FUNCTIONS OF THESE UNITS…

  1. Network Models in Class C on Arbitrary Graphs

    NASA Astrophysics Data System (ADS)

    Cardy, John

    2005-08-01

    We consider network models of quantum localisation in which a particle with a two-component wave function propagates through the nodes and along the edges of an arbitrary directed graph, subject to a random SU(2) rotation on each edge it traverses. The propagation through each node is specified by an arbitrary but fixed S-matrix. Such networks model localisation problems in class C of the classification of Altland and Zirnbauer [1], and, on suitable graphs, they model the spin quantum Hall transition. We extend the analyses of Gruzberg, Ludwig and Read [5] and of Beamond, Cardy and Chalker [2] to show that, on an arbitrary graph, the mean density of states and the mean conductance may be calculated in terms of observables of a classical history-dependent random walk on the same graph. The transition weights for this process are explicitly related to the elements of the S-matrices. They are correctly normalised but, on graphs with nodes of degree greater than 4, not necessarily non-negative (and therefore interpretable as probabilities) unless a sufficient number of them happen to vanish. Our methods use a supersymmetric path integral formulation of the problem which is completely finite and rigorous.

  2. Green's function approach for quantum graphs: An overview

    NASA Astrophysics Data System (ADS)

    Andrade, Fabiano M.; Schmidt, A. G. M.; Vicentini, E.; Cheng, B. K.; da Luz, M. G. E.

    2016-08-01

    Here we review the many aspects and distinct phenomena associated to quantum dynamics on general graph structures. For so, we discuss such class of systems under the energy domain Green's function (G) framework. This approach is particularly interesting because G can be written as a sum over classical-like paths, where local quantum effects are taken into account through the scattering matrix elements (basically, transmission and reflection amplitudes) defined on each one of the graph vertices. Hence, the exact G has the functional form of a generalized semiclassical formula, which through different calculation techniques (addressed in detail here) always can be cast into a closed analytic expression. It allows to solve exactly arbitrary large (although finite) graphs in a recursive and fast way. Using the Green's function method, we survey many properties of open and closed quantum graphs as scattering solutions for the former and eigenspectrum and eigenstates for the latter, also considering quasi-bound states. Concrete examples, like cube, binary trees and Sierpiński-like topologies are presented. Along the work, possible distinct applications using the Green's function methods for quantum graphs are outlined.

  3. Similarity and confidence in artificial grammar learning.

    PubMed

    Tunney, Richard J

    2010-01-01

    Three experiments examined the relationship between similarity ratings and confidence ratings in artificial grammar learning. In Experiment 1 participants rated the similarity of test items to study exemplars. Regression analyses revealed these to be related to some of the objective measures of similarity that have previously been implicated in categorization decisions. In Experiment 2 participants made grammaticality decisions and rated either their confidence in the accuracy of their decisions or the similarity of the test items to the study items. Regression analyses showed that the grammaticality decisions were predicted by the similarity ratings obtained in Experiment 1. Points on the receiver operating characteristics (ROC) curves for the similarity and confidence ratings were closely matched. These data suggest that meta-cognitive judgments of confidence are predicated on structural knowledge of similarity. Experiment 3 confirmed this by showing that confidence ratings to median similarity probe items changed according to the similarity of preceding items.

  4. Syntactic transfer in artificial grammar learning.

    PubMed

    Beesley, T; Wills, A J; Le Pelley, M E

    2010-02-01

    In an artificial grammar learning (AGL) experiment, participants were trained with instances of one grammatical structure before completing a test phase in which they were required to discriminate grammatical from randomly created strings. Importantly, the underlying structure used to generate test strings was different from that used to generate the training strings. Despite the fact that grammatical training strings were more similar to nongrammatical test strings than they were to grammatical test strings, this manipulation resulted in a positive transfer effect, as compared with controls trained with nongrammatical strings. It is suggested that training with grammatical strings leads to an appreciation of set variance that aids the detection of grammatical test strings in AGL tasks. The analysis presented demonstrates that it is useful to conceptualize test performance in AGL as a form of unsupervised category learning.

  5. Genetic algorithms based on genetic grammar

    NASA Astrophysics Data System (ADS)

    Hofestaedt, Ralf; Mueller, Hermann

    1992-08-01

    The cell represents the basic unit of life. It can be interpreted as a chemical machine which can solve special problems. The present knowledge we have of molecular biology allows the characterization of the metabolism as a processing method. This method is an evolutionary product which has been developed over millions of years. First we will present the analyzed features of the metabolism. Then we will go on to compare this processing method with methods which are discussed in computer science. The comparison shows that there is no method in the field of computer science which uses all the metabolic features. This is the reason why we formalize the metabolic processing method. In this paper we choose to use a grammatical formalism. A genetic grammar is the basis of the metabolic system which represents the metabolic processing method. The basic unit of this system (logic unit) will be shown. This allows the discussion of the complexity of realizing the metabolic system in hardware.

  6. Picture grammars in classification and semantic interpretation of 3D coronary vessels visualisations

    NASA Astrophysics Data System (ADS)

    Ogiela, M. R.; Tadeusiewicz, R.; Trzupek, M.

    2009-09-01

    The work presents the new opportunity for making semantic descriptions and analysis of medical structures, especially coronary vessels CT spatial reconstructions, with the use of AI graph-based linguistic formalisms. In the paper there will be discussed the manners of applying methods of computational intelligence to the development of a syntactic semantic description of spatial visualisations of the heart's coronary vessels. Such descriptions may be used for both smart ordering of images while archiving them and for their semantic searches in medical multimedia databases. Presented methodology of analysis can furthermore be used for attaining other goals related performance of computer-assisted semantic interpretation of selected elements and/or the entire 3D structure of the coronary vascular tree. These goals are achieved through the use of graph-based image formalisms based on IE graphs generating grammars that allow discovering and automatic semantic interpretation of irregularities visualised on the images obtained during diagnostic examinations of the heart muscle. The basis for the construction of 3D reconstructions of biological objects used in this work are visualisations obtained from helical CT scans, yet the method itself may be applied also for other methods of medical 3D images acquisition. The obtained semantic information makes it possible to make a description of the structure focused on the semantics of various morphological forms of the visualised vessels from the point of view of the operation of coronary circulation and the blood supply of the heart muscle. Thanks to these, the analysis conducted allows fast and — to a great degree — automated interpretation of the semantics of various morphological changes in the coronary vascular tree, and especially makes it possible to detect these stenoses in the lumen of the vessels that can cause critical decrease in blood supply to extensive or especially important fragments of the heart muscle.

  7. Graph anomalies in cyber communications

    SciTech Connect

    Vander Wiel, Scott A; Storlie, Curtis B; Sandine, Gary; Hagberg, Aric A; Fisk, Michael

    2011-01-11

    Enterprises monitor cyber traffic for viruses, intruders and stolen information. Detection methods look for known signatures of malicious traffic or search for anomalies with respect to a nominal reference model. Traditional anomaly detection focuses on aggregate traffic at central nodes or on user-level monitoring. More recently, however, traffic is being viewed more holistically as a dynamic communication graph. Attention to the graph nature of the traffic has expanded the types of anomalies that are being sought. We give an overview of several cyber data streams collected at Los Alamos National Laboratory and discuss current work in modeling the graph dynamics of traffic over the network. We consider global properties and local properties within the communication graph. A method for monitoring relative entropy on multiple correlated properties is discussed in detail.

  8. Constructing Dense Graphs with Unique Hamiltonian Cycles

    ERIC Educational Resources Information Center

    Lynch, Mark A. M.

    2012-01-01

    It is not difficult to construct dense graphs containing Hamiltonian cycles, but it is difficult to generate dense graphs that are guaranteed to contain a unique Hamiltonian cycle. This article presents an algorithm for generating arbitrarily large simple graphs containing "unique" Hamiltonian cycles. These graphs can be turned into dense graphs…

  9. Information theory and artificial grammar learning: inferring grammaticality from redundancy.

    PubMed

    Jamieson, Randall K; Nevzorova, Uliana; Lee, Graham; Mewhort, D J K

    2016-03-01

    In artificial grammar learning experiments, participants study strings of letters constructed using a grammar and then sort novel grammatical test exemplars from novel ungrammatical ones. The ability to distinguish grammatical from ungrammatical strings is often taken as evidence that the participants have induced the rules of the grammar. We show that judgements of grammaticality are predicted by the local redundancy of the test strings, not by grammaticality itself. The prediction holds in a transfer test in which test strings involve different letters than the training strings. Local redundancy is usually confounded with grammaticality in stimuli widely used in the literature. The confounding explains why the ability to distinguish grammatical from ungrammatical strings has popularized the idea that participants have induced the rules of the grammar, when they have not. We discuss the judgement of grammaticality task in terms of attribute substitution and pattern goodness. When asked to judge grammaticality (an inaccessible attribute), participants answer an easier question about pattern goodness (an accessible attribute).

  10. Yamabe type equations on graphs

    NASA Astrophysics Data System (ADS)

    Grigor'yan, Alexander; Lin, Yong; Yang, Yunyan

    2016-11-01

    Let G = (V , E) be a locally finite graph, Ω ⊂ V be a bounded domain, Δ be the usual graph Laplacian, and λ1 (Ω) be the first eigenvalue of -Δ with respect to Dirichlet boundary condition. Using the mountain pass theorem due to Ambrosetti-Rabinowitz, we prove that if α <λ1 (Ω), then for any p > 2, there exists a positive solution to

  11. Graph signatures for visual analytics.

    PubMed

    Wong, Pak Chung; Foote, Harlan; Chin, George; Mackey, Patrick; Perrine, Ken

    2006-01-01

    We present a visual analytics technique to explore graphs using the concept of a data signature. A data signature, in our context, is a multidimensional vector that captures the local topology information surrounding each graph node. Signature vectors extracted from a graph are projected onto a low-dimensional scatterplot through the use of scaling. The resultant scatterplot, which reflects the similarities of the vectors, allows analysts to examine the graph structures and their corresponding real-life interpretations through repeated use of brushing and linking between the two visualizations. The interpretation of the graph structures is based on the outcomes of multiple participatory analysis sessions with intelligence analysts conducted by the authors at the Pacific Northwest National Laboratory. The paper first uses three public domain data sets with either well-known or obvious features to explain the rationale of our design and illustrate its results. More advanced examples are then used in a customized usability study to evaluate the effectiveness and efficiency of our approach. The study results reveal not only the limitations and weaknesses of the traditional approach based solely on graph visualization, but also the advantages and strengths of our signature-guided approach presented in the paper.

  12. Inference process of programmed attributed regular grammars for character recognition

    NASA Astrophysics Data System (ADS)

    Prundaru, Mihail; Prundaru, Ioana

    2000-12-01

    The paper presents the grammar inference engine of a pattern recognition system for character recognition. The input characters are identified, thinned to a one pixel width pattern and a feature-based description is provided. Using the syntactic recognition paradigm, the features are the set of terminals (or terminal symbols) for the application. The feature-based description includes a set of three attributes (i.e. A, B, C) for each feature. The combined feature and attribute description for each input pattern preserves in a more accurate way the structure of the original pattern. The grammar inference engine uses the feature-based description of each input pattern from the training set to build a grammar for each class of patterns. For each input pattern from the training set, the productions (rewriting rules) are derived together with all the necessary elements such as: the nonterminals, branch and testing conditions. Since the grammars are regular, the process of deriving the production rules is simple. All the productions are collected together providing the tags to be consecutive, without gaps. The size of the class grammars is reduced at an acceptable level for further processing using a set of Evans heuristic rules. These algorithms identifies the redundant productions, eliminating those productions and the correspondent nonterminal symbols. The stop criteria for the Evans thinning algorithm makes sure that no further reductions are possible. The last step of the grammar inference process enables the grammar to identify class members which were not in the training set: a cycling production rule. The above built grammars are used by the syntactic (character) classifier to identify the input patterns as being members of a-priori known classes.

  13. Khovanov homology of graph-links

    SciTech Connect

    Nikonov, Igor M

    2012-08-31

    Graph-links arise as the intersection graphs of turning chord diagrams of links. Speaking informally, graph-links provide a combinatorial description of links up to mutations. Many link invariants can be reformulated in the language of graph-links. Khovanov homology, a well-known and useful knot invariant, is defined for graph-links in this paper (in the case of the ground field of characteristic two). Bibliography: 14 titles.

  14. Private Graphs - Access Rights on Graphs for Seamless Navigation

    NASA Astrophysics Data System (ADS)

    Dorner, W.; Hau, F.; Pagany, R.

    2016-06-01

    After the success of GNSS (Global Navigational Satellite Systems) and navigation services for public streets, indoor seems to be the next big development in navigational services, relying on RTLS - Real Time Locating Services (e.g. WIFI) and allowing seamless navigation. In contrast to navigation and routing services on public streets, seamless navigation will cause an additional challenge: how to make routing data accessible to defined users or restrict access rights for defined areas or only to parts of the graph to a defined user group? The paper will present case studies and data from literature, where seamless and especially indoor navigation solutions are presented (hospitals, industrial complexes, building sites), but the problem of restricted access rights was only touched from a real world, but not a technical perspective. The analysis of case studies will show, that the objective of navigation and the different target groups for navigation solutions will demand well defined access rights and require solutions, how to make only parts of a graph to a user or application available to solve a navigational task. The paper will therefore introduce the concept of private graphs, which is defined as a graph for navigational purposes covering the street, road or floor network of an area behind a public street and suggest different approaches how to make graph data for navigational purposes available considering access rights and data protection, privacy and security issues as well.

  15. Subvoxel accurate graph search using non-Euclidean graph space.

    PubMed

    Abràmoff, Michael D; Wu, Xiaodong; Lee, Kyungmoo; Tang, Li

    2014-01-01

    Graph search is attractive for the quantitative analysis of volumetric medical images, and especially for layered tissues, because it allows globally optimal solutions in low-order polynomial time. However, because nodes of graphs typically encode evenly distributed voxels of the volume with arcs connecting orthogonally sampled voxels in Euclidean space, segmentation cannot achieve greater precision than a single unit, i.e. the distance between two adjoining nodes, and partial volume effects are ignored. We generalize the graph to non-Euclidean space by allowing non-equidistant spacing between nodes, so that subvoxel accurate segmentation is achievable. Because the number of nodes and edges in the graph remains the same, running time and memory use are similar, while all the advantages of graph search, including global optimality and computational efficiency, are retained. A deformation field calculated from the volume data adaptively changes regional node density so that node density varies with the inverse of the expected cost. We validated our approach using optical coherence tomography (OCT) images of the retina and 3-D MR of the arterial wall, and achieved statistically significant increased accuracy. Our approach allows improved accuracy in volume data acquired with the same hardware, and also, preserved accuracy with lower resolution, more cost-effective, image acquisition equipment. The method is not limited to any specific imaging modality and readily extensible to higher dimensions.

  16. Community detection in graphs using singular value decomposition.

    PubMed

    Sarkar, Somwrita; Dong, Andy

    2011-04-01

    A spectral algorithm for community detection is presented. The algorithm consists of three stages: (1) matrix factorization of two matrix forms, square signless Laplacian for unipartite graphs and rectangular adjacency matrix for bipartite graphs, using singular value decompostion (SVD); (2) dimensionality reduction using an optimal linear approximation; and (3) clustering vertices using dot products in reduced dimensional space. The algorithm reveals communities in graphs without placing any restriction on the input network type or the output community type. It is applicable on unipartite or bipartite unweighted or weighted networks. It places no requirement on strict community membership and automatically reveals the number of clusters, their respective sizes and overlaps, and hierarchical modular organization. By representing vertices as vectors in real space, expressed as linear combinations of the orthogonal bases described by SVD, orthogonality becomes the metric for classifying vertices into communities. Results on several test and real world networks are presented, including cases where a mix of disjointed, overlapping, or hierarchical communities are known to exist in the network. PMID:21599247

  17. The contribution of phonological short-term memory to artificial grammar learning.

    PubMed

    Andrade, Jackie; Baddeley, Alan

    2011-05-01

    Three experiments investigated the contribution of phonological short-term memory (STM) to grammar learning by manipulating rehearsal during study of an auditory artificial grammar made up from a vocabulary of spoken Mandarin syllables. Experiment 1 showed that concurrent, irrelevant articulation impaired grammar learning compared with a nonverbal control task. Experiment 2 replicated and extended this finding, showing that repeating the grammatical strings at study improved grammar learning compared with suppressing rehearsal or remaining silent during learning. Experiment 3 found no effects of rehearsal on grammar learning once participants had learned the component syllables. The findings suggest that phonological STM aids artificial grammar learning via effects on vocabulary learning.

  18. Template construction grammar: from visual scene description to language comprehension and agrammatism.

    PubMed

    Barrès, Victor; Lee, Jinyong

    2014-01-01

    How does the language system coordinate with our visual system to yield flexible integration of linguistic, perceptual, and world-knowledge information when we communicate about the world we perceive? Schema theory is a computational framework that allows the simulation of perceptuo-motor coordination programs on the basis of known brain operating principles such as cooperative computation and distributed processing. We present first its application to a model of language production, SemRep/TCG, which combines a semantic representation of visual scenes (SemRep) with Template Construction Grammar (TCG) as a means to generate verbal descriptions of a scene from its associated SemRep graph. SemRep/TCG combines the neurocomputational framework of schema theory with the representational format of construction grammar in a model linking eye-tracking data to visual scene descriptions. We then offer a conceptual extension of TCG to include language comprehension and address data on the role of both world knowledge and grammatical semantics in the comprehension performances of agrammatic aphasic patients. This extension introduces a distinction between heavy and light semantics. The TCG model of language comprehension offers a computational framework to quantitatively analyze the distributed dynamics of language processes, focusing on the interactions between grammatical, world knowledge, and visual information. In particular, it reveals interesting implications for the understanding of the various patterns of comprehension performances of agrammatic aphasics measured using sentence-picture matching tasks. This new step in the life cycle of the model serves as a basis for exploring the specific challenges that neurolinguistic computational modeling poses to the neuroinformatics community.

  19. Constructing a Nonnegative Low-Rank and Sparse Graph With Data-Adaptive Features.

    PubMed

    Zhuang, Liansheng; Gao, Shenghua; Tang, Jinhui; Wang, Jingjing; Lin, Zhouchen; Ma, Yi; Yu, Nenghai

    2015-11-01

    This paper aims at constructing a good graph to discover the intrinsic data structures under a semisupervised learning setting. First, we propose to build a nonnegative low-rank and sparse (referred to as NNLRS) graph for the given data representation. In particular, the weights of edges in the graph are obtained by seeking a nonnegative low-rank and sparse reconstruction coefficients matrix that represents each data sample as a linear combination of others. The so-obtained NNLRS-graph captures both the global mixture of subspaces structure (by the low-rankness) and the locally linear structure (by the sparseness) of the data, hence it is both generative and discriminative. Second, as good features are extremely important for constructing a good graph, we propose to learn the data embedding matrix and construct the graph simultaneously within one framework, which is termed as NNLRS with embedded features (referred to as NNLRS-EF). Extensive NNLRS experiments on three publicly available data sets demonstrate that the proposed method outperforms the state-of-the-art graph construction method by a large margin for both semisupervised classification and discriminative analysis, which verifies the effectiveness of our proposed method.

  20. Sharing Teaching Ideas: Graphing Families of Curves Using Transformations of Reference Graphs

    ERIC Educational Resources Information Center

    Kukla, David

    2007-01-01

    This article provides for a fast extremely accurate approach to graphing functions that is based on learning function reference graphs and then applying algebraic transformations to these reference graphs.

  1. Box graphs and resolutions I

    NASA Astrophysics Data System (ADS)

    Braun, Andreas P.; Schäfer-Nameki, Sakura

    2016-04-01

    Box graphs succinctly and comprehensively characterize singular fibers of elliptic fibrations in codimension two and three, as well as flop transitions connecting these, in terms of representation theoretic data. We develop a framework that provides a systematic map between a box graph and a crepant algebraic resolution of the singular elliptic fibration, thus allowing an explicit construction of the fibers from a singular Weierstrass or Tate model. The key tool is what we call a fiber face diagram, which shows the relevant information of a (partial) toric triangulation and allows the inclusion of more general algebraic blowups. We shown that each such diagram defines a sequence of weighted algebraic blowups, thus providing a realization of the fiber defined by the box graph in terms of an explicit resolution. We show this correspondence explicitly for the case of SU (5) by providing a map between box graphs and fiber faces, and thereby a sequence of algebraic resolutions of the Tate model, which realizes each of the box graphs.

  2. Sequential visibility-graph motifs

    NASA Astrophysics Data System (ADS)

    Iacovacci, Jacopo; Lacasa, Lucas

    2016-04-01

    Visibility algorithms transform time series into graphs and encode dynamical information in their topology, paving the way for graph-theoretical time series analysis as well as building a bridge between nonlinear dynamics and network science. In this work we introduce and study the concept of sequential visibility-graph motifs, smaller substructures of n consecutive nodes that appear with characteristic frequencies. We develop a theory to compute in an exact way the motif profiles associated with general classes of deterministic and stochastic dynamics. We find that this simple property is indeed a highly informative and computationally efficient feature capable of distinguishing among different dynamics and robust against noise contamination. We finally confirm that it can be used in practice to perform unsupervised learning, by extracting motif profiles from experimental heart-rate series and being able, accordingly, to disentangle meditative from other relaxation states. Applications of this general theory include the automatic classification and description of physical, biological, and financial time series.

  3. Algebraic connectivity and graph robustness.

    SciTech Connect

    Feddema, John Todd; Byrne, Raymond Harry; Abdallah, Chaouki T.

    2009-07-01

    Recent papers have used Fiedler's definition of algebraic connectivity to show that network robustness, as measured by node-connectivity and edge-connectivity, can be increased by increasing the algebraic connectivity of the network. By the definition of algebraic connectivity, the second smallest eigenvalue of the graph Laplacian is a lower bound on the node-connectivity. In this paper we show that for circular random lattice graphs and mesh graphs algebraic connectivity is a conservative lower bound, and that increases in algebraic connectivity actually correspond to a decrease in node-connectivity. This means that the networks are actually less robust with respect to node-connectivity as the algebraic connectivity increases. However, an increase in algebraic connectivity seems to correlate well with a decrease in the characteristic path length of these networks - which would result in quicker communication through the network. Applications of these results are then discussed for perimeter security.

  4. The fragment assembly string graph.

    PubMed

    Myers, Eugene W

    2005-09-01

    We present a concept and formalism, the string graph, which represents all that is inferable about a DNA sequence from a collection of shotgun sequencing reads collected from it. We give time and space efficient algorithms for constructing a string graph given the collection of overlaps between the reads and, in particular, present a novel linear expected time algorithm for transitive reduction in this context. The result demonstrates that the decomposition of reads into kmers employed in the de Bruijn graph approach described earlier is not essential, and exposes its close connection to the unitig approach we developed at Celera. This paper is a preliminary piece giving the basic algorithm and results that demonstrate the efficiency and scalability of the method. These ideas are being used to build a next-generation whole genome assembler called BOA (Berkeley Open Assembler) that will easily scale to mammalian genomes.

  5. Graph Analytics for Signature Discovery

    SciTech Connect

    Hogan, Emilie A.; Johnson, John R.; Halappanavar, Mahantesh; Lo, Chaomei

    2013-06-01

    Within large amounts of seemingly unstructured data it can be diffcult to find signatures of events. In our work we transform unstructured data into a graph representation. By doing this we expose underlying structure in the data and can take advantage of existing graph analytics capabilities, as well as develop new capabilities. Currently we focus on applications in cybersecurity and communication domains. Within cybersecurity we aim to find signatures for perpetrators using the pass-the-hash attack, and in communications we look for emails or phone calls going up or down a chain of command. In both of these areas, and in many others, the signature we look for is a path with certain temporal properties. In this paper we discuss our methodology for finding these temporal paths within large graphs.

  6. Graph modeling systems and methods

    DOEpatents

    Neergaard, Mike

    2015-10-13

    An apparatus and a method for vulnerability and reliability modeling are provided. The method generally includes constructing a graph model of a physical network using a computer, the graph model including a plurality of terminating vertices to represent nodes in the physical network, a plurality of edges to represent transmission paths in the physical network, and a non-terminating vertex to represent a non-nodal vulnerability along a transmission path in the physical network. The method additionally includes evaluating the vulnerability and reliability of the physical network using the constructed graph model, wherein the vulnerability and reliability evaluation includes a determination of whether each terminating and non-terminating vertex represents a critical point of failure. The method can be utilized to evaluate wide variety of networks, including power grid infrastructures, communication network topologies, and fluid distribution systems.

  7. Quantum snake walk on graphs

    SciTech Connect

    Rosmanis, Ansis

    2011-02-15

    I introduce a continuous-time quantum walk on graphs called the quantum snake walk, the basis states of which are fixed-length paths (snakes) in the underlying graph. First, I analyze the quantum snake walk on the line, and I show that, even though most states stay localized throughout the evolution, there are specific states that most likely move on the line as wave packets with momentum inversely proportional to the length of the snake. Next, I discuss how an algorithm based on the quantum snake walk might potentially be able to solve an extended version of the glued trees problem, which asks to find a path connecting both roots of the glued trees graph. To the best of my knowledge, no efficient quantum algorithm solving this problem is known yet.

  8. Midlet Navigation Graphs in JML

    NASA Astrophysics Data System (ADS)

    Mostowski, Wojciech; Poll, Erik

    In the context of the EU project Mobius on Proof Carrying Code for Java programs (midlets) on mobile devices, we present a way to express midlet navigation graphs in JML. Such navigation graphs express certain security policies for a midlet. The resulting JML specifications can be automatically checked with the static checker ESC/Java2. Our work was guided by a realistically sized case study developed as demonstrator in the project. We discuss practical difficulties with creating efficient and meaningful JML specifications for automatic verification with a lightweight verification tool such as ESC/Java2, and the potential use of these specifications for PCC.

  9. Boosting for multi-graph classification.

    PubMed

    Wu, Jia; Pan, Shirui; Zhu, Xingquan; Cai, Zhihua

    2015-03-01

    In this paper, we formulate a novel graph-based learning problem, multi-graph classification (MGC), which aims to learn a classifier from a set of labeled bags each containing a number of graphs inside the bag. A bag is labeled positive, if at least one graph in the bag is positive, and negative otherwise. Such a multi-graph representation can be used for many real-world applications, such as webpage classification, where a webpage can be regarded as a bag with texts and images inside the webpage being represented as graphs. This problem is a generalization of multi-instance learning (MIL) but with vital differences, mainly because instances in MIL share a common feature space whereas no feature is available to represent graphs in a multi-graph bag. To solve the problem, we propose a boosting based multi-graph classification framework (bMGC). Given a set of labeled multi-graph bags, bMGC employs dynamic weight adjustment at both bag- and graph-levels to select one subgraph in each iteration as a weak classifier. In each iteration, bag and graph weights are adjusted such that an incorrectly classified bag will receive a higher weight because its predicted bag label conflicts to the genuine label, whereas an incorrectly classified graph will receive a lower weight value if the graph is in a positive bag (or a higher weight if the graph is in a negative bag). Accordingly, bMGC is able to differentiate graphs in positive and negative bags to derive effective classifiers to form a boosting model for MGC. Experiments and comparisons on real-world multi-graph learning tasks demonstrate the algorithm performance.

  10. Graph run-length matrices for histopathological image segmentation.

    PubMed

    Tosun, Akif Burak; Gunduz-Demir, Cigdem

    2011-03-01

    The histopathological examination of tissue specimens is essential for cancer diagnosis and grading. However, this examination is subject to a considerable amount of observer variability as it mainly relies on visual interpretation of pathologists. To alleviate this problem, it is very important to develop computational quantitative tools, for which image segmentation constitutes the core step. In this paper, we introduce an effective and robust algorithm for the segmentation of histopathological tissue images. This algorithm incorporates the background knowledge of the tissue organization into segmentation. For this purpose, it quantifies spatial relations of cytological tissue components by constructing a graph and uses this graph to define new texture features for image segmentation. This new texture definition makes use of the idea of gray-level run-length matrices. However, it considers the runs of cytological components on a graph to form a matrix, instead of considering the runs of pixel intensities. Working with colon tissue images, our experiments demonstrate that the texture features extracted from "graph run-length matrices" lead to high segmentation accuracies, also providing a reasonable number of segmented regions. Compared with four other segmentation algorithms, the results show that the proposed algorithm is more effective in histopathological image segmentation.

  11. Development and Validation of a Diagnostic Grammar Test for Japanese Learners of English

    ERIC Educational Resources Information Center

    Koizumi, Rie; Sakai, Hideki; Ido, Takahiro; Ota, Hiroshi; Hayama, Megumi; Sato, Masatoshi; Nemoto, Akiko

    2011-01-01

    This article reports on the development and validation of the English Diagnostic Test of Grammar (EDiT Grammar) for Japanese learners of English. From among the many aspects of grammar, this test focuses on the knowledge of basic English noun phrases (NPs), especially their internal structures, because previous research has indicated the…

  12. How Grammars of English Have Missed the Boat: There's Been More Flummoxing Than Meets the Eye.

    ERIC Educational Resources Information Center

    Bailey, Charles-James N.

    The possibility should be considered that English grammar has been misanalyzed for centuries because of grammarians' accepting fundamentally flawed assumptions about grammar and, even more so, about the history of English--and that this has resulted in a huge disconnect between English grammars and the genius of English that really exists. The…

  13. Grammar in the Second Language Classroom: An Ever-Changing Role.

    ERIC Educational Resources Information Center

    Lally, Carolyn

    The history of grammar instruction in second language education is traced, focusing on the evolution of grammar's role from a central place in instruction to its current peripheral, almost problematic role. The objective is to provide background information so that second language educators can redefine grammar's role in language instruction. The…

  14. English Grammar in American Schools before 1850. Bulletin, 1921, No. 12

    ERIC Educational Resources Information Center

    Lyman, Rollo LaVerne

    1922-01-01

    English grammar, as a formal subject, distinct from other branches of instruction in the vernacular, made but sporadic appearances in the American schools before 1775. After the Revolution its rise was extremely rapid. English grammar gained momentum as the hold of Latin grammar weakened, and by the end of the first quarter of the nineteenth…

  15. A SHORT SYNOPSIS OF THE MOST ESSENTIAL POINTS IN HAWAIIAN GRAMMAR.

    ERIC Educational Resources Information Center

    ALEXANDER, W.D.

    THIS IS A REPRINT OF A BOOK PUBLISHED IN 1864. IT IS INTENDED AS A REFERENCE GRAMMAR FOR STUDENTS OF HAWAIIAN AND FOR THOSE INTERESTED IN THE COMPARATIVE GRAMMAR OF THE POLYNESIAN LANGUAGES. IT FOLLOWS THE PATTERN OF THE TRADITIONAL GRAMMARS OF THE TIME, BUT THE AUTHOR WAS AWARE OF THE DANGER OF IMPOSING ON HAWAIIAN THE CATEGORIES OF EUROPEAN…

  16. The Role of Grammar in the Writing Curriculum: A Review of the Literature

    ERIC Educational Resources Information Center

    Myhill, Debra; Watson, Annabel

    2014-01-01

    For most Anglophone countries, the history of grammar teaching over the past 50 years is one of contestation, debate and dissent: and 50 years on we are no closer to reaching a consensus about the role of grammar in the English/Language Arts curriculum. The debate has been described through the metaphor of battle and grammar wars (Kamler, 1995;…

  17. Language Practice with Multimedia Supported Web-Based Grammar Revision Material

    ERIC Educational Resources Information Center

    Baturay, Meltem Huri; Daloglu, Aysegul; Yildirim, Soner

    2010-01-01

    The aim of this study was to investigate the perceptions of elementary-level English language learners towards web-based, multimedia-annotated grammar learning. WEBGRAM, a system designed to provide supplementary web-based grammar revision material, uses audio-visual aids to enrich the contextual presentation of grammar and allows learners to…

  18. Impact of Consciousness-Raising Activities on Young English Language Learners' Grammar Performance

    ERIC Educational Resources Information Center

    Fatemipour, Hamidreza; Hemmati, Shiva

    2015-01-01

    Grammar Consciousness-Raising (GCR) is an approach to teaching of grammar which learners instead of being taught the given rules, experience language data. The data challenge them to rethink, restructure their existing mental grammar and construct an explicit rule to describe the grammatical feature which the data illustrate (Ellis, 2002). And…

  19. The Association between Expressive Grammar Intervention and Social and Emergent Literacy Outcomes for Preschoolers with SLI

    ERIC Educational Resources Information Center

    Washington, Karla N.

    2013-01-01

    Purpose: To determine whether (a) expressive grammar intervention facilitated social and emergent literacy outcomes better than no intervention and (b) expressive grammar gains and/or initial expressive grammar level predicted social and emergent literacy outcomes. Method: This investigation was a follow-up to a recently published study exploring…

  20. New Ways in Teaching Grammar. New Ways in TESOL Series: Innovative Classroom Techniques.

    ERIC Educational Resources Information Center

    Pennington, Martha C., Ed.

    This book includes 85 ideas for the teaching of grammar, contributed by teachers of English as a Second Language from varied countries. The ideas are organized in 10 sections that include specific aspects of grammar and grammar topics at the discourse level. These include: noun phrases and clauses (adjectives and nouns, articles, subject-verb…

  1. Graphs for Early Elementary Social Studies.

    ERIC Educational Resources Information Center

    Freeland, Kent; Brewer, Samrie

    1989-01-01

    Describes a lesson plan that instructs third graders to use graphs. Explains learning objectives, motivating students, conducting a class activity that includes graph construction, and concluding and evaluating the lesson. Lists materials needed. (GG)

  2. Standard Distributions: One Graph Fits All

    ERIC Educational Resources Information Center

    Wagner, Clifford H.

    2007-01-01

    Standard distributions are ubiquitous but not unique. With suitable scaling, the graph of a standard distribution serves as the graph for every distribution in the family. The standard exponential can easily be taught in elementary statistics courses.

  3. Understanding Conic Sections Using Alternate Graph Paper

    ERIC Educational Resources Information Center

    Brown, Elizabeth M.; Jones, Elizabeth

    2006-01-01

    This article describes two alternative coordinate systems and their use in graphing conic sections. This alternative graph paper helps students explore the idea of eccentricity using the definitions of the conic sections.

  4. Graphing and Social Studies: An Interdisciplinary Activity.

    ERIC Educational Resources Information Center

    Brehm, Julia L.

    1996-01-01

    Describes a graphing activity that promotes mathematical connections with social studies lessons. Students should be familiar with graphing on the Cartesian coordinate system to play this variation of the game Battleship on maps of various regions of the world. (AIM)

  5. Comparison Graph of Sea Ice Minimum - 2010

    NASA Video Gallery

    This animated graph tracks the retreat of sea ice, measured in millions of square kilometers, averaged from the start of the satellite record in 1979 through 2000 (white). Next, the graph follows t...

  6. Mathematical Minute: Rotating a Function Graph

    ERIC Educational Resources Information Center

    Bravo, Daniel; Fera, Joseph

    2013-01-01

    Using calculus only, we find the angles you can rotate the graph of a differentiable function about the origin and still obtain a function graph. We then apply the solution to odd and even degree polynomials.

  7. Dr.L: Distributed Recursive (Graph) Layout

    2007-11-19

    Dr. L provides two-dimensional visualizations of very large abstract graph structures. it can be used for data mining applications including biology, scientific literature, and social network analysis. Dr. L is a graph layout program that uses a multilevel force-directed algorithm. A graph is input and drawn using a force-directed algorithm based on simulated annealing. The resulting layout is clustered using a single link algorithm. This clustering is used to produce a coarsened graph (fewer nodes)more » which is then re-drawn. this process is repeated until a sufficiently small graph is produced. The smallest graph is drawn and then used as a basis for drawing the original graph by refining the series of coarsened graphs that were produced. The layout engine can be run in serial or in parallel.« less

  8. Microcomputer Unit: Graphing Straight Lines.

    ERIC Educational Resources Information Center

    Hastings, Ellen H.; Yates, Daniel S.

    1983-01-01

    The material is designed to help pupils investigate how the value for slope in the equation of a line affects the inclination for the graph of an equation. A program written in BASIC designed to run on an Apple microcomputer is included. Worksheet masters for duplication are provided. (MP)

  9. Situating Graphs as Workplace Knowledge

    ERIC Educational Resources Information Center

    Noss, Richard; Bakker, Arthur; Hoyles, Celia; Kent, Phillip

    2007-01-01

    We investigate the use and knowledge of graphs in the context of a large industrial factory. We are particularly interested in the question of "transparency", a question that has been extensively considered in the general literature on tool use and, more recently, by Michael Roth and his colleagues in the context of scientific work. Roth uses the…

  10. Box graphs and singular fibers

    NASA Astrophysics Data System (ADS)

    Hayashi, Hirotaka; Lawrie, Craig; Morrison, David R.; Schafer-Nameki, Sakura

    2014-05-01

    We determine the higher codimension fibers of elliptically fibered Calabi-Yau fourfolds with section by studying the three-dimensional = 2 supersymmetric gauge theory with matter which describes the low energy effective theory of M-theory compactified on the associated Weierstrass model, a singular model of the fourfold. Each phase of the Coulomb branch of this theory corresponds to a particular resolution of the Weierstrass model, and we show that these have a concise description in terms of decorated box graphs based on the representation graph of the matter multiplets, or alternatively by a class of convex paths on said graph. Transitions between phases have a simple interpretation as "flopping" of the path, and in the geometry correspond to actual flop transitions. This description of the phases enables us to enumerate and determine the entire network between them, with various matter representations for all reductive Lie groups. Furthermore, we observe that each network of phases carries the structure of a (quasi-)minuscule representation of a specific Lie algebra. Interpreted from a geometric point of view, this analysis determines the generators of the cone of effective curves as well as the network of flop transitions between crepant resolutions of singular elliptic Calabi-Yau fourfolds. From the box graphs we determine all fiber types in codimensions two and three, and we find new, non-Kodaira, fiber types for E 6, E7 and E 8.

  11. Affect and Graphing Calculator Use

    ERIC Educational Resources Information Center

    McCulloch, Allison W.

    2011-01-01

    This article reports on a qualitative study of six high school calculus students designed to build an understanding about the affect associated with graphing calculator use in independent situations. DeBellis and Goldin's (2006) framework for affect as a representational system was used as a lens through which to understand the ways in which…

  12. Ancestral Genres of Mathematical Graphs

    ERIC Educational Resources Information Center

    Gerofsky, Susan

    2011-01-01

    Drawing from sources in gesture studies, cognitive science, the anthropology of religion and art/architecture history, this article explores cultural, bodily and cosmological resonances carried (unintentionally) by mathematical graphs on Cartesian coordinates. Concepts of asymmetric bodily spaces, grids, orthogonality, mapping and sacred spaces…

  13. Humidity Graphs for All Seasons.

    ERIC Educational Resources Information Center

    Esmael, F.

    1982-01-01

    In a previous article in this journal (Vol. 17, p358, 1979), a wet-bulb depression table was recommended for two simple experiments to determine relative humidity. However, the use of a graph is suggested because it gives the relative humidity directly from the wet and dry bulb readings. (JN)

  14. Graphs and Enhancing Maple Multiplication.

    ERIC Educational Resources Information Center

    Cecil, David R.; Wang, Rongdong

    2002-01-01

    Description of a technique in Maple programming language that automatically prints all paths of any desired length along with the name of each vertex, proceeding in order from the beginning vertex to the ending vertex for a given graph. (Author/MM)

  15. Automating 3D reconstruction using a probabilistic grammar

    NASA Astrophysics Data System (ADS)

    Xiong, Hanwei; Xu, Jun; Xu, Chenxi; Pan, Ming

    2015-10-01

    3D reconstruction of objects from point clouds with a laser scanner is still a laborious task in many applications. Automating 3D process is an ongoing research topic and suffers from the complex structure of the data. The main difficulty is due to lack of knowledge of real world objects structure. In this paper, we accumulate such structure knowledge by a probabilistic grammar learned from examples in the same category. The rules of the grammar capture compositional structures at different levels, and a feature dependent probability function is attached for every rule. The learned grammar can be used to parse new 3D point clouds, organize segment patches in a hierarchal way, and assign them meaningful labels. The parsed semantics can be used to guide the reconstruction algorithms automatically. Some examples are given to explain the method.

  16. Control by quantum dynamics on graphs

    SciTech Connect

    Godsil, Chris; Severini, Simone

    2010-05-15

    We address the study of controllability of a closed quantum system whose dynamical Lie algebra is generated by adjacency matrices of graphs. We characterize a large family of graphs that renders a system controllable. The key property is a graph-theoretic feature consisting of a particularly disordered cycle structure. Disregarding efficiency of control functions, but choosing subfamilies of sparse graphs, the results translate into continuous-time quantum walks for universal computation.

  17. Chemical Applications of Graph Theory: Part II. Isomer Enumeration.

    ERIC Educational Resources Information Center

    Hansen, Peter J.; Jurs, Peter C.

    1988-01-01

    Discusses the use of graph theory to aid in the depiction of organic molecular structures. Gives a historical perspective of graph theory and explains graph theory terminology with organic examples. Lists applications of graph theory to current research projects. (ML)

  18. Laplacian versus adjacency matrix in quantum walk search

    NASA Astrophysics Data System (ADS)

    Wong, Thomas G.; Tarrataca, Luís; Nahimov, Nikolay

    2016-10-01

    A quantum particle evolving by Schrödinger's equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace's operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Laplacian and adjacency matrix. The two walks differ qualitatively and quantitatively in their required jumping rate, runtime, sampling of marked vertices, and in what constitutes a natural initial state. Thus the choice of the Laplacian or adjacency matrix to effect the walk has important algorithmic consequences.

  19. Laplacian versus adjacency matrix in quantum walk search

    NASA Astrophysics Data System (ADS)

    Wong, Thomas G.; Tarrataca, Luís; Nahimov, Nikolay

    2016-06-01

    A quantum particle evolving by Schrödinger's equation contains, from the kinetic energy of the particle, a term in its Hamiltonian proportional to Laplace's operator. In discrete space, this is replaced by the discrete or graph Laplacian, which gives rise to a continuous-time quantum walk. Besides this natural definition, some quantum walk algorithms instead use the adjacency matrix to effect the walk. While this is equivalent to the Laplacian for regular graphs, it is different for non-regular graphs and is thus an inequivalent quantum walk. We algorithmically explore this distinction by analyzing search on the complete bipartite graph with multiple marked vertices, using both the Laplacian and adjacency matrix. The two walks differ qualitatively and quantitatively in their required jumping rate, runtime, sampling of marked vertices, and in what constitutes a natural initial state. Thus the choice of the Laplacian or adjacency matrix to effect the walk has important algorithmic consequences.

  20. My Bar Graph Tells a Story

    ERIC Educational Resources Information Center

    McMillen, Sue; McMillen, Beth

    2010-01-01

    Connecting stories to qualitative coordinate graphs has been suggested as an effective instructional strategy. Even students who are able to "create" bar graphs may struggle to correctly "interpret" them. Giving children opportunities to work with qualitative graphs can help them develop the skills to interpret, describe, and compare information…

  1. So Many Graphs, So Little Time

    ERIC Educational Resources Information Center

    Wall, Jennifer J.; Benson, Christine C.

    2009-01-01

    Interpreting graphs found in various content areas is an important skill for students, especially in light of high-stakes testing. In addition, reading and understanding graphs is an important part of numeracy, or numeric literacy, a skill necessary for informed citizenry. This article explores the different categories of graphs, provides…

  2. Collaborative Robotic Instruction: A Graph Teaching Experience

    ERIC Educational Resources Information Center

    Mitnik, Ruben; Recabarren, Matias; Nussbaum, Miguel; Soto, Alvaro

    2009-01-01

    Graphing is a key skill in the study of Physics. Drawing and interpreting graphs play a key role in the understanding of science, while the lack of these has proved to be a handicap and a limiting factor in the learning of scientific concepts. It has been observed that despite the amount of previous graph-working experience, students of all ages…

  3. 47 CFR 80.761 - Conversion graphs.

    Code of Federal Regulations, 2010 CFR

    2010-10-01

    ... 47 Telecommunication 5 2010-10-01 2010-10-01 false Conversion graphs. 80.761 Section 80.761... MARITIME SERVICES Standards for Computing Public Coast Station VHF Coverage § 80.761 Conversion graphs. The following graphs must be employed where conversion from one to the other of the indicated types of units...

  4. 47 CFR 80.761 - Conversion graphs.

    Code of Federal Regulations, 2011 CFR

    2011-10-01

    ... 47 Telecommunication 5 2011-10-01 2011-10-01 false Conversion graphs. 80.761 Section 80.761... MARITIME SERVICES Standards for Computing Public Coast Station VHF Coverage § 80.761 Conversion graphs. The following graphs must be employed where conversion from one to the other of the indicated types of units...

  5. 47 CFR 80.761 - Conversion graphs.

    Code of Federal Regulations, 2013 CFR

    2013-10-01

    ... 47 Telecommunication 5 2013-10-01 2013-10-01 false Conversion graphs. 80.761 Section 80.761... MARITIME SERVICES Standards for Computing Public Coast Station VHF Coverage § 80.761 Conversion graphs. The following graphs must be employed where conversion from one to the other of the indicated types of units...

  6. 47 CFR 80.761 - Conversion graphs.

    Code of Federal Regulations, 2012 CFR

    2012-10-01

    ... 47 Telecommunication 5 2012-10-01 2012-10-01 false Conversion graphs. 80.761 Section 80.761... MARITIME SERVICES Standards for Computing Public Coast Station VHF Coverage § 80.761 Conversion graphs. The following graphs must be employed where conversion from one to the other of the indicated types of units...

  7. 47 CFR 80.761 - Conversion graphs.

    Code of Federal Regulations, 2014 CFR

    2014-10-01

    ... 47 Telecommunication 5 2014-10-01 2014-10-01 false Conversion graphs. 80.761 Section 80.761... MARITIME SERVICES Standards for Computing Public Coast Station VHF Coverage § 80.761 Conversion graphs. The following graphs must be employed where conversion from one to the other of the indicated types of units...

  8. An Evaluation of Universal Grammar and the Phonological Mind1

    PubMed Central

    Everett, Daniel L.

    2016-01-01

    This paper argues against the hypothesis of a “phonological mind” advanced by Berent. It establishes that there is no evidence that phonology is innate and that, in fact, the simplest hypothesis seems to be that phonology is learned like other human abilities. Moreover, the paper fleshes out the original claim of Philip Lieberman that Universal Grammar predicts that not everyone should be able to learn every language, i.e., the opposite of what UG is normally thought to predict. The paper also underscores the problem that the absence of recursion in Pirahã represents for Universal Grammar proposals. PMID:26903889

  9. An Evaluation of Universal Grammar and the Phonological Mind.

    PubMed

    Everett, Daniel L

    2016-01-01

    This paper argues against the hypothesis of a "phonological mind" advanced by Berent. It establishes that there is no evidence that phonology is innate and that, in fact, the simplest hypothesis seems to be that phonology is learned like other human abilities. Moreover, the paper fleshes out the original claim of Philip Lieberman that Universal Grammar predicts that not everyone should be able to learn every language, i.e., the opposite of what UG is normally thought to predict. The paper also underscores the problem that the absence of recursion in Pirahã represents for Universal Grammar proposals.

  10. On Anaphora and the Binding Principles in Categorial Grammar

    NASA Astrophysics Data System (ADS)

    Morrill, Glyn; Valentín, Oriol

    In type logical categorial grammar the analysis of an expression is a resource-conscious proof. Anaphora represents a particular challenge to this approach in that the antecedent resource is multiplied in the semantics. This duplication, which corresponds logically to the structural rule of contraction, may be treated lexically or syntactically. Furthermore, anaphora is subject to constraints, which Chomsky (1981) formulated as Binding Principles A, B, and C. In this paper we consider English anaphora in categorial grammar including reference to the binding principles. We invoke displacement calculus, modal categorial calculus, categorial calculus with limited contraction, and entertain addition of negation as failure.

  11. Model reduction for stochastic CaMKII reaction kinetics in synapses by graph-constrained correlation dynamics

    PubMed Central

    Johnson, Todd; Bartol, Tom; Sejnowski, Terrence; Mjolsness, Eric

    2015-01-01

    Astochastic reaction network model of Ca2+ dynamics in synapses (Pepke et al PLoS Comput. Biol. 6 e1000675) is expressed and simulated using rule-based reaction modeling notation in dynamical grammars and in MCell. The model tracks the response of calmodulin and CaMKII to calcium influx in synapses. Data from numerically intensive simulations is used to train a reduced model that, out of sample, correctly predicts the evolution of interaction parameters characterizing the instantaneous probability distribution over molecular states in the much larger fine-scale models. The novel model reduction method, ‘graph-constrained correlation dynamics’, requires a graph of plausible state variables and interactions as input. It parametrically optimizes a set of constant coefficients appearing in differential equations governing the time-varying interaction parameters that determine all correlations between variables in the reduced model at any time slice. PMID:26086598

  12. Proceedings of a Conference--"The Future of Grammar in American Schools" (Winchester, VA, August 10-11, 1990).

    ERIC Educational Resources Information Center

    National Council of Teachers of English, Urbana, IL. Assembly for the Teaching of English Grammar.

    Providing alternatives to the way grammar is taught, this proceedings includes every paper (or summary) except one delivered at a conference on the future of grammar in American schools. Papers in the proceedings are: "Keynote: The Future of Grammar in American Schools" (Martha Kolln); "Approaches to Grammar: Teaching & Otherwise" (Kathy…

  13. Fast graph operations in quantum computation

    NASA Astrophysics Data System (ADS)

    Zhao, Liming; Pérez-Delgado, Carlos A.; Fitzsimons, Joseph F.

    2016-03-01

    The connection between certain entangled states and graphs has been heavily studied in the context of measurement-based quantum computation as a tool for understanding entanglement. Here we show that this correspondence can be harnessed in the reverse direction to yield a graph data structure, which allows for more efficient manipulation and comparison of graphs than any possible classical structure. We introduce efficient algorithms for many transformation and comparison operations on graphs represented as graph states, and prove that no classical data structure can have similar performance for the full set of operations studied.

  14. Generalization of the Bollobás-Riordan polynomial for tensor graphs

    NASA Astrophysics Data System (ADS)

    Tanasa, Adrian

    2011-07-01

    Tensor models are used nowadays for implementing a fundamental theory of quantum gravity. We define here a polynomial T encoding the supplementary topological information. This polynomial is a natural generalization of the Bollobás-Riordan polynomial (used to characterize matrix graphs) and is different from the Gurău polynomial [R. Gurău, Ann. Henri Poincare 11, 565 (2010)], 10.1007/s00023-010-0035-6, defined for a particular class of tensor graphs, the colorable ones. The polynomial T is defined for both colorable and non-colorable graphs and it is proved to satisfy the deletion/contraction relation. A non-trivial example of a non-colorable graphs is analyzed.

  15. Constrained Graph Optimization: Interdiction and Preservation Problems

    SciTech Connect

    Schild, Aaron V

    2012-07-30

    The maximum flow, shortest path, and maximum matching problems are a set of basic graph problems that are critical in theoretical computer science and applications. Constrained graph optimization, a variation of these basic graph problems involving modification of the underlying graph, is equally important but sometimes significantly harder. In particular, one can explore these optimization problems with additional cost constraints. In the preservation case, the optimizer has a budget to preserve vertices or edges of a graph, preventing them from being deleted. The optimizer wants to find the best set of preserved edges/vertices in which the cost constraints are satisfied and the basic graph problems are optimized. For example, in shortest path preservation, the optimizer wants to find a set of edges/vertices within which the shortest path between two predetermined points is smallest. In interdiction problems, one deletes vertices or edges from the graph with a particular cost in order to impede the basic graph problems as much as possible (for example, delete edges/vertices to maximize the shortest path between two predetermined vertices). Applications of preservation problems include optimal road maintenance, power grid maintenance, and job scheduling, while interdiction problems are related to drug trafficking prevention, network stability assessment, and counterterrorism. Computational hardness results are presented, along with heuristic methods for approximating solutions to the matching interdiction problem. Also, efficient algorithms are presented for special cases of graphs, including on planar graphs. The graphs in many of the listed applications are planar, so these algorithms have important practical implications.

  16. Hierarchical structure of the logical Internet graph

    NASA Astrophysics Data System (ADS)

    Ge, Zihui; Figueiredo, Daniel R.; Jaiswal, Sharad; Gao, Lixin

    2001-07-01

    The study of the Internet topology has recently received much attention from the research community. In particular, the observation that the network graph has interesting properties, such as power laws, that might be explored in a myriad of ways. Most of the work in characterizing the Internet graph is based on the physical network graph, i.e., the connectivity graph. In this paper we investigate how logical relationships between nodes of the AS graph can be used to gain insight to its structure. We characterize the logical graph using various metrics and identify the presence of power laws in the number of customers that a provider has. Using these logical relationships we define a structural model of the AS graph. The model highlights the hierarchical nature of logical relationships and the preferential connection to larger providers. We also investigate the consistency of this model over time and observe interesting properties of the hierarchical structure.

  17. Molecular graph convolutions: moving beyond fingerprints.

    PubMed

    Kearnes, Steven; McCloskey, Kevin; Berndl, Marc; Pande, Vijay; Riley, Patrick

    2016-08-01

    Molecular "fingerprints" encoding structural information are the workhorse of cheminformatics and machine learning in drug discovery applications. However, fingerprint representations necessarily emphasize particular aspects of the molecular structure while ignoring others, rather than allowing the model to make data-driven decisions. We describe molecular graph convolutions, a machine learning architecture for learning from undirected graphs, specifically small molecules. Graph convolutions use a simple encoding of the molecular graph-atoms, bonds, distances, etc.-which allows the model to take greater advantage of information in the graph structure. Although graph convolutions do not outperform all fingerprint-based methods, they (along with other graph-based methods) represent a new paradigm in ligand-based virtual screening with exciting opportunities for future improvement. PMID:27558503

  18. The Feynman Identity for Planar Graphs

    NASA Astrophysics Data System (ADS)

    da Costa, G. A. T. F.

    2016-08-01

    The Feynman identity (FI) of a planar graph relates the Euler polynomial of the graph to an infinite product over the equivalence classes of closed nonperiodic signed cycles in the graph. The main objectives of this paper are to compute the number of equivalence classes of nonperiodic cycles of given length and sign in a planar graph and to interpret the data encoded by the FI in the context of free Lie superalgebras. This solves in the case of planar graphs a problem first raised by Sherman and sets the FI as the denominator identity of a free Lie superalgebra generated from a graph. Other results are obtained. For instance, in connection with zeta functions of graphs.

  19. Fast Approximate Quadratic Programming for Graph Matching

    PubMed Central

    Vogelstein, Joshua T.; Conroy, John M.; Lyzinski, Vince; Podrazik, Louis J.; Kratzer, Steven G.; Harley, Eric T.; Fishkind, Donniell E.; Vogelstein, R. Jacob; Priebe, Carey E.

    2015-01-01

    Quadratic assignment problems arise in a wide variety of domains, spanning operations research, graph theory, computer vision, and neuroscience, to name a few. The graph matching problem is a special case of the quadratic assignment problem, and graph matching is increasingly important as graph-valued data is becoming more prominent. With the aim of efficiently and accurately matching the large graphs common in big data, we present our graph matching algorithm, the Fast Approximate Quadratic assignment algorithm. We empirically demonstrate that our algorithm is faster and achieves a lower objective value on over 80% of the QAPLIB benchmark library, compared with the previous state-of-the-art. Applying our algorithm to our motivating example, matching C. elegans connectomes (brain-graphs), we find that it efficiently achieves performance. PMID:25886624

  20. Molecular graph convolutions: moving beyond fingerprints.

    PubMed

    Kearnes, Steven; McCloskey, Kevin; Berndl, Marc; Pande, Vijay; Riley, Patrick

    2016-08-01

    Molecular "fingerprints" encoding structural information are the workhorse of cheminformatics and machine learning in drug discovery applications. However, fingerprint representations necessarily emphasize particular aspects of the molecular structure while ignoring others, rather than allowing the model to make data-driven decisions. We describe molecular graph convolutions, a machine learning architecture for learning from undirected graphs, specifically small molecules. Graph convolutions use a simple encoding of the molecular graph-atoms, bonds, distances, etc.-which allows the model to take greater advantage of information in the graph structure. Although graph convolutions do not outperform all fingerprint-based methods, they (along with other graph-based methods) represent a new paradigm in ligand-based virtual screening with exciting opportunities for future improvement.

  1. On a programming language for graph algorithms

    NASA Technical Reports Server (NTRS)

    Rheinboldt, W. C.; Basili, V. R.; Mesztenyi, C. K.

    1971-01-01

    An algorithmic language, GRAAL, is presented for describing and implementing graph algorithms of the type primarily arising in applications. The language is based on a set algebraic model of graph theory which defines the graph structure in terms of morphisms between certain set algebraic structures over the node set and arc set. GRAAL is modular in the sense that the user specifies which of these mappings are available with any graph. This allows flexibility in the selection of the storage representation for different graph structures. In line with its set theoretic foundation, the language introduces sets as a basic data type and provides for the efficient execution of all set and graph operators. At present, GRAAL is defined as an extension of ALGOL 60 (revised) and its formal description is given as a supplement to the syntactic and semantic definition of ALGOL. Several typical graph algorithms are written in GRAAL to illustrate various features of the language and to show its applicability.

  2. Molecular graph convolutions: moving beyond fingerprints

    NASA Astrophysics Data System (ADS)

    Kearnes, Steven; McCloskey, Kevin; Berndl, Marc; Pande, Vijay; Riley, Patrick

    2016-08-01

    Molecular "fingerprints" encoding structural information are the workhorse of cheminformatics and machine learning in drug discovery applications. However, fingerprint representations necessarily emphasize particular aspects of the molecular structure while ignoring others, rather than allowing the model to make data-driven decisions. We describe molecular "graph convolutions", a machine learning architecture for learning from undirected graphs, specifically small molecules. Graph convolutions use a simple encoding of the molecular graph---atoms, bonds, distances, etc.---which allows the model to take greater advantage of information in the graph structure. Although graph convolutions do not outperform all fingerprint-based methods, they (along with other graph-based methods) represent a new paradigm in ligand-based virtual screening with exciting opportunities for future improvement.

  3. Subgraph-Based Filterbanks for Graph Signals

    NASA Astrophysics Data System (ADS)

    Tremblay, Nicolas; Borgnat, Pierre

    2016-08-01

    We design a critically-sampled compact-support biorthogonal transform for graph signals, via graph filterbanks. Instead of partitioning the nodes in two sets so as to remove one every two nodes in the filterbank downsampling operations, the design is based on a partition of the graph in connected subgraphs. Coarsening is achieved by defining one "supernode" for each subgraph and the edges for this coarsened graph derives from the connectivity between the subgraphs. Unlike the "one every two nodes" downsampling on bipartite graphs, this coarsening operation does not have an exact formulation in the graph Fourier domain. Instead, we rely on the local Fourier bases of each subgraph to define filtering operations. We apply successfully this method to decompose graph signals, and show promising performance on compression and denoising.

  4. Line graphs as social networks

    NASA Astrophysics Data System (ADS)

    Krawczyk, M. J.; Muchnik, L.; Mańka-Krasoń, A.; Kułakowski, K.

    2011-07-01

    It was demonstrated recently that the line graphs are clustered and assortative. These topological features are known to characterize some social networks [M.E.J. Newman, Y. Park, Why social networks are different from other types of networks, Phys. Rev. E 68 (2003) 036122]; it was argued that this similarity reveals their cliquey character. In the model proposed here, a social network is the line graph of an initial network of families, communities, interest groups, school classes and small companies. These groups play the role of nodes, and individuals are represented by links between these nodes. The picture is supported by the data on the LiveJournal network of about 8×10 6 people.

  5. Graph theoretic analysis of structural connectivity across the spectrum of Alzheimer's disease: The importance of graph creation methods.

    PubMed

    Phillips, David J; McGlaughlin, Alec; Ruth, David; Jager, Leah R; Soldan, Anja

    2015-01-01

    Graph theory is increasingly being used to study brain connectivity across the spectrum of Alzheimer's disease (AD), but prior findings have been inconsistent, likely reflecting methodological differences. We systematically investigated how methods of graph creation (i.e., type of correlation matrix and edge weighting) affect structural network properties and group differences. We estimated the structural connectivity of brain networks based on correlation maps of cortical thickness obtained from MRI. Four groups were compared: 126 cognitively normal older adults, 103 individuals with Mild Cognitive Impairment (MCI) who retained MCI status for at least 3 years (stable MCI), 108 individuals with MCI who progressed to AD-dementia within 3 years (progressive MCI), and 105 individuals with AD-dementia. Small-world measures of connectivity (characteristic path length and clustering coefficient) differed across groups, consistent with prior studies. Groups were best discriminated by the Randić index, which measures the degree to which highly connected nodes connect to other highly connected nodes. The Randić index differentiated the stable and progressive MCI groups, suggesting that it might be useful for tracking and predicting the progression of AD. Notably, however, the magnitude and direction of group differences in all three measures were dependent on the method of graph creation, indicating that it is crucial to take into account how graphs are constructed when interpreting differences across diagnostic groups and studies. The algebraic connectivity measures showed few group differences, independent of the method of graph construction, suggesting that global connectivity as it relates to node degree is not altered in early AD.

  6. Relativity on Rotated Graph Paper

    NASA Astrophysics Data System (ADS)

    Salgado, Roberto

    2011-11-01

    We present visual calculations in special relativity using spacetime diagrams drawn on graph paper that has been rotated by 45 degrees. The rotated lines represent lightlike directions in Minkowski spacetime, and the boxes in the grid (called light-clock diamonds) represent ticks of an inertial observer's lightclock. We show that many quantitative results can be read off a spacetime diagram by counting boxes, using a minimal amount of algebra.

  7. A Practical Spanish Grammar for Border Patrol Officers.

    ERIC Educational Resources Information Center

    Immigration and Naturalization Service (Dept. of Justice), Washington, DC.

    Written for probationary patrol inspectors at the Border Patrol Training School, El Paso, Texas, this text presents a concise, traditional analysis of Spanish grammar. Each of the 21 lessons focuses on an aspect of the language including sections on the parts of speech, special verbs, commands, numbers, passive voice, and the subjunctive mood. A…

  8. English Verbs of Future Reference in a Pedagogical Grammar

    ERIC Educational Resources Information Center

    Smith, Michael Sharwood

    1972-01-01

    A method is proposed for formalizing the basic meanings underlying the forms of verbs which contain future reference. The method proposed is intended as a contribution to pedagogical grammar rather than theoretical linguistics. See FL 508 197 for availability. (Author/RM)

  9. The Role of Grammar Instruction in a Communicative Approach.

    ERIC Educational Resources Information Center

    Terrell, Tracy David

    1991-01-01

    Theory and research suggest three ways grammar instruction might assist second-language acquisition. These include the following: as an advance organizer; as a meaning-form focus in communication activities where there are many examples of a single meaning-form relationship; and through monitoring, if learners can acquire their own input. (41…

  10. Trends in the Teaching of Grammar in Spanish Language Textbooks.

    ERIC Educational Resources Information Center

    Terrell, Tracy David

    1990-01-01

    Proposes and illustrates the use of a framework for describing methodological trends in beginning-level college Spanish texts. The framework's five parameters focus on communication activities/grammar; contextualization/non-contextualization; meaningful/role; divergent/convergent; and interactive/non-interactive exercises. (21 references) (CB)

  11. Complex Text in ESL Grammar Textbooks: Barriers or Gateways?

    ERIC Educational Resources Information Center

    Lesikin, Joan

    2000-01-01

    Suggests that English-as-a-Second-Language (ESL) teachers assess prospective textbooks by comparing real-life user's actual knowledge of the author's assumed student knowledge. Through examination of charts and page excerpts of two ESL grammar textbooks, demonstrates that access to the pedagogical knowledge demands sophisticated formal knowledge,…

  12. Cognitive Adequacy in a Dialogic Functional Discourse Grammar

    ERIC Educational Resources Information Center

    Mackenzie, J. Lachlan

    2012-01-01

    Functional Discourse Grammar (FDG), as a theory of the organization of natural languages, seeks to attain pragmatic, typological and cognitive adequacy. The attempt to achieve cognitive adequacy has been fraught with problems stemming from the vagueness of the concept and the difficulty of adapting to trends in psycholinguistics. Specifically,…

  13. On the Form of Bilingual Grammars: The Phonological Component.

    ERIC Educational Resources Information Center

    Elerick, Charles

    This research is based on the assumption that a Spanish/English bilingual is aware of the phonological and semantic relatedness of the many hundreds of pairs of transparently cognate items in the two languages. This awareness is linguistically significant in that it is reflected in the internalized grammar of the bilingual. The bilingual speaker…

  14. The Foreign Language Syllabus--Grammar, Notions and Functions.

    ERIC Educational Resources Information Center

    Saltarelli, Mario, Ed.

    1983-01-01

    Papers in this journal issue concern various aspects of foreign language syllabus construction. Titles and authors are: "The Threshold Level: A Notional-Functional Syllabus" (Barbara F. Matthies); "Functions of Grammar in a Language Teaching Syllabus" (William E. Rutherford); "Communicative and Grammatical Syllabuses to Teach Conversational…

  15. The Strategies Approach: Effective for Reviewing Grammar and Punctuation Concepts

    ERIC Educational Resources Information Center

    Quible, Zane K.

    2008-01-01

    This article is based on results of a quasi-experimental study in which the efficacy of the strategies approach for reviewing grammar and punctuation concepts was assessed in a business communication course. The control group studied rules-based review materials; the treatment group studied strategies-based review materials. On the three sets of…

  16. Improving DHH Students' Grammar through an Individualized Software Program

    ERIC Educational Resources Information Center

    Cannon, Joanna E.; Easterbrooks, Susan R.; Gagne, Phill; Beal-Alvarez, Jennifer

    2011-01-01

    The purpose of this study was to determine if the frequent use of a targeted, computer software grammar instruction program, used as an individualized classroom activity, would influence the comprehension of morphosyntax structures (determiners, tense, and complementizers) in deaf/hard-of-hearing (DHH) participants who use American Sign Language…

  17. Lexical, Functional Grammar Analysis of Korean Complex Predicates.

    ERIC Educational Resources Information Center

    Kim, Hee-Seob

    The structure of complementation in complex predicates in Korean has attracted configurational analysis. Using a lexical functional grammar (LFG) framework, this paper examines the structure of complementation in complex predicates. The term "predicate" in this context is used to describe both verbs and adjectives that are assumed to consist of…

  18. Using a Corpus in a 300-Level Spanish Grammar Course

    ERIC Educational Resources Information Center

    Benavides, Carlos

    2015-01-01

    The present study examined the use and effectiveness of a large corpus--the Corpus del Español (Davies, 2002)--in a 300-level Spanish grammar university course. Students conducted hands-on corpus searches with the goal of finding concordances containing particular types of collocations (combinations of words that tend to co-occur) and tokens (any…

  19. Caught'ya Again! More Grammar with a Giggle.

    ERIC Educational Resources Information Center

    Kiester, Jane Bell

    This teaching guide is built around a method (called the "Caught'ya" method) of teaching grammar and mechanics with humor. The guide contains story ideas and three sets of 100 Caught'ya sentences, as well as a chapter which discusses specific ways to use the Caught'ya at home. Following an introduction, the guide is divided into the following nine…

  20. Slavic in Head-Driven Phrase Structure Grammar.

    ERIC Educational Resources Information Center

    Borsley, Robert D., Ed.; Przepiorkowski, Adam, Ed.

    The collection of essays on the properties of Slavic languages in the context of the theory of head-driven phrase structure grammar (HPSG) includes: "Typological Similarities in HPSG" (Tania Avgustinova, Wojciech Skut, Hans Uszkoreit); "Auxiliaries, Verbs and Complementizers in Polish" (Robert D. Borsley); "An Architecture for Phonology" (Tilman…

  1. Kiribati (Gilbertese): Grammar Handbook. Peace Corps Language Handbook Series.

    ERIC Educational Resources Information Center

    Trussel, Stephen

    This grammar handbook analyzes the rules of the Kiribati language and provides exercises on them. It is divided into 40 lessons. The first part of each lesson is a description of some part of the language, with examples; the second part is made up of oral and written exercises. Answers to the written exercises are provided at the end of the book,…

  2. The Pedagogic Effectiveness of Developmental Readiness in ESL Grammar Instruction

    ERIC Educational Resources Information Center

    Mansouri, Fethi; Duffy, Loretta

    2005-01-01

    The project reported in this paper aims to test the concept of "learner developmental readiness" and its pedagogic effectiveness in the teaching of foreign language grammar. It focuses on the teaching of English as a second language (ESL) in a formal classroom context. The aim is to ascertain whether a specific teaching order based on the concept…

  3. Noam Chomsky Writes to Mrs. Davis about Grammar and Education.

    ERIC Educational Resources Information Center

    English Education, 1984

    1984-01-01

    In a personal letter, Chomsky suggests that while the study of grammar has little detectable effect on writing ability, it can, as a branch of science, help students learn how (and why) to think about hard and intriguing questions and to develop natural curiosity. (HOD)

  4. Perceptual Constraints and the Learnability of Simple Grammars

    ERIC Educational Resources Information Center

    Endress, Ansgar D.; Dehaene-Lambertz, Ghislaine; Mehler, Jacques

    2007-01-01

    Cognitive processes are often attributed to statistical or symbolic general-purpose mechanisms. Here we show that some spontaneous generalizations are driven by specialized, highly constrained symbolic operations. We explore how two types of artificial grammars are acquired, one based on repetitions and the other on characteristic relations…

  5. Tanzanian Swahili: Grammar Handbook. Peace Corps Language Handbook Series.

    ERIC Educational Resources Information Center

    Hawkinson, Annie K.

    This grammar handbook analyzes the rules of Tanzanian Swahili and provides different types of exercises on them. It is divided into 36 lessons and is illustrated with pen-and-ink drawings. A bibliography, index, and Swahili-English glossary complete the volume. (AMH)

  6. Kabiye Grammar Handbook. Peace Corps Language Handbook Series.

    ERIC Educational Resources Information Center

    Sedlak, Philip A. S.

    This handbook contains 20 lessons on Kabiye phonology and grammar and is intended particularly for Peace Corps volunteers in Togo. Each lesson contains explanations in English, vocabulary, and oral and written exercises. A number of pen-and-ink drawings of cultural interest illustrate the lessons. An answer key to the written exercises and a…

  7. A Pilot Test of Grammar and Punctuation Software.

    ERIC Educational Resources Information Center

    Ober, Scot

    1988-01-01

    The author identified grammar and punctuation software suitable for secondary or postsecondary business students. Three programs--(1) Agreement of Subject and Verb, (2) Punctuation Review, and (3) English Achievement I--were field tested in a classroom setting. Student impressions of the programs are reported. (CH)

  8. Aspects of a Grammar of Makary Kotoko (Chadic, Cameroon)

    ERIC Educational Resources Information Center

    Allison, Sean David

    2012-01-01

    Makary Kotoko (MK), a Central Chadic B language, is spoken in the north of Cameroon just south of Lake Chad. Published works on MK to date include about a dozen articles on different aspects of the grammar of the language, primarily by H. Tourneux. The present work, which is based on a substantial corpus of recorded texts, is a systematic…

  9. El Hispanohablante y la Gramatica (The Spanish Speaker and Grammar).

    ERIC Educational Resources Information Center

    Blanco, George M.

    1994-01-01

    Studied the grammatical knowledge that undergraduates specializing in bilingual education have of their mother tongue. Data collected from an entrance exam, dialog journals and a simulated oral proficiency exam indicate that these students do not have a formal knowledge of grammatical rules but do have a high level of functional grammar. (24…

  10. Upending the Grammar of the Conventional Religious School

    ERIC Educational Resources Information Center

    Aron, Isa

    2014-01-01

    This article provides an overview and analysis of a relatively new phenomenon: congregational schools that have altered the conventional grammar of schooling, either through their structural arrangements or through their curricular approaches. Five pre-bar/bat mitzvah models are discussed: family schools, schools as communities,…

  11. Solomon Islands Pijin: Grammar Handbook. Peace Corps Language Handbook Series.

    ERIC Educational Resources Information Center

    Huebner, Thom; Horoi, Stephen Rex

    This grammar handbook analyzes the rules of Solomon Islands Pijin and provides exercises on them. It is divided into 24 lessons. The first part of each lesson is a description of some element or function of the language, with examples; the second part is made up of oral and written exercises. The volume concludes with appendices on the personal…

  12. Development and Analysis of Television Grammar: An Overall View.

    ERIC Educational Resources Information Center

    Metallinos, Nikos

    Research has shown that producers and consumers of television programs are still uncertain about the nature of the "grammar" or "lexicon" that makes up the language of television. Although attempts have been made in experimental television ("video art"), systematic studies on the idiosyncratic nature, unique features, and specific components of…

  13. A Grammar Sketch of the Kaki Ae Language.

    ERIC Educational Resources Information Center

    Clifton, John M.

    Kaki Ae is a non-Austronesian language spoken by about 300 people on the south coast of Papua New Guinea, at best distantly related to any other language in that area. A brief grammar sketch of the language is presented, including discussion of the phonology, sentences, phrases, words, and morpheme categories. Kaki Ae phonemics include 11…

  14. A Grammar of Southern Pomo: An Indigenous Language of California

    ERIC Educational Resources Information Center

    Walker, Neil Alexander

    2013-01-01

    Southern Pomo is a moribund indigenous language, one of seven closely related Pomoan languages once spoken in Northern California in the vicinity of the Russian River drainage, Clear Lake, and the adjacent Pacific coast. This work is the first full-length grammar of the language. It is divided into three parts. Part I introduces the sociocultural…

  15. The Story of English Grammar in United States Schools

    ERIC Educational Resources Information Center

    Kolln, Martha; Hancock, Craig

    2005-01-01

    This article assumes the value of a scientifically grounded, rhetorically focused, professionally supported, and publicly embraced grammar within the public schools and examines the past century of practices within the United States from that perspective. It describes a brief renaissance in the 50's and early 60's, inspired largely by the…

  16. Input-Based Grammar Pedagogy: A Comparison of Two Possibilities

    ERIC Educational Resources Information Center

    Marsden, Emma

    2005-01-01

    This article presents arguments for using listening and reading activities as an option for techniques in grammar pedagogy. It describes two possible approaches: Processing Instruction (PI) and Enriched Input (EI), and examples of their key features are included in the appendices. The article goes on to report on a classroom based quasi-experiment…

  17. Towards a Pragmatic Grammar of Teachers' Epistemic Networks.

    ERIC Educational Resources Information Center

    Tochon, Francois V.

    Possibilities of conceptual and pragmatic analysis exist for identifying epistemological processing in teacher thinking. These modes of organizing thought condition classroom planning, shape meaning from a virtual didactic knowledge-store, and scaffold further pedagogical interactions. The semio-cognitive grammar proposed is adapted to the…

  18. A Reference Grammar of Dutch, with Exercises and Key.

    ERIC Educational Resources Information Center

    Fehringer, Carol

    This textbook provides an accessible reference grammar of the Dutch language for English-speaking students of Dutch to help consolidate their knowledge through practical exercises on a whole range of grammatical topics. It is intended both for beginners and intermediate level students. Advanced learners of Dutch wishing to review particular…

  19. Artificial Intelligence Tools for Grammar and Spelling Instruction.

    ERIC Educational Resources Information Center

    Pijls, Fieny; And Others

    1987-01-01

    Discusses grammar and spelling instruction in The Netherlands for students aged 10-15 and describes an intelligent computer-assisted instructional environment consisting of a linguistic expert system, a didactic module, and a student interface. Three prototypes are described: BOUWSTEEN and COGO for analyzing sentences, and TDTDT for conjugating…

  20. E-Learning Turkish Language and Grammar: Analyzing Learners' Behavior

    ERIC Educational Resources Information Center

    Georgalas, Panagiotis

    2012-01-01

    This study analyses the behavior and the preferences of the Greek learners of Turkish language, who use a particular e-learning website in parallel with their studies, namely: http://turkish.pgeorgalas.gr. The website offers free online material in Greek and English language for learning the Turkish language and grammar. The traffic of several…

  1. Fluency Does Not Express Implicit Knowledge of Artificial Grammars

    ERIC Educational Resources Information Center

    Scott, Ryan B.; Dienes, Zoltan

    2010-01-01

    It is commonly held that implicit knowledge expresses itself as fluency. A perceptual clarification task was used to examine the relationship between perceptual processing fluency, subjective familiarity, and grammaticality judgments in a task frequently used to produce implicit knowledge, artificial grammar learning (AGL). Four experiments…

  2. The Role of Core Grammar in Pidgin Development.

    ERIC Educational Resources Information Center

    Macedo, Donaldo P.

    1986-01-01

    Examines the process of pidgin development within the context of the Government and Binding Theory proposed by Chomsky in 1981. Hypothesizes that the contact of various languages may produce a new experience which subsequently fixes the parameters of Universal Grammar, providing a pidgin core gammar. (SED)

  3. Hong Kong ESL Teachers' Questions About English Grammar.

    ERIC Educational Resources Information Center

    Wu, Kamyin; Sengupta, Sima

    1998-01-01

    This paper reports an exploratory study of questions about English grammar sent in by a group of Hong Kong English-as-a-Second-Language teachers to a teacher support network, "Telenex." The study examines the questions Hong Kong ESL teachers ask about the English language. (Author/JL)

  4. What Artificial Grammar Learning Reveals about the Neurobiology of Syntax

    ERIC Educational Resources Information Center

    Petersson, Karl-Magnus; Folia, Vasiliki; Hagoort, Peter

    2012-01-01

    In this paper we examine the neurobiological correlates of syntax, the processing of structured sequences, by comparing FMRI results on artificial and natural language syntax. We discuss these and similar findings in the context of formal language and computability theory. We used a simple right-linear unification grammar in an implicit artificial…

  5. Functional Grammar in the ESL Classroom: Noticing, Exploring and Practicing

    ERIC Educational Resources Information Center

    Lock, Graham; Jones, Rodney

    2011-01-01

    A set of easy to use techniques helps students discover for themselves how grammar works in real world contexts and how grammatical choices are not just about form but about meaning. Sample teaching ideas, covering a wide range of grammatical topics including verb tense, voice, reference and the organization of texts, accompanies each procedure.…

  6. SWAHILI GRAMMAR AND SYNTAX. DUQUESNE STUDIES, AFRICAN SERIES 1.

    ERIC Educational Resources Information Center

    LOOGMAN, ALFONS

    THIS COMPREHENSIVE STUDY OF SWAHILI, ONE OF THE BANTU LANGUAGES IN THE NIGER-CONGO GROUP, IS BASED ON THE AUTHOR'S 37 YEARS OF WRITING AND TEACHING EXPERIENCE IN EAST AFRICA. THE STUDY IS INTENDED TO PRESENT THE SWAHILI LANGUAGE IN TERMS OF ITS OWN STRUCTURE, RATHER THAN IN TERMS OF LATIN OR ENGLISH GRAMMARS. A PRELIMINARY SECTION IN PART ONE…

  7. Grammar Learning and Teaching: Time, Tense and Verb

    ERIC Educational Resources Information Center

    Zhuang, Xin

    2010-01-01

    The learning of English tenses and verbs is obviously the major and challenging part of second language learning and acquisition for Chinese students. The paper analyzes the features of simple present tense, simple past tense and verbs in them from the aspect of Sidney Greenbaum and Randolph Quirk's student grammar book as an instructive example.…

  8. Information theory and artificial grammar learning: inferring grammaticality from redundancy.

    PubMed

    Jamieson, Randall K; Nevzorova, Uliana; Lee, Graham; Mewhort, D J K

    2016-03-01

    In artificial grammar learning experiments, participants study strings of letters constructed using a grammar and then sort novel grammatical test exemplars from novel ungrammatical ones. The ability to distinguish grammatical from ungrammatical strings is often taken as evidence that the participants have induced the rules of the grammar. We show that judgements of grammaticality are predicted by the local redundancy of the test strings, not by grammaticality itself. The prediction holds in a transfer test in which test strings involve different letters than the training strings. Local redundancy is usually confounded with grammaticality in stimuli widely used in the literature. The confounding explains why the ability to distinguish grammatical from ungrammatical strings has popularized the idea that participants have induced the rules of the grammar, when they have not. We discuss the judgement of grammaticality task in terms of attribute substitution and pattern goodness. When asked to judge grammaticality (an inaccessible attribute), participants answer an easier question about pattern goodness (an accessible attribute). PMID:25828458

  9. Teachers' Grammar on the Electronic Highway: Design Criteria for "Telegram."

    ERIC Educational Resources Information Center

    Wu, Kamyin; Tsui, Amy B. M.

    1997-01-01

    Discusses the rationale and criteria for developing "Telegram," an electronic grammar database for English-as-a- Second-Language teachers in Hong Kong. Describes the importance of explicit grammatical knowledge in effective language teaching, and describes the design criteria for "Telegram," which aims to provide a body of content knowledge and…

  10. Grammar Review: Your Tool for Success. Teacher Materials.

    ERIC Educational Resources Information Center

    Pittsburgh Univ., Johnstown, PA. Education Div.

    Teacher materials are provided for a computer-assisted English grammar curriculum for adult basic education students (1-8 grade level). They accompany a software program (diskette) that the student is able to use by himself/herself with the Apple IIc or Apple IIe computer with single or double drive and a monitor or a television with an R.F.…

  11. "Fire Your Proofreader!" Grammar Correction in the Writing Classroom

    ERIC Educational Resources Information Center

    Shin, Sang-Keun

    2008-01-01

    This article critically reviews the usefulness of grammar correction in second language writing instruction through the eyes of five second-language writers. It first examines the validity of four teaching principles that appear to influence how writing instructors approach error correction in classrooms and concludes with discussions as to why…

  12. Offline grammar-based recognition of handwritten sentences.

    PubMed

    Zimmermann, Matthias; Chappelier, Jean-Cédric; Bunke, Horst

    2006-05-01

    This paper proposes a sequential coupling of a Hidden Markov Model (HMM) recognizer for offline handwritten English sentences with a probabilistic bottom-up chart parser using Stochastic Context-Free Grammars (SCFG) extracted from a text corpus. Based on extensive experiments, we conclude that syntax analysis helps to improve recognition rates significantly.

  13. Making Meaning with Grammar: A Repertoire of Possibilities

    ERIC Educational Resources Information Center

    Myhill, Debra; Lines, Helen; Watson, Annabel

    2012-01-01

    The place of grammar in an English or literacy curriculum has long been a source of debate, one in which professionals, politicians and the public have often engaged with unbridled enthusiasm. As such, the debate has sometimes been characterised more by ideology or polemic, than by intellectual engagement with the core ideas. In part, this is…

  14. THE ACQUISITION OF SPANISH GRAMMAR BY MEXICAN CHILDREN.

    ERIC Educational Resources Information Center

    BLOUNT, B.G.; KERNAN, KEITH T.

    USING THE METHODOLOGY DEVISED BY JEAN BERKO (1958) TO TEST AMERICAN CHILDREN ON THEIR INTERNALIZATION OF ENGLISH GRAMMATICAL RULES, 92 MEXICAN CHILDREN OF CIUDAD GUZMAN, JALISCO, WERE TESTED TO DETERMINE THEIR INTERNALIZATION OF SPANISH GRAMMAR. THE CHILDREN WERE FROM THE LOWER SOCIO-ECONOMIC CLASS, AS WERE THE 18 ADULTS WHO TOOK THE SAME TEST TO…

  15. Ewe (for Togo): Grammar Handbook. Peace Corps Language Handbook Series.

    ERIC Educational Resources Information Center

    Kozelka, Paul R.

    This handbook is composed of: (1) 20 grammar lessons; (2) an introduction to the handbook and to the Ewe language; (3) an appendix presenting the most important differences between Ewe and Mina, the lingua franca in the capital and in markets, offices, and work-sites throughout Togo; (4) answers to written summary exercises; (5) an Ewe-English…

  16. Grammar, Meaning and Pragmatics: Sorting out the Muddle

    ERIC Educational Resources Information Center

    Swan, Michael

    2007-01-01

    The term "pragmatics" is commonly used in two quite different senses. In linguistic discourse, "pragmatics" refers to the strategies (exploitation of shared knowledge, assumptions about communicative intent, etc.), by which language users relate the dictionary/grammar meaning of utterances to their communicative value in…

  17. Referential Markers and Agreement Markers in Functional Discourse Grammar

    ERIC Educational Resources Information Center

    Hengeveld, Kees

    2012-01-01

    It follows from the ordering principles that are applied in Functional Discourse Grammar that the positional possibilities of markers of agreement and those of cross-reference are different. Markers of cross reference are predicted to occur closer to the verb stem, while markers of agreement would occupy peripheral positions. This paper tests…

  18. A Computer Program for Testing Grammars On-Line.

    ERIC Educational Resources Information Center

    Gross, Louis N.

    This paper describes a computer system which is intended to aid the linguist in building a transformational grammar. The program operates as a rule tester, performing three services for the user through sets of functions which allow the user to--specify, change, and print base trees (to which transformations would apply); define transformations…

  19. Language Development: Form and Function in Emerging Grammars.

    ERIC Educational Resources Information Center

    Bloom, Lois Masket

    The research reported is part of an investigation into the acquisition of grammar, using nonlinguistic information from situational and behavioral context to analyze the development of linguistic expression. Three children were seen for approximately 8 hours, every 6 weeks, in their homes, from the age of 19 months--soon after the earliest…

  20. Do Null Subjects (Mis-)Trigger Pro-Drop Grammars?

    ERIC Educational Resources Information Center

    Frazier, Lyn

    2015-01-01

    Native speakers of English regularly hear sentences without overt subjects. Nevertheless, they maintain a [[superscript -]pro] grammar that requires sentences to have an overt subject. It is proposed that listeners of English recognize that speakers reduce predictable material and thus attribute null subjects to this process, rather than changing…

  1. Program Evaluation: English Grammar in the Language Classroom

    ERIC Educational Resources Information Center

    Azimi, Mozhgan

    2014-01-01

    The present study wants to find out the reasons for choosing the current methods/techniques for teaching grammar and it also wants to investigate whether there is a relation between teachers' thinking and their actions in the class or not. For this reason, four language teachers were selected. The subjects were selected by non-random sampling.…

  2. A Reference Grammar of Japanese. Yale Linguistic Series.

    ERIC Educational Resources Information Center

    Martin, Samuel E.

    This reference grammar of Japanese is divided into thirty-one major sections: (1) notational conventions, including spelling, punctuation, accent, and juncture; (2) sentence construction: nuclear sentences and expanded sentences; (3) predicate adjuncts; (4) expansion constraints and noun subcategorization; (5) voice conversions; (6) nuclear focus…

  3. Language Dictionaries and Grammars of Guam and Micronesia.

    ERIC Educational Resources Information Center

    Goetzfridt, Nicholas J.; Goniwiecha, Mark C.

    The study of language reference materials, particularly dictionaries and grammar works, for languages of Guam and Micronesia includes a brief history of their evolution and an annotated bibliography. An introductory section describes the geographic situation of Micronesia and chronicles numerous periods of foreign influence: Spanish Colonization…

  4. Topological structure of dictionary graphs

    NASA Astrophysics Data System (ADS)

    Fukś, Henryk; Krzemiński, Mark

    2009-09-01

    We investigate the topological structure of the subgraphs of dictionary graphs constructed from WordNet and Moby thesaurus data. In the process of learning a foreign language, the learner knows only a subset of all words of the language, corresponding to a subgraph of a dictionary graph. When this subgraph grows with time, its topological properties change. We introduce the notion of the pseudocore and argue that the growth of the vocabulary roughly follows decreasing pseudocore numbers—that is, one first learns words with a high pseudocore number followed by smaller pseudocores. We also propose an alternative strategy for vocabulary growth, involving decreasing core numbers as opposed to pseudocore numbers. We find that as the core or pseudocore grows in size, the clustering coefficient first decreases, then reaches a minimum and starts increasing again. The minimum occurs when the vocabulary reaches a size between 103 and 104. A simple model exhibiting similar behavior is proposed. The model is based on a generalized geometric random graph. Possible implications for language learning are discussed.

  5. Helping Students Make Sense of Graphs: An Experimental Trial of SmartGraphs Software

    NASA Astrophysics Data System (ADS)

    Zucker, Andrew; Kay, Rachel; Staudt, Carolyn

    2014-06-01

    Graphs are commonly used in science, mathematics, and social sciences to convey important concepts; yet students at all ages demonstrate difficulties interpreting graphs. This paper reports on an experimental study of free, Web-based software called SmartGraphs that is specifically designed to help students overcome their misconceptions regarding graphs. SmartGraphs allows students to interact with graphs and provides hints and scaffolding to help students, if they need help. SmartGraphs activities can be authored to be useful in teaching and learning a variety of topics that use graphs (such as slope, velocity, half-life, and global warming). A 2-year experimental study in physical science classrooms was conducted with dozens of teachers and thousands of students. In the first year, teachers were randomly assigned to experimental or control conditions. Data show that students of teachers who use SmartGraphs as a supplement to normal instruction make greater gains understanding graphs than control students studying the same content using the same textbooks, but without SmartGraphs. Additionally, teachers believe that the SmartGraphs activities help students meet learning goals in the physical science course, and a great majority reported they would use the activities with students again. In the second year of the study, several specific variations of SmartGraphs were researched to help determine what makes SmartGraphs effective.

  6. Combinatorial structure of k-semiprimitive matrix families

    NASA Astrophysics Data System (ADS)

    Al'pin, Yu A.; Al'pina, V. S.

    2016-05-01

    Protasov's Theorem on the combinatorial structure of k-primitive families of non-negative matrices is generalized to k-semiprimitive matrix families. The main tool is the binary relation of colour compatibility on the vertices of the coloured graph of the matrix family. Bibliography: 14 titles.

  7. Computational Genomics Using Graph Theory

    NASA Astrophysics Data System (ADS)

    Schlick, Tamar

    2005-03-01

    With exciting new discoveries concerning RNA's regulatory cellular roles in gene expression, structural and functional problems associated with DNA's venerable cousin have come to the forefront. RNA folding, for example, is analogous to the well-known protein folding problem, and seeks to link RNA's primary sequence with secondary and tertiary structures. As a single-stranded polynucleotide, RNA's secondary structures are defined by a network of hydrogen bonds, which lead to a variety of stems, loops, junctions, bulges, and other motifs. Supersecondary pseudoknot structures can also occur and, together, lead to RNA's complex tertiary interactions stabilized by salt and solvent ions in the natural cellular milieu. Besides folding, challenges in RNA research include identifying locations and functions of RNA genes, discovering RNA's structural repertoire (folding motifs), designing novel RNAs, and developing new antiviral and antibiotic compounds composed of, or targeting, RNAs. In this talk, I will describe some of these new biological findings concerning RNA and present an approach using graph theory (network theory) to represent RNA secondary structures. Because the RNA motif space using graphs is vastly smaller than RNA's sequence space, many problems related to analyzing and discovering new RNAs can be simplified and studied systematically. Some preliminary applications to designing novel RNAs will also be described.Related ReadingH. H. Gan, S. Pasquali, and T. Schlick, ``A Survey of Existing RNAs using Graph Theory with Implications to RNA Analysis and Design,'' Nuc. Acids Res. 31: 2926--2943 (2003). J. Zorn, H. H. Gan, N. Shiffeldrim, and T. Schlick, ``Structural Motifs in Ribosomal RNAs: Implications for RNA Design and Genomics,'' Biopolymers 73: 340--347 (2004). H. H. Gan, D. Fera, J. Zorn, M. Tang, N. Shiffeldrim, U. Laserson, N. Kim, and T. Schlick,``RAG: RNA-As-Graphs Database -- Concepts, Analysis, and Features,'' Bioinformatics 20: 1285--1291 (2004). U

  8. Linguistic Grammar Learning and DRD2-TAQ-IA Polymorphism

    PubMed Central

    Wong, Patrick C. M.; Ettlinger, Marc; Zheng, Jing

    2013-01-01

    As research into the neurobiology of language has focused primarily on the systems level, fewer studies have examined the link between molecular genetics and normal variations in language functions. Because the ability to learn a language varies in adults and our genetic codes also vary, research linking the two provides a unique window into the molecular neurobiology of language. We consider a candidate association between the dopamine receptor D2 gene (DRD2) and linguistic grammar learning. DRD2-TAQ-IA polymorphism (rs1800497) is associated with dopamine receptor D2 distribution and dopamine impact in the human striatum, such that A1 allele carriers show reduction in D2 receptor binding relative to carriers who are homozygous for the A2 allele. The individual differences in grammatical rule learning that are particularly prevalent in adulthood are also associated with striatal function and its role in domain-general procedural memory. Therefore, we reasoned that procedurally-based grammar learning could be associated with DRD2-TAQ-IA polymorphism. Here, English-speaking adults learned artificial concatenative and analogical grammars, which have been respectively associated with procedural and declarative memory. Language learning capabilities were tested while learners’ neural hemodynamic responses were simultaneously measured by fMRI. Behavioral learning and brain activation data were subsequently compared with the learners’ DRD2 (rs1800497) genotype. Learners who were homozygous for the A2 allele were better at concatenative (but not analogical) grammar learning and had higher striatal responses relative to those who have at least one A1 allele. These results provide preliminary evidence for the neurogenetic basis of normal variations in linguistic grammar learning and its link to domain-general functions. PMID:23741438

  9. Linguistic grammar learning and DRD2-TAQ-IA polymorphism.

    PubMed

    Wong, Patrick C M; Ettlinger, Marc; Zheng, Jing

    2013-01-01

    As research into the neurobiology of language has focused primarily on the systems level, fewer studies have examined the link between molecular genetics and normal variations in language functions. Because the ability to learn a language varies in adults and our genetic codes also vary, research linking the two provides a unique window into the molecular neurobiology of language. We consider a candidate association between the dopamine receptor D2 gene (DRD2) and linguistic grammar learning. DRD2-TAQ-IA polymorphism (rs1800497) is associated with dopamine receptor D2 distribution and dopamine impact in the human striatum, such that A1 allele carriers show reduction in D2 receptor binding relative to carriers who are homozygous for the A2 allele. The individual differences in grammatical rule learning that are particularly prevalent in adulthood are also associated with striatal function and its role in domain-general procedural memory. Therefore, we reasoned that procedurally-based grammar learning could be associated with DRD2-TAQ-IA polymorphism. Here, English-speaking adults learned artificial concatenative and analogical grammars, which have been respectively associated with procedural and declarative memory. Language learning capabilities were tested while learners' neural hemodynamic responses were simultaneously measured by fMRI. Behavioral learning and brain activation data were subsequently compared with the learners' DRD2 (rs1800497) genotype. Learners who were homozygous for the A2 allele were better at concatenative (but not analogical) grammar learning and had higher striatal responses relative to those who have at least one A1 allele. These results provide preliminary evidence for the neurogenetic basis of normal variations in linguistic grammar learning and its link to domain-general functions.

  10. What exactly is Universal Grammar, and has anyone seen it?

    PubMed

    Dąbrowska, Ewa

    2015-01-01

    Universal Grammar (UG) is a suspect concept. There is little agreement on what exactly is in it; and the empirical evidence for it is very weak. This paper critically examines a variety of arguments that have been put forward as evidence for UG, focussing on the three most powerful ones: universality (all human languages share a number of properties), convergence (all language learners converge on the same grammar in spite of the fact that they are exposed to different input), and poverty of the stimulus (children know things about language which they could not have learned from the input available to them). I argue that these arguments are based on premises which are either false or unsubstantiated. Languages differ from each other in profound ways, and there are very few true universals, so the fundamental crosslinguistic fact that needs explaining is diversity, not universality. A number of recent studies have demonstrated the existence of considerable differences in adult native speakers' knowledge of the grammar of their language, including aspects of inflectional morphology, passives, quantifiers, and a variety of more complex constructions, so learners do not in fact converge on the same grammar. Finally, the poverty of the stimulus argument presupposes that children acquire linguistic representations of the kind postulated by generative grammarians; constructionist grammars such as those proposed by Tomasello, Goldberg and others can be learned from the input. We are the only species that has language, so there must be something unique about humans that makes language learning possible. The extent of crosslinguistic diversity and the considerable individual differences in the rate, style and outcome of acquisition suggest that it is more promising to think in terms of a language-making capacity, i.e., a set of domain-general abilities, rather than an innate body of knowledge about the structural properties of the target system.

  11. What exactly is Universal Grammar, and has anyone seen it?

    PubMed Central

    Dąbrowska, Ewa

    2015-01-01

    Universal Grammar (UG) is a suspect concept. There is little agreement on what exactly is in it; and the empirical evidence for it is very weak. This paper critically examines a variety of arguments that have been put forward as evidence for UG, focussing on the three most powerful ones: universality (all human languages share a number of properties), convergence (all language learners converge on the same grammar in spite of the fact that they are exposed to different input), and poverty of the stimulus (children know things about language which they could not have learned from the input available to them). I argue that these arguments are based on premises which are either false or unsubstantiated. Languages differ from each other in profound ways, and there are very few true universals, so the fundamental crosslinguistic fact that needs explaining is diversity, not universality. A number of recent studies have demonstrated the existence of considerable differences in adult native speakers’ knowledge of the grammar of their language, including aspects of inflectional morphology, passives, quantifiers, and a variety of more complex constructions, so learners do not in fact converge on the same grammar. Finally, the poverty of the stimulus argument presupposes that children acquire linguistic representations of the kind postulated by generative grammarians; constructionist grammars such as those proposed by Tomasello, Goldberg and others can be learned from the input. We are the only species that has language, so there must be something unique about humans that makes language learning possible. The extent of crosslinguistic diversity and the considerable individual differences in the rate, style and outcome of acquisition suggest that it is more promising to think in terms of a language-making capacity, i.e., a set of domain-general abilities, rather than an innate body of knowledge about the structural properties of the target system. PMID:26157406

  12. What exactly is Universal Grammar, and has anyone seen it?

    PubMed

    Dąbrowska, Ewa

    2015-01-01

    Universal Grammar (UG) is a suspect concept. There is little agreement on what exactly is in it; and the empirical evidence for it is very weak. This paper critically examines a variety of arguments that have been put forward as evidence for UG, focussing on the three most powerful ones: universality (all human languages share a number of properties), convergence (all language learners converge on the same grammar in spite of the fact that they are exposed to different input), and poverty of the stimulus (children know things about language which they could not have learned from the input available to them). I argue that these arguments are based on premises which are either false or unsubstantiated. Languages differ from each other in profound ways, and there are very few true universals, so the fundamental crosslinguistic fact that needs explaining is diversity, not universality. A number of recent studies have demonstrated the existence of considerable differences in adult native speakers' knowledge of the grammar of their language, including aspects of inflectional morphology, passives, quantifiers, and a variety of more complex constructions, so learners do not in fact converge on the same grammar. Finally, the poverty of the stimulus argument presupposes that children acquire linguistic representations of the kind postulated by generative grammarians; constructionist grammars such as those proposed by Tomasello, Goldberg and others can be learned from the input. We are the only species that has language, so there must be something unique about humans that makes language learning possible. The extent of crosslinguistic diversity and the considerable individual differences in the rate, style and outcome of acquisition suggest that it is more promising to think in terms of a language-making capacity, i.e., a set of domain-general abilities, rather than an innate body of knowledge about the structural properties of the target system. PMID:26157406

  13. Linguistic grammar learning and DRD2-TAQ-IA polymorphism.

    PubMed

    Wong, Patrick C M; Ettlinger, Marc; Zheng, Jing

    2013-01-01

    As research into the neurobiology of language has focused primarily on the systems level, fewer studies have examined the link between molecular genetics and normal variations in language functions. Because the ability to learn a language varies in adults and our genetic codes also vary, research linking the two provides a unique window into the molecular neurobiology of language. We consider a candidate association between the dopamine receptor D2 gene (DRD2) and linguistic grammar learning. DRD2-TAQ-IA polymorphism (rs1800497) is associated with dopamine receptor D2 distribution and dopamine impact in the human striatum, such that A1 allele carriers show reduction in D2 receptor binding relative to carriers who are homozygous for the A2 allele. The individual differences in grammatical rule learning that are particularly prevalent in adulthood are also associated with striatal function and its role in domain-general procedural memory. Therefore, we reasoned that procedurally-based grammar learning could be associated with DRD2-TAQ-IA polymorphism. Here, English-speaking adults learned artificial concatenative and analogical grammars, which have been respectively associated with procedural and declarative memory. Language learning capabilities were tested while learners' neural hemodynamic responses were simultaneously measured by fMRI. Behavioral learning and brain activation data were subsequently compared with the learners' DRD2 (rs1800497) genotype. Learners who were homozygous for the A2 allele were better at concatenative (but not analogical) grammar learning and had higher striatal responses relative to those who have at least one A1 allele. These results provide preliminary evidence for the neurogenetic basis of normal variations in linguistic grammar learning and its link to domain-general functions. PMID:23741438

  14. German Grammar in the Students' Words: The "Essentialization" of German Grammar by American College-Level Learners

    ERIC Educational Resources Information Center

    Chavez, Monika

    2011-01-01

    This study of 134 college-level learners of German, enrolled in four years of instruction, showed them to "essentialize" German grammar when asked to describe it to a hypothetical friend. Kubota defined the term essentialization to capture learners' views of the target culture. Its main characteristic is the presupposition of "essential, stable,…

  15. Re-Thinking Grammar: The Impact of Embedded Grammar Teaching on Students' Writing and Students' Metalinguistic Understanding

    ERIC Educational Resources Information Center

    Myhill, Debra A.; Jones, Susan M.; Lines, Helen; Watson, Annabel

    2012-01-01

    This paper reports on a national study, involving a mixed-method research design comprising a randomised controlled trial (RCT), text analysis, student and teacher interviews and lesson observations. It set out to investigate whether contextualised teaching of grammar, linked to the teaching of writing, would improve student outcomes in writing…

  16. Grammar Is the Heart of Language: Grammar and Its Role in Language Learning among Finnish University Students

    ERIC Educational Resources Information Center

    Saaristo, Pekka

    2015-01-01

    This article presents and discusses views on grammar and its role in formal language learning amongst Finnish university students. The results are based on a questionnaire which was distributed to students at the University of Jyväskylä as part of institutional action research. The background to the project was a feeling amongst some teachers of…

  17. Computing Information Value from RDF Graph Properties

    SciTech Connect

    al-Saffar, Sinan; Heileman, Gregory

    2010-11-08

    Information value has been implicitly utilized and mostly non-subjectively computed in information retrieval (IR) systems. We explicitly define and compute the value of an information piece as a function of two parameters, the first is the potential semantic impact the target information can subjectively have on its recipient's world-knowledge, and the second parameter is trust in the information source. We model these two parameters as properties of RDF graphs. Two graphs are constructed, a target graph representing the semantics of the target body of information and a context graph representing the context of the consumer of that information. We compute information value subjectively as a function of both potential change to the context graph (impact) and the overlap between the two graphs (trust). Graph change is computed as a graph edit distance measuring the dissimilarity between the context graph before and after the learning of the target graph. A particular application of this subjective information valuation is in the construction of a personalized ranking component in Web search engines. Based on our method, we construct a Web re-ranking system that personalizes the information experience for the information-consumer.

  18. Components in time-varying graphs

    NASA Astrophysics Data System (ADS)

    Nicosia, Vincenzo; Tang, John; Musolesi, Mirco; Russo, Giovanni; Mascolo, Cecilia; Latora, Vito

    2012-06-01

    Real complex systems are inherently time-varying. Thanks to new communication systems and novel technologies, today it is possible to produce and analyze social and biological networks with detailed information on the time of occurrence and duration of each link. However, standard graph metrics introduced so far in complex network theory are mainly suited for static graphs, i.e., graphs in which the links do not change over time, or graphs built from time-varying systems by aggregating all the links as if they were concurrent in time. In this paper, we extend the notion of connectedness, and the definitions of node and graph components, to the case of time-varying graphs, which are represented as time-ordered sequences of graphs defined over a fixed set of nodes. We show that the problem of finding strongly connected components in a time-varying graph can be mapped into the problem of discovering the maximal-cliques in an opportunely constructed static graph, which we name the affine graph. It is, therefore, an NP-complete problem. As a practical example, we have performed a temporal component analysis of time-varying graphs constructed from three data sets of human interactions. The results show that taking time into account in the definition of graph components allows to capture important features of real systems. In particular, we observe a large variability in the size of node temporal in- and out-components. This is due to intrinsic fluctuations in the activity patterns of individuals, which cannot be detected by static graph analysis.

  19. Components in time-varying graphs.

    PubMed

    Nicosia, Vincenzo; Tang, John; Musolesi, Mirco; Russo, Giovanni; Mascolo, Cecilia; Latora, Vito

    2012-06-01

    Real complex systems are inherently time-varying. Thanks to new communication systems and novel technologies, today it is possible to produce and analyze social and biological networks with detailed information on the time of occurrence and duration of each link. However, standard graph metrics introduced so far in complex network theory are mainly suited for static graphs, i.e., graphs in which the links do not change over time, or graphs built from time-varying systems by aggregating all the links as if they were concurrent in time. In this paper, we extend the notion of connectedness, and the definitions of node and graph components, to the case of time-varying graphs, which are represented as time-ordered sequences of graphs defined over a fixed set of nodes. We show that the problem of finding strongly connected components in a time-varying graph can be mapped into the problem of discovering the maximal-cliques in an opportunely constructed static graph, which we name the affine graph. It is, therefore, an NP-complete problem. As a practical example, we have performed a temporal component analysis of time-varying graphs constructed from three data sets of human interactions. The results show that taking time into account in the definition of graph components allows to capture important features of real systems. In particular, we observe a large variability in the size of node temporal in- and out-components. This is due to intrinsic fluctuations in the activity patterns of individuals, which cannot be detected by static graph analysis. PMID:22757508

  20. JavaGenes: Evolving Graphs with Crossover

    NASA Technical Reports Server (NTRS)

    Globus, Al; Atsatt, Sean; Lawton, John; Wipke, Todd

    2000-01-01

    Genetic algorithms usually use string or tree representations. We have developed a novel crossover operator for a directed and undirected graph representation, and used this operator to evolve molecules and circuits. Unlike strings or trees, a single point in the representation cannot divide every possible graph into two parts, because graphs may contain cycles. Thus, the crossover operator is non-trivial. A steady-state, tournament selection genetic algorithm code (JavaGenes) was written to implement and test the graph crossover operator. All runs were executed by cycle-scavagging on networked workstations using the Condor batch processing system. The JavaGenes code has evolved pharmaceutical drug molecules and simple digital circuits. Results to date suggest that JavaGenes can evolve moderate sized drug molecules and very small circuits in reasonable time. The algorithm has greater difficulty with somewhat larger circuits, suggesting that directed graphs (circuits) are more difficult to evolve than undirected graphs (molecules), although necessary differences in the crossover operator may also explain the results. In principle, JavaGenes should be able to evolve other graph-representable systems, such as transportation networks, metabolic pathways, and computer networks. However, large graphs evolve significantly slower than smaller graphs, presumably because the space-of-all-graphs explodes combinatorially with graph size. Since the representation strongly affects genetic algorithm performance, adding graphs to the evolutionary programmer's bag-of-tricks should be beneficial. Also, since graph evolution operates directly on the phenotype, the genotype-phenotype translation step, common in genetic algorithm work, is eliminated.