Handbook of graph grammars and computing by graph transformation
Engels, G; Kreowski, H J; Rozenberg, G
1999-01-01
Graph grammars originated in the late 60s, motivated by considerations about pattern recognition and compiler construction. Since then, the list of areas which have interacted with the development of graph grammars has grown quite impressively. Besides the aforementioned areas, it includes software specification and development, VLSI layout schemes, database design, modeling of concurrent systems, massively parallel computer architectures, logic programming, computer animation, developmental biology, music composition, visual languages, and many others.The area of graph grammars and graph tran
DEFF Research Database (Denmark)
Greenyer, Joel; Kindler, Ekkart
2010-01-01
and for model-based software engineering approaches in general. QVT (Query/View/Transformation) is the transformation technology recently proposed for this purpose by the OMG. TGGs (Triple Graph Grammars) are another transformation technology proposed in the mid-nineties, used for example in the FUJABA CASE...
Hermann, Frank; Ehrig, Hartmut; Orejas, Fernando; Ulrike, Golas
2010-01-01
Triple Graph Grammars (TGGs) are a well-established concept for the specification of model transformations. In previous work we have formalized and analyzed already crucial properties of model transformations like termination, correctness and completeness, but functional behaviour - especially local confluence - is missing up to now. In order to close this gap we generate forward translation rules, which extend standard forward rules by translation attributes keeping track of the elements whi...
Generic Graph Grammar: A Simple Grammar for Generic Procedural Modelling
DEFF Research Database (Denmark)
Christiansen, Asger Nyman; Bærentzen, Jakob Andreas
2012-01-01
in a directed cyclic graph. Furthermore, the basic productions are chosen such that Generic Graph Grammar seamlessly combines the capabilities of L-systems to imitate biological growth (to model trees, animals, etc.) and those of split grammars to design structured objects (chairs, houses, etc.). This results...
Fundamentals of algebraic graph transformation
Ehrig, Hartmut; Prange, Ulrike; Taentzer, Gabriele
2006-01-01
Graphs are widely used to represent structural information in the form of objects and connections between them. Graph transformation is the rule-based manipulation of graphs, an increasingly important concept in computer science and related fields. This is the first textbook treatment of the algebraic approach to graph transformation, based on algebraic structures and category theory. Part I is an introduction to the classical case of graph and typed graph transformation. In Part II basic and advanced results are first shown for an abstract form of replacement systems, so-called adhesive high-level replacement systems based on category theory, and are then instantiated to several forms of graph and Petri net transformation systems. Part III develops typed attributed graph transformation, a technique of key relevance in the modeling of visual languages and in model transformation. Part IV contains a practical case study on model transformation and a presentation of the AGG (attributed graph grammar) tool envir...
Negotiated Grammar Transformation
V. Zaytsev (Vadim)
2012-01-01
htmlabstractIn this paper, we study controlled adaptability of metamodel transformations. We consider one of the most rigid metamodel transformation formalisms — automated grammar transformation with operator suites, where a transformation script is built in such a way that it is essentially meant
Mapping Between Semantic Graphs and Sentences in Grammar Induction System
Directory of Open Access Journals (Sweden)
Laszlo Kovacs
2010-06-01
Full Text Available The proposed transformation module performs mapping be-
tween two di®erent knowledge representation forms used in grammar induction systems. The kernel knowledge representation form is a special predicate centered conceptual graph called ECG. The ECG provides a semantic-based, language independent description of the environment. The other base representation form is some kind of language. The sentences of the language should meet the corresponding grammatical rules. The pilot project demonstrates the functionality of a translator module using this transformation engine between the ECG graph and the Hungarian language.
Transformational Grammar and Cognitive Psycholinguistics.
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…
Readings in Applied Transformational Grammar.
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…
de Mol, M.J.; Rensink, Arend; Hunt, James J.
This paper introduces an approach for adding graph transformation-based functionality to existing JAVA programs. The approach relies on a set of annotations to identify the intended graph structure, as well as on user methods to manipulate that structure, within the user’s own JAVA class
Graph Grammar-Based Multi-Frontal Parallel Direct Solver for Two-Dimensional Isogeometric Analysis
Kuźnik, Krzysztof; Paszyński, Maciej; Calo, Victor M.
2012-01-01
at parent nodes and eliminates rows corresponding to fully assembled degrees of freedom. Finally, there are graph grammar productions responsible for root problem solution and recursive backward substitutions. Expressing the solver algorithm by graph grammar
Graph transformation tool contest 2008
Rensink, Arend; van Gorp, Pieter
This special section is the outcome of the graph transformation tool contest organised during the Graph-Based Tools (GraBaTs) 2008 workshop, which took place as a satellite event of the International Conference on Graph Transformation (ICGT) 2008. The contest involved two parts: three “off-line case
An approach to multiscale modelling with graph grammars.
Ong, Yongzhi; Streit, Katarína; Henke, Michael; Kurth, Winfried
2014-09-01
Functional-structural plant models (FSPMs) simulate biological processes at different spatial scales. Methods exist for multiscale data representation and modification, but the advantages of using multiple scales in the dynamic aspects of FSPMs remain unclear. Results from multiscale models in various other areas of science that share fundamental modelling issues with FSPMs suggest that potential advantages do exist, and this study therefore aims to introduce an approach to multiscale modelling in FSPMs. A three-part graph data structure and grammar is revisited, and presented with a conceptual framework for multiscale modelling. The framework is used for identifying roles, categorizing and describing scale-to-scale interactions, thus allowing alternative approaches to model development as opposed to correlation-based modelling at a single scale. Reverse information flow (from macro- to micro-scale) is catered for in the framework. The methods are implemented within the programming language XL. Three example models are implemented using the proposed multiscale graph model and framework. The first illustrates the fundamental usage of the graph data structure and grammar, the second uses probabilistic modelling for organs at the fine scale in order to derive crown growth, and the third combines multiscale plant topology with ozone trends and metabolic network simulations in order to model juvenile beech stands under exposure to a toxic trace gas. The graph data structure supports data representation and grammar operations at multiple scales. The results demonstrate that multiscale modelling is a viable method in FSPM and an alternative to correlation-based modelling. Advantages and disadvantages of multiscale modelling are illustrated by comparisons with single-scale implementations, leading to motivations for further research in sensitivity analysis and run-time efficiency for these models.
Graph Creation, Visualisation and Transformation
Directory of Open Access Journals (Sweden)
Maribel Fernández
2010-03-01
Full Text Available We describe a tool to create, edit, visualise and compute with interaction nets - a form of graph rewriting systems. The editor, called GraphPaper, allows users to create and edit graphs and their transformation rules using an intuitive user interface. The editor uses the functionalities of the TULIP system, which gives us access to a wealth of visualisation algorithms. Interaction nets are not only a formalism for the specification of graphs, but also a rewrite-based computation model. We discuss graph rewriting strategies and a language to express them in order to perform strategic interaction net rewriting.
Conceptual graph grammar--a simple formalism for sublanguage.
Johnson, S B
1998-11-01
There are a wide variety of computer applications that deal with various aspects of medical language: concept representation, controlled vocabulary, natural language processing, and information retrieval. While technical and theoretical methods appear to differ, all approaches investigate different aspects of the same phenomenon: medical sublanguage. This paper surveys the properties of medical sublanguage from a formal perspective, based on detailed analyses cited in the literature. A review of several computer systems based on sublanguage approaches shows some of the difficulties in addressing the interaction between the syntactic and semantic aspects of sublanguage. A formalism called Conceptual Graph Grammar is presented that attempts to combine both syntax and semantics into a single notation by extending standard Conceptual Graph notation. Examples from the domain of pathology diagnoses are provided to illustrate the use of this formalism in medical language analysis. The strengths and weaknesses of the approach are then considered. Conceptual Graph Grammar is an attempt to synthesize the common properties of different approaches to sublanguage into a single formalism, and to begin to define a common foundation for language-related research in medical informatics.
A Solution to the Flowgraphs Case Study using Triple Graph Grammars and eMoflon
Directory of Open Access Journals (Sweden)
Anthony Anjorin
2013-11-01
Full Text Available After 20 years of Triple Graph Grammars (TGGs and numerous actively maintained implementations, there is now a need for challenging examples and success stories to show that TGGs can be used for real-world bidirectional model transformations. Our primary goal in recent years has been to increase the expressiveness of TGGs by providing a set of pragmatic features that allow a controlled fallback to programmed graph transformations and Java. Based on the Flowgraphs case study of the Transformation Tool Contest (TTC 2013, we present (i attribute constraints used to express complex bidirectional attribute manipulation, (ii binding expressions for specifying arbitrary context relationships, and (iii post-processing methods as a black box extension for TGG rules. In each case, we discuss the enabled trade-off between guaranteed formal properties and expressiveness. Our solution, implemented with our metamodelling and model transformation tool eMoflon (www.emoflon.org, is available as a virtual machine hosted on Share.
Generative Graph Grammar of Neo-Vaiśeṣika Formal Ontology (NVFO)
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.
Recent Developments in Transformational Grammar.
Jacobs, Roderick A.
1969-01-01
In the years following the appearance of Noam Chomsky's book, "Syntactic Structures," in 1957, transformational grammarians modified and improved his initial model of language. The notion of a deep structure of meaning underlying a sentence's surface structure was revised to embody elements representing negation, command, and interrogation, and to…
Graph Transformation Semantics for a QVT Language
Rensink, Arend; Nederpel, Ronald; Bruni, Roberto; Varró, Dániel
It has been claimed by many in the graph transformation community that model transformation, as understood in the context of Model Driven Architecture, can be seen as an application of graph transformation. In this paper we substantiate this claim by giving a graph transformation-based semantics to
Lee, Kyu J.; Kunii, T. L.; Noma, T.
1993-01-01
In this paper, we propose a syntactic pattern recognition method for non-schematic drawings, based on a new attributed graph grammar with flexible embedding. In our graph grammar, the embedding rule permits the nodes of a guest graph to be arbitrarily connected with the nodes of a host graph. The ambiguity caused by this flexible embedding is controlled with the evaluation of synthesized attributes and the check of context sensitivity. To integrate parsing with the synthesized attribute evaluation and the context sensitivity check, we also develop a bottom up parsing algorithm.
Graph Grammar-Based Multi-Frontal Parallel Direct Solver for Two-Dimensional Isogeometric Analysis
Kuźnik, Krzysztof
2012-06-02
This paper introduces the graph grammar based model for developing multi-thread multi-frontal parallel direct solver for two dimensional isogeometric finite element method. Execution of the solver algorithm has been expressed as the sequence of graph grammar productions. At the beginning productions construct the elimination tree with leaves corresponding to finite elements. Following sequence of graph grammar productions generates element frontal matri-ces at leaf nodes, merges matrices at parent nodes and eliminates rows corresponding to fully assembled degrees of freedom. Finally, there are graph grammar productions responsible for root problem solution and recursive backward substitutions. Expressing the solver algorithm by graph grammar productions allows us to explore the concurrency of the algorithm. The graph grammar productions are grouped into sets of independent tasks that can be executed concurrently. The resulting concurrent multi-frontal solver algorithm is implemented and tested on NVIDIA GPU, providing O(NlogN) execution time complexity where N is the number of degrees of freedom. We have confirmed this complexity by solving up to 1 million of degrees of freedom with 448 cores GPU.
Improving Control Efficiency of Dynamic Street Lighting by Utilizing the Dual Graph Grammar Concept
Directory of Open Access Journals (Sweden)
Igor Wojnicki
2018-02-01
Full Text Available The paper introduces a definition of dual graph grammar. It enables two graphs to share information in a synchronized way. A smart city example application, which is an outdoor lighting control system utilizing the dual graph grammar, is also demonstrated. The system controls dimming of street lights which is based on traffic intensity. Each luminaire’s light level is adjusted individually to comply with the lighting norms to ensure safety. Benefits of applying the dual graph grammar are twofold. First, it increases expressive power of the mathematical model that the system uses. It becomes possible to take into account complex geographical distribution of sensors and logical dependencies among them. Second, it increases the system’s efficiency by reducing the problem size during run-time. Experimental results show a reduction of the computation time by a factor of 2.8. The approach has been verified in practice.
Chemical Graph Transformation with Stereo-Information
DEFF Research Database (Denmark)
Andersen, Jakob Lykke; Flamm, Christoph; Merkle, Daniel
2017-01-01
Double Pushout graph transformation naturally facilitates the modelling of chemical reactions: labelled undirected graphs model molecules and direct derivations model chemical reactions. However, the most straightforward modelling approach ignores the relative placement of atoms and their neighbo......Double Pushout graph transformation naturally facilitates the modelling of chemical reactions: labelled undirected graphs model molecules and direct derivations model chemical reactions. However, the most straightforward modelling approach ignores the relative placement of atoms...... and their neighbours in space. Stereoisomers of chemical compounds thus cannot be distinguished, even though their chemical activity may differ substantially. In this contribution we propose an extended chemical graph transformation system with attributes that encode information about local geometry. The modelling...... of graph transformation, but we here propose a framework that also allows for partially specified stereoinformation. While there are several stereochemical configurations to be considered, we focus here on the tetrahedral molecular shape, and suggest general principles for how to treat all other chemically...
From LL-regular to LL(1) grammars: Transformations, covers and parsing
Nijholt, Antinus
1982-01-01
In this paper it is shown that it is possible to transform any LL-regular grammar G into an LL(1) grammar G' in such a way that parsing G' is as good as parsing G. That is, a parse of a sentence of grammar G can be obtained with a simple string homomorphism from the parse of a corresponding sentence
Institute of Scientific and Technical Information of China (English)
JeanetteDeCarrico; DianeLarsen-Freeman
2004-01-01
When it comes to definitions of grammar,confusion abounds.One problem is that the word grammar means different things to different people.For many,the term sugges tsa list of do's and don't's,rules that tell us we should say It is I,not It is me,that we should not say ain't,or that weshould avoid ending a sentence with a preposition.For oth
Institute of Scientific and Technical Information of China (English)
JeanetteDecarrico; DianeLarsen-Freeman
2004-01-01
Previous sections have reviewed issues in describing grammar, issues that were mainly concerned with what to describe, how to describe it and how to account for differing approaches and their implications in terms of theory and pedagogy in applied linguistics. But however precise and thorough researchers may attempt to be in addressing these issues, there are certain limitations to descriptions of grammar given in isolation from all other parts of the language system
Graph Transformation for Consolidation of Creativity Sessions Results
DEFF Research Database (Denmark)
Dolog, Peter
2010-01-01
Graph transformation approach for consolidation of creativity sessions results is part of the FP7 EU/IST project idSpace: Tooling of and training for collaborative, distributed product innovation. The goal of graph transformation approach is to provide a tool for merging results of various sessions...... (such as brainstorming sessions), which are represented as graphs, when the session participants- are physically distributed....
Improved Conflict Detection for Graph Transformation with Attributes
Directory of Open Access Journals (Sweden)
Géza Kulcsár
2015-04-01
Full Text Available In graph transformation, a conflict describes a situation where two alternative transformations cannot be arbitrarily serialized. When enriching graphs with attributes, existing conflict detection techniques typically report a conflict whenever at least one of two transformations manipulates a shared attribute. In this paper, we propose an improved, less conservative condition for static conflict detection of graph transformation with attributes by explicitly taking the semantics of the attribute operations into account. The proposed technique is based on symbolic graphs, which extend the traditional notion of graphs by logic formulas used for attribute handling. The approach is proven complete, i.e., any potential conflict is guaranteed to be detected.
Engineering Object-Oriented Semantics Using Graph Transformations
Kastenberg, H.; Kleppe, A.G.; Rensink, Arend
In this paper we describe the application of the theory of graph transformations to the practise of language design. We have defined the semantics of a small but realistic object-oriented language (called TAAL) by mapping the language constructs to graphs and their operational semantics to graph
Parameterized Verification of Graph Transformation Systems with Whole Neighbourhood Operations
Delzanno, Giorgio; Stückrath, Jan
2014-01-01
We introduce a new class of graph transformation systems in which rewrite rules can be guarded by universally quantified conditions on the neighbourhood of nodes. These conditions are defined via special graph patterns which may be transformed by the rule as well. For the new class for graph rewrite rules, we provide a symbolic procedure working on minimal representations of upward closed sets of configurations. We prove correctness and effectiveness of the procedure by a categorical presenta...
Proving termination of graph transformation systems using weighted type graphs over semirings
Bruggink, H.J.S.; König, B.; Nolte, D.; Zantema, H.; Parisi-Presicce, F.; Westfechtel, B.
2015-01-01
We introduce techniques for proving uniform termination of graph transformation systems, based on matrix interpretations for string rewriting. We generalize this technique by adapting it to graph rewriting instead of string rewriting and by generalizing to ordered semirings. In this way we obtain a
Transformation of UML models to CSP : a case study for graph transformation tools
Varró, D.; Asztalos, M.; Bisztray, D.; Boronat, A.; Dang, D.; Geiß, R.; Greenyer, J.; Van Gorp, P.M.E.; Kniemeyer, O.; Narayanan, A.; Rencis, E.; Weinell, E.; Schürr, A.; Nagl, M.; Zündorf, A.
2008-01-01
Graph transformation provides an intuitive mechanism for capturing model transformations. In the current paper, we investigate and compare various graph transformation tools using a compact practical model transformation case study carried out as part of the AGTIVE 2007 Tool Contest [22]. The aim of
Understanding the Models of Grammar
Mahaputri, Ratna Andhika
2013-01-01
This article provides comprehensive explanation about several models of grammar. The first model of grammar which is explained is considered from the functional grammar and associated with the American linguist Noam Chomsky that is Transformational Grammar. This model of grammar is consisted of three components they are phrase structure rule, the lexicon, and transformation. The second model of grammar which is explained in this article is Minimalist Grammar. This article also compares her...
Rose, L.M.; Herrmannsdoerfer, M.; Mazanek, S.; Van Gorp, P.M.E.; Buchwald, S.; Horn, T.; Kalnina, E.; Koch, A.; Lano, K.; Schätz, B.; Wimmer, M.
2014-01-01
We describe the results of the Transformation Tool Contest 2010 workshop, in which nine graph and model transformation tools were compared for specifying model migration. The model migration problem—migration of UML activity diagrams from version 1.4 to version 2.2—is non-trivial and practically
Clone Detection for Graph-Based Model Transformation Languages
DEFF Research Database (Denmark)
Strüber, Daniel; Plöger, Jennifer; Acretoaie, Vlad
2016-01-01
and analytical quality assurance. From these use cases, we derive a set of key requirements. We describe our customization of existing model clone detection techniques allowing us to address these requirements. Finally, we provide an experimental evaluation, indicating that our customization of ConQAT, one......Cloning is a convenient mechanism to enable reuse across and within software artifacts. On the downside, it is also a practice related to significant long-term maintainability impediments, thus generating a need to identify clones in affected artifacts. A large variety of clone detection techniques...... has been proposed for programming and modeling languages; yet no specific ones have emerged for model transformation languages. In this paper, we explore clone detection for graph-based model transformation languages. We introduce potential use cases for such techniques in the context of constructive...
Vector grammars and PN machines
Institute of Scientific and Technical Information of China (English)
蒋昌俊
1996-01-01
The concept of vector grammars under the string semantic is introduced.The dass of vector grammars is given,which is similar to the dass of Chomsky grammars.The regular vector grammar is divided further.The strong and weak relation between the vector grammar and scalar grammar is discussed,so the spectrum system graph of scalar and vector grammars is made.The equivalent relation between the regular vector grammar and Petri nets (also called PN machine) is pointed.The hybrid PN machine is introduced,and its language is proved equivalent to the language of the context-free vector grammar.So the perfect relation structure between vector grammars and PN machines is formed.
Directory of Open Access Journals (Sweden)
Sarunya Kanjanawattana
2017-07-01
Full Text Available Image classification plays a vital role in many areas of study, such as data mining and image processing; however, serious problems collectively referred to as the course of dimensionality have been encountered in previous studies as factors that reduce system performance. Furthermore, we also confront the problem of different graph characteristics even if graphs belong to same types. In this study, we propose a novel method of graph-type classification. Using our approach, we open up a new solution of high-dimensional images and address problems of different characteristics by converting graph images to one dimension with a discrete Fourier transformation and creating numeric datasets using wavelet and Hough transformations. Moreover, we introduce a new classifier, which is a combination between artificial neuron networks (ANNs and support vector machines (SVMs, which we call ANNSVM, to enhance accuracy. The objectives of our study are to propose an effective graph-type classification method that includes finding a new data representative used for classification instead of two-dimensional images and to investigate what features make our data separable. To evaluate the method of our study, we conducted five experiments with different methods and datasets. The input dataset we focused on was a numeric dataset containing wavelet coefficients and outputs of a Hough transformation. From our experimental results, we observed that the highest accuracy was provided using our method with Coiflet 1, which achieved a 0.91 accuracy.
Transformation Strategies between Block-Oriented and Graph-Oriented Process Modelling Languages
DEFF Research Database (Denmark)
Mendling, Jan; Lassen, Kristian Bisgaard; Zdun, Uwe
2006-01-01
Much recent research work discusses the transformation between different process modelling languages. This work, however, is mainly focussed on specific process modelling languages, and thus the general reusability of the applied transformation concepts is rather limited. In this paper, we aim...... to abstract from concrete transformation strategies by distinguishing two major paradigms for representing control flow in process modelling languages: block-oriented languages (such as BPEL and BPML) and graph-oriented languages (such as EPCs and YAWL). The contribution of this paper are generic strategies...... for transforming from block-oriented process languages to graph-oriented languages, and vice versa....
Generalising tree traversals and tree transformations to DAGs
DEFF Research Database (Denmark)
Bahr, Patrick; Axelsson, Emil
2017-01-01
We present a recursion scheme based on attribute grammars that can be transparently applied to trees and acyclic graphs. Our recursion scheme allows the programmer to implement a tree traversal or a tree transformation and then apply it to compact graph representations of trees instead. The resul......We present a recursion scheme based on attribute grammars that can be transparently applied to trees and acyclic graphs. Our recursion scheme allows the programmer to implement a tree traversal or a tree transformation and then apply it to compact graph representations of trees instead...... as the complementing theory with a number of examples....
Strictness Analysis for Attribute Grammars
DEFF Research Database (Denmark)
Rosendahl, Mads
1992-01-01
interpretation of attribute grammars. The framework is used to construct a strictness analysis for attribute grammars. Results of the analysis enable us to transform an attribute grammar such that attributes are evaluated during parsing, if possible. The analysis is proved correct by relating it to a fixpoint...... semantics for attribute grammars. An implementation of the analysis is discussed and some extensions to the analysis are mentioned....
Transformation Strategies between Block-Oriented and Graph-Oriented Process Modelling Languages
DEFF Research Database (Denmark)
Mendling, Jan; Lassen, Kristian Bisgaard; Zdun, Uwe
to abstract from concrete transformationstrategies by distinguishing two major paradigms for process modelling languages:block-oriented languages (such as BPEL and BPML) and graph-oriented languages(such as EPCs and YAWL). The contribution of this paper are generic strategiesfor transforming from block......Much recent research work discusses the transformation between differentprocess modelling languages. This work, however, is mainly focussed on specific processmodelling languages, and thus the general reusability of the applied transformationconcepts is rather limited. In this paper, we aim......-oriented process languages to graph-oriented languages,and vice versa. We also present two case studies of applying our strategies....
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…
Modelling and analysis of distributed simulation protocols with distributed graph transformation
Lara, Juan de; Taentzer, Gabriele
2005-01-01
Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. J. de Lara, and G. Taentzer, "Modelling and analysis of distributed simulation protocols with distributed graph transformation...
DEFF Research Database (Denmark)
Christiansen, Henning
2005-01-01
A grammar formalism based upon CHR is proposed analogously to the way Definite Clause Grammars are defined and implemented on top of Prolog. These grammars execute as robust bottom-up parsers with an inherent treatment of ambiguity and a high flexibility to model various linguistic phenomena....... The formalism extends previous logic programming based grammars with a form of context-sensitive rules and the possibility to include extra-grammatical hypotheses in both head and body of grammar rules. Among the applications are straightforward implementations of Assumption Grammars and abduction under...... integrity constraints for language analysis. CHR grammars appear as a powerful tool for specification and implementation of language processors and may be proposed as a new standard for bottom-up grammars in logic programming....
DEFF Research Database (Denmark)
Christiansen, Henning
A grammar formalism based upon CHR is proposed analogously to the way Definite Clause Grammars are defined and implemented on top of Prolog. These grammars execute as robust bottom-up parsers with an inherent treatment of ambiguity and a high flexibility to model various linguistic phenomena....... The formalism extends previous logic programming based grammars with a form of context-sensitive rules and the possibility to include extra-grammatical hypotheses in both head and body of grammar rules. Among the applications are straightforward implementations of Assumption Grammars and abduction under...... integrity constraints for language analysis. CHR grammars appear as a powerful tool for specification and implementation of language processors and may be proposed as a new standard for bottom-up grammars in logic programming....
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.
English Grammar Comparison:Descriptive Grammar vs. Prescriptive Grammar
Institute of Scientific and Technical Information of China (English)
ZHANG Jing-wen; LI Yi-an
2015-01-01
English grammar is thought as one of the most important parts in both language learning and teaching. While few peo⁃ple know there is more than one kind of English grammar. This essay provides the features and comparison between two com⁃monly used English grammar, namely descriptive grammar and prescriptive grammar, and assist English teachers to explore further in grammar teaching.
Style representation in design grammars
DEFF Research Database (Denmark)
Ahmad, Sumbul; Chase, Scott Curland
2012-01-01
The concept of style is relevant for both the analysis and synthesis of designs. New styles are often formed by the adaptation of previous ones based on changes in design criteria and context. A formal characterization of style is given by shape grammars, which describe the compositional rules...... underlying a set of designs. Stylistic change can be modelled by grammar transformations, which allow the transformation of the structure and vocabulary of a grammar that is used to describe a particular style. In order for grammars to be useful beyond a single application, they should have the capability...... to be transformed according to changing design style needs. Issues of formalizing stylistic change necessitate a lucid and formal definition of style in the design language generated by a grammar. Furthermore, a significant aspect of the definition of style is the representation of aesthetic qualities attributed...
Institute of Scientific and Technical Information of China (English)
Michael Swan
2008-01-01
@@ The trouble with teaching grammar is that we are never quite sure whether it works or not:its effects are uncertain and hard to assess.Michael Swan looks at grammar teaching and the carry-over to spontaneous production by students.
Automatic Transformation of the Thai Categorial Grammar Treebank to Dependency Trees
DEFF Research Database (Denmark)
Rishøj, Christian; Ruangrajitpakorn, Taneth; Boonkwan, Prachya
2011-01-01
on a generic mapping of CG types in case of unknown words. Currently, all but a handful of the trees in the Thai CG bank can unambiguously be transformed into directed dependency trees. Dependency labels can optionally be assigned with a learned classifier, which in a preliminary evaluation with a very small...... training set achieves 76.5% label accuracy. In the process, a number of annotation errors in the CG bank were identified and corrected. Although rather limited in its coverage, excluding e.g. long-distance dependencies, topicalisations and longer sentences, the resulting treebank is believed to be sound...
National Research Council Canada - National Science Library
Robinson, Jane J
1974-01-01
.... The theory of systematic variation affords better direction for gathering data on rule-governed language use and a means for representing the results in formal grammars that predict speech behavior...
Institute of Scientific and Technical Information of China (English)
王楠
2012-01-01
This paper describes the nature of grammar as "universalness". The universal grammar indicates that all the languages in the world have identical grammar. This is discussed from three aspects, which gives insight into grammar acquisition.
Nijholt, Antinus
1980-01-01
Culik II and Cogen introduced the class of LR-regular grammars, an extension of the LR(k) grammars. In this paper we consider an analogous extension of the LL(k) grammars called the LL-regular grammars. The relation of this class of grammars to other classes of grammars will be shown. Any LL-regular
Recovering grammar relationships for the Java language specification
R. Lämmel (Ralf); V. Zaytsev (Vadim)
2011-01-01
textabstractGrammar convergence is a method that helps in discovering relationships between different grammars of the same language or different language versions. The key element of the method is the operational, transformation-based representation of those relationships. Given input grammars for
Institute of Scientific and Technical Information of China (English)
张松懋
1994-01-01
Forest grammar,a new type of high-dimensional grammar,is proposed in this paper,of which both the left and the right parts of every production are concatenations of tree structures.A classification of forest grammar is studied,especially,a subclass of the forest grammar,i.e.the context-sensitive forest grammar,and one of its subclasses is defined,called the weak precedence forest grammar.
Grammar and Context in Functional Discourse Grammar
Hengeveld, K.; Mackenzie, J.L.
2014-01-01
This article presents a proposal for the organization of the Contextual Component in Functional Discourse Grammar. A guiding principle in this proposal is that, given the fact that Functional Discourse Grammar is a theory of grammar, the Contextual Component should provide the information that is
Gohatre, Umakant Bhaskar; Patil, Venkat P.
2018-04-01
In computer vision application, the multiple object detection and tracking, in real-time operation is one of the important research field, that have gained a lot of attentions, in last few years for finding non stationary entities in the field of image sequence. The detection of object is advance towards following the moving object in video and then representation of object is step to track. The multiple object recognition proof is one of the testing assignment from detection multiple objects from video sequence. The picture enrollment has been for quite some time utilized as a reason for the location the detection of moving multiple objects. The technique of registration to discover correspondence between back to back casing sets in view of picture appearance under inflexible and relative change. The picture enrollment is not appropriate to deal with event occasion that can be result in potential missed objects. In this paper, for address such problems, designs propose novel approach. The divided video outlines utilizing area adjancy diagram of visual appearance and geometric properties. Then it performed between graph sequences by using multi graph matching, then getting matching region labeling by a proposed graph coloring algorithms which assign foreground label to respective region. The plan design is robust to unknown transformation with significant improvement in overall existing work which is related to moving multiple objects detection in real time parameters.
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…
Institute of Scientific and Technical Information of China (English)
刘辉
2007-01-01
Instead of being a boring subject, grammar is in fact one of the most exciting, creative, relevant subjects. It is sometimes described as the skeleton of a language, but it is much more than bones. It is the language's heartbeat, for without grammar; there can be no meaningful or effective communication. And grammar has different definitions and categories according to different contexts. By first reviewing the past linguists, especially those grammarians and their research, the paper makes some comparisons between some categories of grammar and puts forward that there is no 'good' or 'bad' grammar but knowing grammar or knowing about grammar really has a close relationship with effective communication.
TGGs for Transforming UML to CSP
DEFF Research Database (Denmark)
Greenyer, Joel; Kindler, Ekkart; Rieke, Jan
Contest. The second transformation problem, a transformation from UML activity diagrams to CSP processes, i.e. a transformation between two models, is a typical application for Triple Graph Grammars (TGGs). We present our contributed solution, presenting the TGG rules and the implementation of our TGG...... interpreter. Moreover, we point out the advantages of our soulution as well as some restrictions of the current implementation. This paper will only briefly state the transformation problem and focus on our TGG approach and the discussion of the rules....
Graph Transformation and Designing Parallel Sparse Matrix Algorithms beyond Data Dependence Analysis
Directory of Open Access Journals (Sweden)
H.X. Lin
2004-01-01
Full Text Available Algorithms are often parallelized based on data dependence analysis manually or by means of parallel compilers. Some vector/matrix computations such as the matrix-vector products with simple data dependence structures (data parallelism can be easily parallelized. For problems with more complicated data dependence structures, parallelization is less straightforward. The data dependence graph is a powerful means for designing and analyzing parallel algorithms. However, for sparse matrix computations, parallelization based on solely exploiting the existing parallelism in an algorithm does not always give satisfactory results. For example, the conventional Gaussian elimination algorithm for the solution of a tri-diagonal system is inherently sequential, so algorithms specially for parallel computation has to be designed. After briefly reviewing different parallelization approaches, a powerful graph formalism for designing parallel algorithms is introduced. This formalism will be discussed using a tri-diagonal system as an example. Its application to general matrix computations is also discussed. Its power in designing parallel algorithms beyond the ability of data dependence analysis is shown by means of a new algorithm called ACER (Alternating Cyclic Elimination and Reduction algorithm.
Fast Discrete Fourier Transform Computations Using the Reduced Adder Graph Technique
Directory of Open Access Journals (Sweden)
Andrew G. Dempster
2007-01-01
Full Text Available It has recently been shown that the n-dimensional reduced adder graph (RAG-n technique is beneficial for many DSP applications such as for FIR and IIR filters, where multipliers can be grouped in multiplier blocks. This paper highlights the importance of DFT and FFT as DSP objects and also explores how the RAG-n technique can be applied to these algorithms. This RAG-n DFT will be shown to be of low complexity and possess an attractively regular VLSI data flow when implemented with the Rader DFT algorithm or the Bluestein chirp-z algorithm. ASIC synthesis data are provided and demonstrate the low complexity and high speed of the design when compared to other alternatives.
Fast Discrete Fourier Transform Computations Using the Reduced Adder Graph Technique
Directory of Open Access Journals (Sweden)
Dempster Andrew G
2007-01-01
Full Text Available It has recently been shown that the -dimensional reduced adder graph (RAG- technique is beneficial for many DSP applications such as for FIR and IIR filters, where multipliers can be grouped in multiplier blocks. This paper highlights the importance of DFT and FFT as DSP objects and also explores how the RAG- technique can be applied to these algorithms. This RAG- DFT will be shown to be of low complexity and possess an attractively regular VLSI data flow when implemented with the Rader DFT algorithm or the Bluestein chirp- algorithm. ASIC synthesis data are provided and demonstrate the low complexity and high speed of the design when compared to other alternatives.
Institute of Scientific and Technical Information of China (English)
张松懋
1994-01-01
The syntactic parsing algorithm of weak precedence forest grammar has been introduced and the correctness and unambiguity of this algorithm have been proved. An example is given to the syntactic parsing procedure of weak precedence forest grammar.
Institute of Scientific and Technical Information of China (English)
XIAO Kunxue
2005-01-01
Constructionist approach with its brand-new perspective has begun to demonstrate its dynamic power. This paper attempts to review the basic ideas, achievements and comparison with generative grammar of Construction Grammar and generalize some problems and future research prospects.
Institute of Scientific and Technical Information of China (English)
WU Cai-ling; WANG Xi
2015-01-01
More and more researchers have now agreed upon the necessity of teaching grammar, but it still remains controversial as how to teach the forms, with the central consideration of not to harm the meaning-focused communicative teaching method. In this essay, one of the issues in grammar teaching will be discussed as how to present new grammar to learners, through evaluating and modifying a particular presentation activity in a grammar-teaching textbook.
Institute of Scientific and Technical Information of China (English)
孟静
2007-01-01
Grammar learning has often been regarded as a structure based activity .Grammar games which are worth paying attention to and implementing in the classroom can help learner to learn and recall a grammar material in a pleasant, entertaining way and motivate learners,promote the communicative competence and generate the fluency. In this essay, the author compares the use of games in learning grammar with some traditional techniques for grammar presentation and revision, in order to find the advantages of using games. Also the author discusses how to choose appropriate games and when to use games.
Functional and cognitive grammars
Institute of Scientific and Technical Information of China (English)
Anna Siewierska
2011-01-01
This paper presents a comprehensive review of the functional approach and cognitive approach to the nature of language and its relation to other aspects of human cognition. The paper starts with a brief discussion of the origins and the core tenets of the two approaches in Section 1. Section 2 discusses the similarities and differences between the three full-fledged structural functional grammars subsumed in the functional approach： Halliday＇s Systemic Functional Grammar （SFG）, Dik＇s Functional Grammar （FG）, and Van Valin＇s Role and Reference Grammar （RRG）. Section 3 deals with the major features of the three cognitive frameworks： Langacker＇s Cognitive Grammar （CG）, Goldberg＇s Cognitive Construction Grammar （CCG）, and Croft＇s Radical Construction Grammar （RCG）. Section 4 compares the two approaches and attempts to provide a unified functional-cognitive grammar. In the last section, the author concludes the paper with remarks on the unidirectional shift from functional grammar to cognitive grammar that may indicate a reinterpretation of the traditional relationship between functional and cognitive models of grammar.
Katan, Pesia; Kahta, Shani; Sasson, Ayelet; Schiff, Rachel
2017-07-01
Graph complexity as measured by topological entropy has been previously shown to affect performance on artificial grammar learning tasks among typically developing children. The aim of this study was to examine the effect of graph complexity on implicit sequential learning among children with developmental dyslexia. Our goal was to determine whether children's performance depends on the complexity level of the grammar system learned. We conducted two artificial grammar learning experiments that compared performance of children with developmental dyslexia with that of age- and reading level-matched controls. Experiment 1 was a high topological entropy artificial grammar learning task that aimed to establish implicit learning phenomena in children with developmental dyslexia using previously published experimental conditions. Experiment 2 is a lower topological entropy variant of that task. Results indicated that given a high topological entropy grammar system, children with developmental dyslexia who were similar to the reading age-matched control group had substantial difficulty in performing the task as compared to typically developing children, who exhibited intact implicit learning of the grammar. On the other hand, when tested on a lower topological entropy grammar system, all groups performed above chance level, indicating that children with developmental dyslexia were able to identify rules from a given grammar system. The results reinforced the significance of graph complexity when experimenting with artificial grammar learning tasks, particularly with dyslexic participants.
Automatic Transformation of MPI Programs to Asynchronous, Graph-Driven Form
Energy Technology Data Exchange (ETDEWEB)
Baden, Scott B [University of California, San Diego; Weare, John H [University of California, San Diego; Bylaska, Eric J [Pacific Northwest National Laboratory
2013-04-30
The goals of this project are to develop new, scalable, high-fidelity algorithms for atomic-level simulations and program transformations that automatically restructure existing applications, enabling them to scale forward to Petascale systems and beyond. The techniques enable legacy MPI application code to exploit greater parallelism though increased latency hiding and improved workload assignment. The techniques were successfully demonstrated on high-end scalable systems located at DOE laboratories. Besides the automatic MPI program transformations efforts, the project also developed several new scalable algorithms for ab-initio molecular dynamics, including new massively parallel algorithms for hybrid DFT and new parallel in time algorithms for molecular dynamics and ab-initio molecular dynamics. These algorithms were shown to scale to very large number of cores, and they were designed to work in the latency hiding framework developed in this project. The effectiveness of the developments was enhanced by the direct application to real grand challenge simulation problems covering a wide range of technologically important applications, time scales and accuracies. These included the simulation of the electronic structure of mineral/fluid interfaces, the very accurate simulation of chemical reactions in microsolvated environments, and the simulation of chemical behavior in very large enzyme reactions.
TG Grammar's Implications for the Foreign Language Teaching
Institute of Scientific and Technical Information of China (English)
殷彩
2009-01-01
Chomsky's Transformational-Generative (TG) grammar is another revolution to linguistics after Saussure's strueturalism, and it plays an important role in the modem linguistics. Introducing the research perspective and method of TG grammar, this paper analyses its implications for the foreign language teaching.
Thacker, Mike
2014-01-01
Essential French Grammar is an innovative reference grammar and workbook for intermediate and advanced undergraduate students of French (CEFR levels B2 to C1). Its clear explanations of grammar are supported by contemporary examples and lively cartoon drawings. Each chapter contains: * real-life language examples in French, with English translations * a 'key points' box and tables that summarise grammar concepts * a variety of exercises to reinforce learning * a contemporary primary source or literary extract to illustrate grammar in context. To aid your understanding, this book also contains a glossary of grammatical terms in French and English, useful verb tables and a key to the exercises. Together, these features all help you to grasp complex points of grammar and develop your French language skills.
Jubb, Margaret
2013-01-01
Instructors' edition without answer keysDiscount of 20% offered when 10 ebooks are sold- e.g. they will be sold for 263.60/ £151.90 instead of 329.50/£189.90French Grammar in Context presents a unique and exciting approach to learning grammar. Authentic texts from a rich variety of sources, literary and journalistic, are used as the starting point for the illustration and explanation of key areas of French grammar. Each point is consolidated with a wide range of written and spoken exercises. Grammar is presented not as an end in itself, but as a
A Modal-Logic Based Graph Abstraction
Bauer, J.; Boneva, I.B.; Kurban, M.E.; Rensink, Arend; Ehrig, H; Heckel, R.; Rozenberg, G.; Taentzer, G.
2008-01-01
Infinite or very large state spaces often prohibit the successful verification of graph transformation systems. Abstract graph transformation is an approach that tackles this problem by abstracting graphs to abstract graphs of bounded size and by lifting application of productions to abstract
Grammar-translation and CLT in L2 Grammar Teaching
Institute of Scientific and Technical Information of China (English)
缪杉莎
2013-01-01
This paper puts forward to compare teaching method between grammar-translation and CLT in grammar teaching. Gram⁃mar leaning is a basic concept in English learning as grammar is an important element in a communicative approach to language. This paper discussed CLT method can help and encourage student to study, however, grammar-translation method is able to under⁃stand.
Morrissey, Glenda; Young, Barbara N.
2005-01-01
The variety of theories relating to teaching ESL learners leads to contradictory ideas about teaching a second language. This paper focuses on the continuing importance of grammar in teaching and the current resurgence in interest in returning to grammar as an important component in the classroom.
REFLECTIONS ON GRAMMAR TEACHING
Institute of Scientific and Technical Information of China (English)
2000-01-01
This article aims to answer three questions:(1)Why there exists a discrepancy between the learner’sgrammar knowledge and their communicative skills?(2)What problems are there with grammar tests andteaching?(3)How should grammar be taught as"away of talking"rather than"a description of rules"?
Institute of Scientific and Technical Information of China (English)
Jiang Nongxin
2003-01-01
@@ 1 Definition of grammar Grammar is the science dealing with the systematic rules of a language, its forms, inflections, syntax, and the art of using them correctly. It is summarized from language use and practice, and reflects the logic of thinking in people's speech or writing.
Kreutner, Edith
2015-01-01
In this case study, I will show how directing a movie on grammar can help students improve their oral skills as well as their language competency, team working and planning skills, and also teach them about learning itself. I will present an innovative teaching project that uses the medium of film to get students engaged with grammar and that aims…
Phonology without universal grammar.
Archangeli, Diana; Pulleyblank, Douglas
2015-01-01
The question of identifying the properties of language that are specific human linguistic abilities, i.e., Universal Grammar, lies at the center of linguistic research. This paper argues for a largely Emergent Grammar in phonology, taking as the starting point that memory, categorization, attention to frequency, and the creation of symbolic systems are all nonlinguistic characteristics of the human mind. The articulation patterns of American English rhotics illustrate categorization and systems; the distribution of vowels in Bantu vowel harmony uses frequencies of particular sequences to argue against Universal Grammar and in favor of Emergent Grammar; prefix allomorphy in Esimbi illustrates the Emergent symbolic system integrating phonological and morphological generalizations. The Esimbi case has been treated as an example of phonological opacity in a Universal Grammar account; the Emergent analysis resolves the pattern without opacity concerns.
Directory of Open Access Journals (Sweden)
Bárbara Amaral da Silva
2015-03-01
Full Text Available From the notion of parody, credibility and legitimacy, coming mainly from studies in discourse analysis, and ideas from the sociolinguistic we intend to develop a brief comparison between the Expositive Grammar – Advanced Course (46st ed.:1926 of Eduardo Carlos Pereira, who initially presents itself as a merely descriptive grammar, and the Portuguese Grammar by the Confused Method, written by Mendes Fradique (4st ed.: 1985. We observed that the first one claims to be “expositive” when it is clearly prescriptive. The work of Mendes Fradique uses humor and irony to parody prescriptive grammars, criticizing the “good use”. In order to prove the above statement, we selected some of the concepts presented by those works, checking the position taken by each one. Among them is the very concept of grammar, language etc.
Endriss, U.; Grandi, U.
Graph aggregation is the process of computing a single output graph that constitutes a good compromise between several input graphs, each provided by a different source. One needs to perform graph aggregation in a wide variety of situations, e.g., when applying a voting rule (graphs as preference
Compiler generation based on grammar inheritance
Aksit, Mehmet; Mostert, Rene; Haverkort, Boudewijn R.H.M.
1990-01-01
The concept of grammar inheritance is introduced. Grammar inheritance is a structural organization of grammar rules by which a grammar inherits rules from ancestor grammars or may have its own rules inherited by descendant grammars. Grammar inheritance supports reusability and extensibility of
Spoken Grammar for Chinese Learners
Institute of Scientific and Technical Information of China (English)
徐晓敏
2013-01-01
Currently, the concept of spoken grammar has been mentioned among Chinese teachers. However, teach-ers in China still have a vague idea of spoken grammar. Therefore this dissertation examines what spoken grammar is and argues that native speakers’ model of spoken grammar needs to be highlighted in the classroom teaching.
Institute of Scientific and Technical Information of China (English)
陈福生
1984-01-01
@@ There are two kinds of grammar, prescriptive grammar and descriptive grammar. The prescriptive grammar gives orders how a language ought to be used rather than simply describing how it is used.This type of grammar lays down a lot of rules for the student to follow but the gifted philologist Edward Sapir points out that all grammatical rules leak. This type of grammar also warns the student against what are called ‘Shall-nots', but these ‘Shall-nots' are more likely to cause the student muchconcern rather than helping him to exprese his ideas in English. On the contrary, the descriptive grammar just describes how a language is used.
Grammar and Grammar Teaching——A Reflective Journal of Grammar and Communication
Institute of Scientific and Technical Information of China (English)
周佳
2010-01-01
@@ 1 Introduction When we talk about grammar, we will usually refer to the detailed instruction rules of grammar. In China, grammar is usually taught explicitly in formal instructions, which is different from that in some western countries. So there are some controversial questions coming out: Should there be formal instruction of grammar?
Graphing trillions of triangles.
Burkhardt, Paul
2017-07-01
The increasing size of Big Data is often heralded but how data are transformed and represented is also profoundly important to knowledge discovery, and this is exemplified in Big Graph analytics. Much attention has been placed on the scale of the input graph but the product of a graph algorithm can be many times larger than the input. This is true for many graph problems, such as listing all triangles in a graph. Enabling scalable graph exploration for Big Graphs requires new approaches to algorithms, architectures, and visual analytics. A brief tutorial is given to aid the argument for thoughtful representation of data in the context of graph analysis. Then a new algebraic method to reduce the arithmetic operations in counting and listing triangles in graphs is introduced. Additionally, a scalable triangle listing algorithm in the MapReduce model will be presented followed by a description of the experiments with that algorithm that led to the current largest and fastest triangle listing benchmarks to date. Finally, a method for identifying triangles in new visual graph exploration technologies is proposed.
Katan, Pesia; Kahta, Shani; Sasson, Ayelet; Schiff, Rachel
2017-01-01
Graph complexity as measured by topological entropy has been previously shown to affect performance on artificial grammar learning tasks among typically developing children. The aim of this study was to examine the effect of graph complexity on implicit sequential learning among children with developmental dyslexia. Our goal was to determine…
Mazet, Veronique
2013-01-01
The easy way to master French grammar French Grammar For Dummies is a logical extension and complement to the successful language learning book, French For Dummies. In plain English, it teaches you the grammatical rules of the French language, including parts of speech, sentence construction, pronouns, adjectives, punctuation, stress and verb tenses, and moods. Throughout the book, you get plenty of practice opportunities to help you on your goal of mastering basic French grammar and usage. Grasp the grammatical rules of French including parts of speech, sentenc
Kuźnik, Krzysztof; Paszyński, Maciej; Calo, Victor M.
2013-01-01
on NVIDIA CUDA GPU, delivering logarithmic execution time for linear, quadratic, cubic and higher order B-splines. Thus, the CUDA implementation delivers the optimal performance predicted by our graph grammar analysis. We utilize the solver for multiple
Importance of Grammar in English Teaching
Institute of Scientific and Technical Information of China (English)
赵天毓
2011-01-01
Grammar teaching is one of the most difficult and important points in the middle school. However, there exist some problems with present grammar teaching, such as students＇ poor knowledge of grammar, improper teaching methods and the ignorance of grammar
Zhang, L.-C.; Patone, M.
2017-01-01
We synthesise the existing theory of graph sampling. We propose a formal definition of sampling in finite graphs, and provide a classification of potential graph parameters. We develop a general approach of Horvitz–Thompson estimation to T-stage snowball sampling, and present various reformulations of some common network sampling methods in the literature in terms of the outlined graph sampling theory.
Janssen, P.; Stouffs, R.M.F.; Chaszar, A.T.; Boeykens, S.; Toth, B.
2012-01-01
This paper describes the use of property graphs for mapping data between AEC software tools, which are not linked by common data formats and/or other interoperability measures. The intention of introducing this in practice, education and research is to facilitate the use of diverse, non-integrated
Directory of Open Access Journals (Sweden)
Fredy Ángel Miguel Amaya Robayo
2010-08-01
Full Text Available Es un hecho conocido que toda gramática libre de contexto puede ser transformada a la forma normal de Chomsky de tal forma que los lenguajes generados por las dos gramáticas son equivalentes. Una gramática en forma normal de Chomsky (FNC, tiene algunas ventajas, por ejemplo sus árboles de derivación son binarios, la forma de sus reglas más simples etc. Por eso es siempre deseable poder trabajar con una gramática en FNC en las aplicaciones que lo requieran. Existe un algoritmo que permite transformar una gramática libre de contexto a una en FNC, sin embargo la cantidad de reglas generadas al hacer la transformación depende del número de reglas en la gramática inicial así como de otras características. En este trabajo se analiza desde el punto de vista experimental y estadístico, la relación existente entre el número de reglas iniciales y el número de reglas que resultan luego de transformar una Gramática Libre de Contexto a la FNC. Esto permite planificar la cantidad de recursos computacionales necesarios en caso de tratar con gramáticas de alguna complejidad.It is well known that any context-free grammar can be transformed to the Chomsky normal form so that the languages generated by each one are equivalent. A grammar in Chomsky Normal Form (CNF, has some advantages: their derivation trees are binary, simplest rules and so on. So it is always desirable to work with a grammar in CNF in applications that require them. There is an algorithm that can transform a context-free grammar to one CNF grammar, however the number of rules generated after the transformation depends on the initial grammar and other circumstances. In this work we analyze from the experimental and statistical point of view the relationship between the number of initial rules and the number of resulting rules after transforming. This allows you to plan the amount of computational resources needed in case of dealing with grammars of some complexity.
Functional discourse grammar: pragmatic aspects
Hannay, M.; Hengeveld, K.; Brisard, F.; Östman, J.O.; Verschueren, J.
2009-01-01
This chapter introduces Functional Discourse Grammar, focusing on the way in which this model is capable of accounting for the grammatical encoding of pragmatic distinctions and for the typological variation found in this area of grammar.
Closure properties of Watson-Crick grammars
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.
DEFF Research Database (Denmark)
Nielson, Hanne Riis; Skyum, S.
1981-01-01
It is shown that any well-defined attribute grammar is k-visit for some k. Furthermore, it is shown that given a well-defined grammar G and an integer k, it is decidable whether G is k-visit. Finally it is shown that the k-visit grammars specify a proper hierarchy with respect to translations...
The Necessity of Grammar Teaching
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…
Brouwer, A.E.; Haemers, W.H.; Brouwer, A.E.; Haemers, W.H.
2012-01-01
This chapter presents some simple results on graph spectra.We assume the reader is familiar with elementary linear algebra and graph theory. Throughout, J will denote the all-1 matrix, and 1 is the all-1 vector.
Borjars, Kersti
2013-01-01
Answering key questions such as 'Why study grammar?' and 'What is standard English?', Introducing English Grammar guides readers through the practical analysis of the syntax of English sentences. With all special terms carefully explained as they are introduced, the book is written for readers with no previous experience of grammatical analysis. It is ideal for all those beginning their study of linguistics, English language or speech pathology, as well as students with primarily literary interests who need to cover the basics of linguistic analysis. The approach taken is in line with current research in grammar, a particular advantage for students who may go on to study syntax in more depth. All the examples and exercises use real language taken from newspaper articles, non-standard dialects and include excerpts from studies of patients with language difficulties. Students are encouraged to think about the terminology as a tool kit for studying language and to test what can and cannot be described using thes...
TEACHING GRAMMAR IN CONTEXT: WHY AND HOW?
Noor Maulidiyah
2017-01-01
Grammar is an important component of English. Without grammar, it is not possible to communicate meaning successfully. Therefore, teachers and educators have to pay close attention to teaching grammar effectively. Based on the writer‘s experience in teaching grammar using the traditional way, many students still had difficulty in acquiring the grammar points. The grammar meetings were not effective, and the students did not thoroughly understand the grammar exercises. The students seemed bore...
A comprehensive French grammar
Price, Glanville
2013-01-01
Characterized by clear and accessible explanations, numerous examples and sample sentences, a new section on register and tone, and useful appendices covering topics including age and time, A Comprehensive French Grammar, Sixth Edition is an indispensable tool for advanced students of French language and literature.A revised edition of this established, bestselling French grammarIncludes a new section on register and medium and offers expanded treatment of French punctuationFeatures numerous examples and sample sentences, and useful appendices covering topics including age, time, and dimension
DEFF Research Database (Denmark)
Christiansen, Henning; Dahl, Veronica
2009-01-01
By extending logic grammars with constraint logic, we give them the ability to create knowledge bases that represent the meaning of an input string. Semantic information is thus defined through extra-grammatical means, and a sentence's meaning logically follows as a by-product of string rewriting....... We formalize these ideas, and exemplify them both within and outside first-order logic, and for both fixed and dynamic knowledge bases. Within the latter variety, we consider the usual left-to-right derivations that are traditional in logic grammars, but also -- in a significant departure from...
Hawkins, Roger
2015-01-01
Long trusted as the most comprehensive, up-to-date and user-friendly grammar available, French Grammar and Usage is a complete guide to French as it is written and spoken today. It includes clear descriptions of all the main grammatical phenomena of French, and their use, illustrated by numerous examples taken from contemporary French, and distinguishes the most common forms of usage, both formal and informal.Key features include:Comprehensive content, covering all the major structures of contemporary French User-friendly organisation offering easy-to-find sections with cross-referencing and i
Ward, Lesley J
2009-01-01
If you're confused by commas, perplexed by pronouns, and plain terrified by tenses, English Grammar For Dummies will put your fears to rest. Packed with expert guidance, it covers everything from sentence basics to rules even your English teacher didn't know - if you want to brush up on your grammar, this is the only guide you'll ever need. Discover how to: avoid common grammatical errors; get to grips with apostrophes; structure sentences correctly; use verbs and find the right tense; and decide when to use slang or formal English.
Grammar and Grammaring: Toward Modes for English Grammar Teaching in China
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…
Institute of Scientific and Technical Information of China (English)
1996-01-01
IntroductionToday many Chinese students think of English grammar as an unpopular and difficult part of theirEnglish lessons Even more worryingly,that attitude is one they have usually picked up from theirteachers.Namely,grammar seems to be hard work for EFL teachers and students.So should grammarteaching be abolishedWhy do many teachers and students take a negative attitude toward grammarInthis paper,first,I will attempt to discuss the place of grammar in EFL teaching.Next,I will outline thetraditional methods of grammar teaching and the results of this kind of grammar teaching.Finally,I willput forward some suggestions on how to make grammar teaching more interesting in Chinese classrooms.
Plaisier, Heleen
2006-01-01
This book is a descriptive grammar of Lepcha, a Tibeto-Burman language spoken in Sikkim, Darjeeling district in West Bengal in India, in Ilam district in Nepal, and in a few villages of Samtsi district in south-western Bhutan. The data for this study were collected during several sojourns amongst
Zaytsev, V.; Pierantonio, A.; Schätz, B.; Tamzalit, D.
2014-01-01
The evolution of a software language (whether modelled by a grammar or a schema or a metamodel) is not limited to development of new versions and dialects. An important dimension of a software language evolution is maturing in the sense of improving the quality of its definition. In this paper, we
Existential Grammar for Composition.
Merchant, Frank
The teaching of grammar has been in sad decline since medieval times, when it included the whole skill of creating in language. Our textbook community has moved through a series of ineffective fashions, from those of Fries to post-Chomsky. All have presumed to replace prescriptive rules with realistic explanations. But all have fallen, like the…
Arlington County Public Schools, VA. REEP, Arlington Education and Employment Program.
This document provides the Arlington Education and Employment Program's (REEP) favorite techniques for teaching English-as-a-Second-Language (ESL) grammar. The focus, levels, and materials needed are presented for each of the techniques as well as the steps to follow. (Adjunct ERIC Clearinghouse for ESL Literacy Education) (Author/VWL)
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…
Knowing Chinese character grammar.
Myers, James
2016-02-01
Chinese character structure has often been described as representing a kind of grammar, but the notion of character grammar has hardly been explored. Patterns in character element reduplication are particularly grammar-like, displaying discrete combinatoriality, binarity, phonology-like final prominence, and potentially the need for symbolic rules (X→XX). To test knowledge of these patterns, Chinese readers were asked to judge the acceptability of fake characters varying both in grammaticality (obeying or violating reduplication constraints) and in lexicality (of the reduplicative configurations). While lexical knowledge was important (lexicality improved acceptability and grammatical configurations were accepted more quickly when also lexical), grammatical knowledge was important as well, with grammaticality improving acceptability equally for lexical and nonlexical configurations. Acceptability was also higher for more frequent reduplicative elements, suggesting that the reduplicative configurations were decomposed. Chinese characters present an as-yet untapped resource for exploring fundamental questions about the nature of the human capacity for grammar. Copyright © 2015 Elsevier B.V. All rights reserved.
Regular extensions of some classes of grammars
Nijholt, Antinus
Culik and Cohen introduced the class of LR-regular grammars, an extension of the LR(k) grammars. In this report we consider the analogous extension of the LL(k) grammers, called the LL-regular grammars. The relations of this class of grammars to other classes of grammars are shown. Every LL-regular
Comparison of Context-free Grammars Based on Parsing Generated Test Data
B. Fischer (Bernd); R. Lämmel (Ralf); V. Zaytsev (Vadim); U. Aßmann; J. Saraiva; A.M. Sloane
2011-01-01
textabstractThere exist a number of software engineering scenarios that essentially involve equivalence or correspondence assertions for some of the context-free grammars in the scenarios. For instance, when applying grammar transformations during parser development---be it for the sake of
Single-View 3D Scene Reconstruction and Parsing by Attribute Grammar.
Liu, Xiaobai; Zhao, Yibiao; Zhu, Song-Chun
2018-03-01
In this paper, we present an attribute grammar for solving two coupled tasks: i) parsing a 2D image into semantic regions; and ii) recovering the 3D scene structures of all regions. The proposed grammar consists of a set of production rules, each describing a kind of spatial relation between planar surfaces in 3D scenes. These production rules are used to decompose an input image into a hierarchical parse graph representation where each graph node indicates a planar surface or a composite surface. Different from other stochastic image grammars, the proposed grammar augments each graph node with a set of attribute variables to depict scene-level global geometry, e.g., camera focal length, or local geometry, e.g., surface normal, contact lines between surfaces. These geometric attributes impose constraints between a node and its off-springs in the parse graph. Under a probabilistic framework, we develop a Markov Chain Monte Carlo method to construct a parse graph that optimizes the 2D image recognition and 3D scene reconstruction purposes simultaneously. We evaluated our method on both public benchmarks and newly collected datasets. Experiments demonstrate that the proposed method is capable of achieving state-of-the-art scene reconstruction of a single image.
Procedural Content Graphs for Urban Modeling
Directory of Open Access Journals (Sweden)
Pedro Brandão Silva
2015-01-01
Full Text Available Massive procedural content creation, for example, for virtual urban environments, is a difficult, yet important challenge. While shape grammars are a popular example of effectiveness in architectural modeling, they have clear limitations regarding readability, manageability, and expressive power when addressing a variety of complex structural designs. Moreover, shape grammars aim at geometry specification and do not facilitate integration with other types of content, such as textures or light sources, which could rather accompany the generation process. We present procedural content graphs, a graph-based solution for procedural generation that addresses all these issues in a visual, flexible, and more expressive manner. Besides integrating handling of diverse types of content, this approach introduces collective entity manipulation as lists, seamlessly providing features such as advanced filtering, grouping, merging, ordering, and aggregation, essentially unavailable in shape grammars. Hereby, separated entities can be easily merged or just analyzed together in order to perform a variety of context-based decisions and operations. The advantages of this approach are illustrated via examples of tasks that are either very cumbersome or simply impossible to express with previous grammar approaches.
Institute of Scientific and Technical Information of China (English)
肖琳燃
2017-01-01
Grammar is an aspect of language about which learners have different opinions. Some learners are very interested in ifnding out or learning grammar rules and doing lots of grammar exercises. Others hate grammar and think it is the most boring part of learning a new language. Whatever opinion you have, however, you cannot escape from grammar; it is in every sentence you read or write, speak or hear. Grammar is simply the word for the rules that people follow when they use a language. We need those rules in the same way as we need the rules in a game. If there are no rules, or if everybody follows their own rules, the game would soon break down. It's the same with language; without rules we would not be able to communicate with other people. So you cannot escape from grammar, but the key question here is: what is the best way to learn grammar? You can learn the rules of a game by simply playing the game. You will certainly make mistakes; you may even get hurt. Eventually, however, you will know how to play. Of course, the rules of a language are very much more complicated than the rules of any game, but in fact this is exactly how you learned your own language. Nobody taught you the rules of your mother tongue as you were growing up but now you never make a grammar mistake.
The Teaching of English Grammar
Institute of Scientific and Technical Information of China (English)
祖凤霞
2009-01-01
Acquiring the grammar system is vital in the foreign language learning, and there has always been the debate on how learners can best acquire the English grammar. Inthis paper, two methods for teaching grammar will be presented--traditional practice and consciousness-raising. Both thetwo methods have their ad-vantages and disadvantages. But in practice, it is a better idea to combine different methods to make grammar teaching more effective. In addition, the consideration of different individual learners is also very important.
A communicative grammar of English
Leech, Geoffrey
2013-01-01
A Communicative Grammar of English has long been established as a grammar innovative in approach, reliable in coverage, and clear in its explanations. This fully revised and redesigned third edition provides up-to-date and accessible help to teachers, advanced learners and undergraduate students of English. Part One looks at the way English grammar varies in different types of English, such as 'formal' and 'informal', 'spoken' and 'written'; Part Two focuses on the uses of grammar rather than on grammatical structure and Part Three provides a handy alphabetically arranged guide to
DEFF Research Database (Denmark)
Vestergaard, Preben Dahl; Hartnell, Bert L.
2006-01-01
There are many results dealing with the problem of decomposing a fixed graph into isomorphic subgraphs. There has also been work on characterizing graphs with the property that one can delete the edges of a number of edge disjoint copies of the subgraph and, regardless of how that is done, the gr...
International Nuclear Information System (INIS)
Barra, F.; Gaspard, P.
2001-01-01
We consider the classical evolution of a particle on a graph by using a time-continuous Frobenius-Perron operator that generalizes previous propositions. In this way, the relaxation rates as well as the chaotic properties can be defined for the time-continuous classical dynamics on graphs. These properties are given as the zeros of some periodic-orbit zeta functions. We consider in detail the case of infinite periodic graphs where the particle undergoes a diffusion process. The infinite spatial extension is taken into account by Fourier transforms that decompose the observables and probability densities into sectors corresponding to different values of the wave number. The hydrodynamic modes of diffusion are studied by an eigenvalue problem of a Frobenius-Perron operator corresponding to a given sector. The diffusion coefficient is obtained from the hydrodynamic modes of diffusion and has the Green-Kubo form. Moreover, we study finite but large open graphs that converge to the infinite periodic graph when their size goes to infinity. The lifetime of the particle on the open graph is shown to correspond to the lifetime of a system that undergoes a diffusion process before it escapes
Attribute And-Or Grammar for Joint Parsing of Human Pose, Parts and Attributes.
Park, Seyoung; Nie, Xiaohan; Zhu, Song-Chun
2017-07-25
This paper presents an attribute and-or grammar (A-AOG) model for jointly inferring human body pose and human attributes in a parse graph with attributes augmented to nodes in the hierarchical representation. In contrast to other popular methods in the current literature that train separate classifiers for poses and individual attributes, our method explicitly represents the decomposition and articulation of body parts, and account for the correlations between poses and attributes. The A-AOG model is an amalgamation of three traditional grammar formulations: (i)Phrase structure grammar representing the hierarchical decomposition of the human body from whole to parts; (ii)Dependency grammar modeling the geometric articulation by a kinematic graph of the body pose; and (iii)Attribute grammar accounting for the compatibility relations between different parts in the hierarchy so that their appearances follow a consistent style. The parse graph outputs human detection, pose estimation, and attribute prediction simultaneously, which are intuitive and interpretable. We conduct experiments on two tasks on two datasets, and experimental results demonstrate the advantage of joint modeling in comparison with computing poses and attributes independently. Furthermore, our model obtains better performance over existing methods for both pose estimation and attribute prediction tasks.
Explicit teaching of grammar and improvement in the grammar of ...
African Journals Online (AJOL)
Explicit teaching of grammar and improvement in the grammar of student writing. J Parkinson. Abstract. No Abstract. Full Text: EMAIL FREE FULL TEXT EMAIL FREE FULL TEXT · DOWNLOAD FULL TEXT DOWNLOAD FULL TEXT. Article Metrics. Metrics Loading ... Metrics powered by PLOS ALM
Teachers' Perceptions about Grammar Teaching
Thu, Tran Hoang
2009-01-01
This study investigates English as a second language (ESL) teachers' beliefs in grammar teaching. A 32-item questionnaire was administered to 11 ESL teachers in a language school in California. The results show that the participants generally believe that the formal study of grammar is essential to the eventual mastery of a foreign or second…
Object grammars and random generation
Directory of Open Access Journals (Sweden)
I. Dutour
1998-12-01
Full Text Available This paper presents a new systematic approach for the uniform random generation of combinatorial objects. The method is based on the notion of object grammars which give recursive descriptions of objects and generalize context-freegrammars. The application of particular valuations to these grammars leads to enumeration and random generation of objects according to non algebraic parameters.
The preverbal locative NP in Lexical Functional Grammar
African Journals Online (AJOL)
Data is drawn from some of the findings of the study I conducted on the locative inversion constructions in Botswana in 2003. I explore an information structure analysis of the findings. I also propose an analysis within Lexical Functional Grammar (Henceforth LFG), a non-transformational theory which considers languages ...
Structural priming, action planning, and grammar.
MacDonald, Maryellen C; Weiss, Daniel J
2017-01-01
Structural priming is poorly understood and cannot inform accounts of grammar for two reasons. First, those who view performance as grammar + processing will always be able to attribute psycholinguistic data to processing rather than grammar. Second, structural priming may be simply an example of hysteresis effects in general action planning. If so, then priming offers no special insight into grammar.
The History of Modern Chinese Grammar Studies
Peverelli, P.J.
2015-01-01
This book discusses the way Chinese scholars developed a national grammar. Chinese didnt develop grammar until Chinas contact with Western grammar books in the 19th Century. The first indigenous grammar was published in 1889. It included some traditional notions, but mainly imitated European
TEACHING GRAMMAR IN CONTEXT: WHY AND HOW?
Directory of Open Access Journals (Sweden)
Noor Maulidiyah
2017-04-01
Then the paper explains the concept of context in teaching grammar and describes the reasons for teaching grammar in context. The last part of the paper demonstrates how grammar is taught in context. These sample lessons are taken from different sources based on experts when teaching grammar in context.Teaching grammar in context is more useful and can help the students to master English better.
Classroom Grammar Teaching for Adult Learners
Institute of Scientific and Technical Information of China (English)
石怡
2014-01-01
As Wight (1999, p.33) pointed out to“know a language was to know the grammar of it”, hence grammar teaching is usually the main approach in second or foreign language teaching. This paper presents an analysis from three aspects to il-lustrate why classroom grammar teaching benefits adult learners. However, if grammar is overstated, some negative results will occur. Therefore a balance between grammar teaching and communicative skill teaching is need, as is a balance between accuracy and fluency.
Learning System of Web Navigation Patterns through Hypertext Probabilistic Grammars
Directory of Open Access Journals (Sweden)
Augusto Cortez Vasquez
2015-01-01
Full Text Available One issue of real interest in the area of web data mining is to capture users’ activities during connection and extract behavior patterns that help define their preferences in order to improve the design of future pages adapting websites interfaces to individual users. This research is intended to provide, first of all, a presentation of the methodological foundations of the use of probabilistic languages to identify relevant or most visited websites. Secondly, the web sessions are represented by graphs and probabilistic context-free grammars so that the sessions that have the highest probabilities are considered the most visited and most preferred, therefore, the most important in relation to a particular topic. It aims to develop a tool for processing web sessions obtained from a log server represented by probabilistic context-free grammars.
English grammar a university course
Downing, Angela
2014-01-01
This best-selling comprehensive descriptive grammar forms a complete course, ideal for all students studying English Language ,whether on a course or for self-study. Broadly based on Hallidayan systemic-functional grammar but also drawing on cognitive linguistics and discourse analysis, English Grammar is accessible, avoiding overly theoretical or technical explanations.Divided into 12 self-contained chapters based around language functions, each chapter is divided into units of class-length material. Key features include:Numerous authentic texts from a wide range of sources, both spoken and w
English Grammar Workbook For Dummies
O'Sullivan, Nuala
2010-01-01
English Grammar Workbook For Dummies, UK Edition is grammar First Aid for anyone wanting to perfect their English and develop the practical skills needed to write and speak correctly. Each chapter focuses on key grammatical principles, with easy-to-follow theory and examples as well as practice questions and explanations. From verbs, prepositions and tenses, to style, expressions and tricky word traps, this hands-on workbook is essential for both beginners looking to learn and practise the basics of English grammar, and those who want to brush up skills they already have - quickly, easily, and
Practising French grammar a workbook
Dr Roger Hawkins; Towell, Richard
2015-01-01
This new edition of Practising French Grammar offers a set of varied and accessible exercises for developing a practical awareness of French as it is spoken and written today. The lively examples and authentic texts and cartoons have been updated to reflect current usage. A new companion website provides a wealth of additional interactive exercises to help consolidate challenging grammar points. Practising French Grammar provides concise summaries of key grammatical points at the beginning of each exercise, as well as model answers to the exercises and translations of difficult words, making i
ULTRA: Universal Grammar as a Universal Parser.
Medeiros, David P
2018-01-01
A central concern of generative grammar is the relationship between hierarchy and word order, traditionally understood as two dimensions of a single syntactic representation. A related concern is directionality in the grammar. Traditional approaches posit process-neutral grammars, embodying knowledge of language, put to use with infinite facility both for production and comprehension. This has crystallized in the view of Merge as the central property of syntax, perhaps its only novel feature. A growing number of approaches explore grammars with different directionalities, often with more direct connections to performance mechanisms. This paper describes a novel model of universal grammar as a one-directional, universal parser. Mismatch between word order and interpretation order is pervasive in comprehension; in the present model, word order is language-particular and interpretation order (i.e., hierarchy) is universal. These orders are not two dimensions of a unified abstract object (e.g., precedence and dominance in a single tree); rather, both are temporal sequences, and UG is an invariant real-time procedure (based on Knuth's stack-sorting algorithm) transforming word order into hierarchical order. This shift in perspective has several desirable consequences. It collapses linearization, displacement, and composition into a single performance process. The architecture provides a novel source of brackets (labeled unambiguously and without search), which are understood not as part-whole constituency relations, but as storage and retrieval routines in parsing. It also explains why neutral word order within single syntactic cycles avoids 213-like permutations. The model identifies cycles as extended projections of lexical heads, grounding the notion of phase. This is achieved with a universal processor, dispensing with parameters. The empirical focus is word order in noun phrases. This domain provides some of the clearest evidence for 213-avoidance as a cross
DEFF Research Database (Denmark)
Seiller, Thomas
2016-01-01
Interaction graphs were introduced as a general, uniform, construction of dynamic models of linear logic, encompassing all Geometry of Interaction (GoI) constructions introduced so far. This series of work was inspired from Girard's hyperfinite GoI, and develops a quantitative approach that should...... be understood as a dynamic version of weighted relational models. Until now, the interaction graphs framework has been shown to deal with exponentials for the constrained system ELL (Elementary Linear Logic) while keeping its quantitative aspect. Adapting older constructions by Girard, one can clearly define...... "full" exponentials, but at the cost of these quantitative features. We show here that allowing interpretations of proofs to use continuous (yet finite in a measure-theoretic sense) sets of states, as opposed to earlier Interaction Graphs constructions were these sets of states were discrete (and finite...
Trudeau, Richard J
1994-01-01
Preface1. Pure Mathematics Introduction; Euclidean Geometry as Pure Mathematics; Games; Why Study Pure Mathematics?; What's Coming; Suggested Reading2. Graphs Introduction; Sets; Paradox; Graphs; Graph diagrams; Cautions; Common Graphs; Discovery; Complements and Subgraphs; Isomorphism; Recognizing Isomorphic Graphs; Semantics The Number of Graphs Having a Given nu; Exercises; Suggested Reading3. Planar Graphs Introduction; UG, K subscript 5, and the Jordan Curve Theorem; Are there More Nonplanar Graphs?; Expansions; Kuratowski's Theorem; Determining Whether a Graph is Planar or
Mathematical grammar of biology
Yamagishi, Michel Eduardo Beleza
2017-01-01
This seminal, multidisciplinary book shows how mathematics can be used to study the first principles of DNA. Most importantly, it enriches the so-called “Chargaff’s grammar of biology” by providing the conceptual theoretical framework necessary to generalize Chargaff’s rules. Starting with a simple example of DNA mathematical modeling where human nucleotide frequencies are associated to the Fibonacci sequence and the Golden Ratio through an optimization problem, its breakthrough is showing that the reverse, complement and reverse-complement operators defined over oligonucleotides induce a natural set partition of DNA words of fixed-size. These equivalence classes, when organized into a matrix form, reveal hidden patterns within the DNA sequence of every living organism. Intended for undergraduate and graduate students both in mathematics and in life sciences, it is also a valuable resource for researchers interested in studying invariant genomic properties.
LexGram - a practical categorial grammar formalism -
Koenig, Esther
1995-01-01
We present the LexGram system, an amalgam of (Lambek) categorial grammar and Head Driven Phrase Structure Grammar (HPSG), and show that the grammar formalism it implements is a well-structured and useful tool for actual grammar development.
Diestel, Reinhard
2017-01-01
This standard textbook of modern graph theory, now in its fifth edition, combines the authority of a classic with the engaging freshness of style that is the hallmark of active mathematics. It covers the core material of the subject with concise yet reliably complete proofs, while offering glimpses of more advanced methods in each field by one or two deeper results, again with proofs given in full detail. The book can be used as a reliable text for an introductory course, as a graduate text, and for self-study. From the reviews: “This outstanding book cannot be substituted with any other book on the present textbook market. It has every chance of becoming the standard textbook for graph theory.”Acta Scientiarum Mathematiciarum “Deep, clear, wonderful. This is a serious book about the heart of graph theory. It has depth and integrity. ”Persi Diaconis & Ron Graham, SIAM Review “The book has received a very enthusiastic reception, which it amply deserves. A masterly elucidation of modern graph theo...
Analyzing Ambiguity of Context-Free Grammars
DEFF Research Database (Denmark)
Brabrand, Claus; Giegerich, Robert; Møller, Anders
2007-01-01
It has been known since 1962 that the ambiguity problem for context-free grammars is undecidable. Ambiguity in context-free grammars is a recurring problem in language design and parser generation, as well as in applications where grammars are used as models of real-world physical structures. We...... observe that there is a simple linguistic characterization of the grammar ambiguity problem, and we show how to exploit this to conservatively approximate the problem based on local regular approximations and grammar unfoldings. As an application, we consider grammars that occur in RNA analysis...
Gould, Ronald
2012-01-01
This introduction to graph theory focuses on well-established topics, covering primary techniques and including both algorithmic and theoretical problems. The algorithms are presented with a minimum of advanced data structures and programming details. This thoroughly corrected 1988 edition provides insights to computer scientists as well as advanced undergraduates and graduate students of topology, algebra, and matrix theory. Fundamental concepts and notation and elementary properties and operations are the first subjects, followed by examinations of paths and searching, trees, and networks. S
A Learning Algorithm for Multimodal Grammar Inference.
D'Ulizia, A; Ferri, F; Grifoni, P
2011-12-01
The high costs of development and maintenance of multimodal grammars in integrating and understanding input in multimodal interfaces lead to the investigation of novel algorithmic solutions in automating grammar generation and in updating processes. Many algorithms for context-free grammar inference have been developed in the natural language processing literature. An extension of these algorithms toward the inference of multimodal grammars is necessary for multimodal input processing. In this paper, we propose a novel grammar inference mechanism that allows us to learn a multimodal grammar from its positive samples of multimodal sentences. The algorithm first generates the multimodal grammar that is able to parse the positive samples of sentences and, afterward, makes use of two learning operators and the minimum description length metrics in improving the grammar description and in avoiding the over-generalization problem. The experimental results highlight the acceptable performances of the algorithm proposed in this paper since it has a very high probability of parsing valid sentences.
A Task-driven Grammar Refactoring Algorithm
Directory of Open Access Journals (Sweden)
Ivan Halupka
2012-01-01
Full Text Available This paper presents our proposal and the implementation of an algorithm for automated refactoring of context-free grammars. Rather than operating under some domain-specific task, in our approach refactoring is perfomed on the basis of a refactoring task defined by its user. The algorithm and the corresponding refactoring system are called mARTINICA. mARTINICA is able to refactor grammars of arbitrary size and structural complexity. However, the computation time needed to perform a refactoring task with the desired outcome is highly dependent on the size of the grammar. Until now, we have successfully performed refactoring tasks on small and medium-size grammars of Pascal-like languages and parts of the Algol-60 programming language grammar. This paper also briefly introduces the reader to processes occurring in grammar refactoring, a method for describing desired properties that a refactored grammar should fulfill, and there is a discussion of the overall significance of grammar refactoring.
Chartrand, Gary; Zhang, Ping
2010-01-01
Gary Chartrand has influenced the world of Graph Theory for almost half a century. He has supervised more than a score of Ph.D. dissertations and written several books on the subject. The most widely known of these texts, Graphs and Digraphs, … has much to recommend it, with clear exposition, and numerous challenging examples [that] make it an ideal textbook for the advanced undergraduate or beginning graduate course. The authors have updated their notation to reflect the current practice in this still-growing area of study. By the authors' estimation, the 5th edition is approximately 50% longer than the 4th edition. … the legendary Frank Harary, author of the second graph theory text ever produced, is one of the figures profiled. His book was the standard in the discipline for several decades. Chartrand, Lesniak and Zhang have produced a worthy successor.-John T. Saccoman, MAA Reviews, June 2012 (This book is in the MAA's basic library list.)As with the earlier editions, the current text emphasizes clear...
Some Key Principles for Developing Grammar Skills
Institute of Scientific and Technical Information of China (English)
张威
2008-01-01
Grammar is sometimes defined aft"the way words are put together to make correct sentences"(Ur,2004,P.75).The aim of teaching grammar is to raise the rates of the correctness of language use and help the students transfer the isolated language points to apply language.In this essay，the author introduces two kinds of Conlnlon methods in English grammar class. And there are some key principles in grammar teaching.
Snowball Throwing in Teaching Grammar
Directory of Open Access Journals (Sweden)
Yanuarti Apsari
2018-05-01
Full Text Available The aims of this study are to describe the implementation of snowball throwing in teaching grammar and to investigate the benefits of applying snowball throwing. The research was conducted at STKIP Siliwangi Bandung. This study applied qualitative research involving one class consisting of second semester students in English Department who were taking the subject of foundation of English Grammar. The data were obtained from classroom observation and students’ interview. The findings showed that there are seven stages in implementing snowball throwing in teaching grammar. The stages consist of preparing teaching material, forming group, re-explaining the material to the member of the group, formulating question, tossing the ball, answering questions and evaluating teaching and learning process. In addition, the findings also revealed that there are some benefits from applying snowball throwing in teaching grammar such as improving students’ comprehension in learning grammar, creating enjoyable learning atmosphere, increasing students’ vocabulary, developing students’ speaking skill, developing students’ cooperation skill and increasing students’ participation in the class.
CLIMB grammars: three projects using metagrammar engineering
Fokkens, A.S.; Avgustinova, T.; Zhang, Yi
2012-01-01
This paper introduces the CLIMB (Comparative Libraries of Implementations with Matrix Basis) methodology and grammars. The basic idea behind CLIMB is to use code generation as a general methodology for grammar development in order to create a more systematic approach to grammar development. The
A Construction Grammar for the Classroom
Holme, Randal
2010-01-01
Construction grammars (Lakoff, Women, fire and dangerous things: What categories reveal about the Mind, University of Chicago Press, 1987; Langacker, Foundations of cognitive grammar: Theoretical pre-requisites, Stanford University Press, 1987; Croft, Radical construction grammar: Syntactic theory in typological perspective, Oxford University…
Drama Grammar: Towards a Performative Postmethod Pedagogy
Even, Susanne
2011-01-01
This article presents the original concept of drama grammar, the synthesis of grammar instruction and drama pedagogy, which integrates both structural and communicative paradigms through a dialectic combination of acting and linguistic analysis. Based on the principles of drama pedagogy, drama grammar makes use of techniques from the performing…
An Evaluation of the Grammar Teaching Material
Institute of Scientific and Technical Information of China (English)
张可科
2013-01-01
Of the many issues surrounding grammar, perhaps the hottest debate is whether to teach it or not. We review briefly argu⁃ments against and in support of grammar teaching before examining current grammar approaches in second language teaching.
Reframing the English Grammar Schools Debate
Morris, Rebecca; Perry, Thomas
2017-01-01
In October 2015 the Department for Education (DfE) permitted a grammar school in Tonbridge, Kent, to open up an annexe in Sevenoaks, 10 miles away. Amidst claims that the annexe was essentially a new grammar school, the decision reignited an old debate about the value of academically-selective "grammar" schools in England. The intensity…
Procedure Of Teaching Grammar Using Memory Enhancement
Directory of Open Access Journals (Sweden)
Herri Susanto
2011-11-01
Full Text Available Teaching grammar has been regarded as a process of understanding from the context. It means a teacher teaches the pupils contextually more than just the rules. However, I have my own experience that teaching grammar methods must depend on the purposes of learning grammar. Some people learn grammar as a means to fulfill the syllabus needs for schools but other people learn grammar for special purposes out of school syllabus, such as for entrance test. For these reasons, the methods of teaching grammar should be different. The students who learn grammar based on the school syllabus probably needs longer procedure of learning that usually uses contextual teaching through listening, speaking, writing, and reading. Nevertheless, students who learn grammar for test need shorter procedure of learning such as memorizing. Therefore, I propose giving a workshop of teaching grammar using memory enhancement as another alternative teaching grammar method. This workshop would show the class that grammar can be learnt through memory enhancement process, i.e.; mind map, music, memory technique and drill to boost up students understanding for test preparation.
Learnable Classes of Categorial Grammars.
Kanazawa, Makoto
Learnability theory is an attempt to illuminate the concept of learnability using a mathematical model of learning. Two models of learning of categorial grammars are examined here: the standard model, in which sentences presented to the learner are flat strings of words, and one in which sentences are presented in the form of functor-argument…
Grammar Texts and Consumerist Subtexts
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…
Network Analysis with Stochastic Grammars
2015-09-17
rules N = 0 //non-terminal index clusters = cluster(W) //number of clusters drive the number S productions //cluster function described in text...Essa, “Recognizing multitasked activities from video using stochastic context-free grammar,” AAAI/IAAI, pp. 770–776, 2002. [18] R. Nevatia, T. Zhao
Dorvlo, Kofi
2008-01-01
This dissertation presents a comprehensive description of the grammar of Logba, one of the fourteen Ghana-Togo Mountain (GTM) languages spoken by approximately 7,500 speakers on the Southeastern frontier of the Ghana-Togo border. It is the outcome of fifteen months research in Logba speaking
Abstract Interpretation Using Attribute Grammar
DEFF Research Database (Denmark)
Rosendahl, Mads
1990-01-01
This paper deals with the correctness proofs of attribute grammars using methods from abstract interpretation. The technique will be described by defining a live-variable analysis for a small flow-chart language and proving it correct with respect to a continuation style semantics. The proof...
Inferring ontology graph structures using OWL reasoning
Rodriguez-Garcia, Miguel Angel; Hoehndorf, Robert
2018-01-01
' semantic content remains a challenge.We developed a method to transform ontologies into graphs using an automated reasoner while taking into account all relations between classes. Searching for (existential) patterns in the deductive closure of ontologies
Chartrand, Gary; Rosen, Kenneth H
2008-01-01
Beginning with the origin of the four color problem in 1852, the field of graph colorings has developed into one of the most popular areas of graph theory. Introducing graph theory with a coloring theme, Chromatic Graph Theory explores connections between major topics in graph theory and graph colorings as well as emerging topics. This self-contained book first presents various fundamentals of graph theory that lie outside of graph colorings, including basic terminology and results, trees and connectivity, Eulerian and Hamiltonian graphs, matchings and factorizations, and graph embeddings. The remainder of the text deals exclusively with graph colorings. It covers vertex colorings and bounds for the chromatic number, vertex colorings of graphs embedded on surfaces, and a variety of restricted vertex colorings. The authors also describe edge colorings, monochromatic and rainbow edge colorings, complete vertex colorings, several distinguishing vertex and edge colorings, and many distance-related vertex coloring...
Strategic Port Graph Rewriting: An Interactive Modelling and Analysis Framework
Directory of Open Access Journals (Sweden)
Maribel Fernández
2014-07-01
Full Text Available We present strategic portgraph rewriting as a basis for the implementation of visual modelling and analysis tools. The goal is to facilitate the specification, analysis and simulation of complex systems, using port graphs. A system is represented by an initial graph and a collection of graph rewriting rules, together with a user-defined strategy to control the application of rules. The strategy language includes constructs to deal with graph traversal and management of rewriting positions in the graph. We give a small-step operational semantics for the language, and describe its implementation in the graph transformation and visualisation tool PORGY.
XML Graphs in Program Analysis
DEFF Research Database (Denmark)
Møller, Anders; Schwartzbach, Michael Ignatieff
2007-01-01
XML graphs have shown to be a simple and effective formalism for representing sets of XML documents in program analysis. It has evolved through a six year period with variants tailored for a range of applications. We present a unified definition, outline the key properties including validation...... of XML graphs against different XML schema languages, and provide a software package that enables others to make use of these ideas. We also survey four very different applications: XML in Java, Java Servlets and JSP, transformations between XML and non-XML data, and XSLT....
Grammar Games: A Case for Instructionist Game Models to Enhance Grammar Awareness and Accuracy
Raftery, Brian; Santos, Jennifer
2015-01-01
Based on our own experiences teaching grammar in developmental writing classes and classes not dedicated to writing instruction, along with a history of scholarship that indicates a need for grammar pedagogies (e.g., Dougherty, 2012), instructor-designed grammar games can likely help facilitate learning about these mechanics of writing while…
Effect of X-Word Grammar and Traditional Grammar Instruction on Grammatical Accuracy
Livingston, Sue; Toce, Andi; Casey, Toce; Montoya, Fernando; Hart, Bonny R.; O'Flaherty, Carmela
2018-01-01
This study first briefly describes an instructional approach to teaching grammar known as X-Word Grammar and then compares its effectiveness in assisting students in achieving grammatical accuracy with traditionally taught grammar. Two groups of L2 pre-college students were taught using curricula and practice procedures in two different grammar…
Fast Parsing using Pruning and Grammar Specialization
Rayner, Manny; Carter, David
1996-01-01
We show how a general grammar may be automatically adapted for fast parsing of utterances from a specific domain by means of constituent pruning and grammar specialization based on explanation-based learning. These methods together give an order of magnitude increase in speed, and the coverage loss entailed by grammar specialization is reduced to approximately half that reported in previous work. Experiments described here suggest that the loss of coverage has been reduced to the point where ...
Multiword Constructions in the Grammar.
Culicover, Peter W; Jackendoff, Ray; Audring, Jenny
2017-07-01
There is ample evidence that speakers' linguistic knowledge extends well beyond what can be described in terms of rules of compositional interpretation stated over combinations of single words. We explore a range of multiword constructions (MWCs) to get a handle both on the extent of the phenomenon and on the grammatical constraints that may govern it. We consider idioms of various sorts, collocations, compounds, light verbs, syntactic nuts, and assorted other constructions, as well as morphology. Our conclusion is that MWCs highlight the central role that grammar plays in licensing MWCs in the lexicon and the creation of novel MWCs, and they help to clarify how the lexicon articulates with the rest of the grammar. Copyright © 2017 Cognitive Science Society, Inc.
DEFF Research Database (Denmark)
Bock, Lars Nicolai
2011-01-01
Artiklen diskuterer ordet "transformation" med udgangspunkt i dels hvorledes ordet bruges i arkitektfaglig terminologi og dels med fokus på ordets potentielle indhold og egnethed i samme teminologi.......Artiklen diskuterer ordet "transformation" med udgangspunkt i dels hvorledes ordet bruges i arkitektfaglig terminologi og dels med fokus på ordets potentielle indhold og egnethed i samme teminologi....
Energy Technology Data Exchange (ETDEWEB)
LACKS,S.A.
2003-10-09
Transformation, which alters the genetic makeup of an individual, is a concept that intrigues the human imagination. In Streptococcus pneumoniae such transformation was first demonstrated. Perhaps our fascination with genetics derived from our ancestors observing their own progeny, with its retention and assortment of parental traits, but such interest must have been accelerated after the dawn of agriculture. It was in pea plants that Gregor Mendel in the late 1800s examined inherited traits and found them to be determined by physical elements, or genes, passed from parents to progeny. In our day, the material basis of these genetic determinants was revealed to be DNA by the lowly bacteria, in particular, the pneumococcus. For this species, transformation by free DNA is a sexual process that enables cells to sport new combinations of genes and traits. Genetic transformation of the type found in S. pneumoniae occurs naturally in many species of bacteria (70), but, initially only a few other transformable species were found, namely, Haemophilus influenzae, Neisseria meningitides, Neisseria gonorrheae, and Bacillus subtilis (96). Natural transformation, which requires a set of genes evolved for the purpose, contrasts with artificial transformation, which is accomplished by shocking cells either electrically, as in electroporation, or by ionic and temperature shifts. Although such artificial treatments can introduce very small amounts of DNA into virtually any type of cell, the amounts introduced by natural transformation are a million-fold greater, and S. pneumoniae can take up as much as 10% of its cellular DNA content (40).
Graph visualization (Invited talk)
Wijk, van J.J.; Kreveld, van M.J.; Speckmann, B.
2012-01-01
Black and white node link diagrams are the classic method to depict graphs, but these often fall short to give insight in large graphs or when attributes of nodes and edges play an important role. Graph visualization aims obtaining insight in such graphs using interactive graphical representations.
Analyzing Ambiguity of Context-Free Grammars
DEFF Research Database (Denmark)
Brabrand, Claus; Giegerich, Robert; Møller, Anders
2010-01-01
It has been known since 1962 that the ambiguity problem for context-free grammars is undecidable. Ambiguity in context-free grammars is a recurring problem in language design and parser generation, as well as in applications where grammars are used as models of real-world physical structures. We...... observe that there is a simple linguistic characterization of the grammar ambiguity problem, and we show how to exploit this by presenting an ambiguity analysis framework based on conservative language approximations. As a concrete example, we propose a technique based on local regular approximations...
Grammar Teaching in Chinese Tertiary Education
Institute of Scientific and Technical Information of China (English)
LAN Hui-hui
2016-01-01
Grammar teaching, as one essential aspect of English language teaching (ELT), has been and continues to be an area of some controversy and debates, which entails the emergency of diverse classroom practices for language teachers:Focus on Form or Focus on FormS. Connected with the specific context of grammar teaching in Chinese higher education, this paper tends to re-consider the place of grammar teaching in the classroom, and come up with some feasible approaches to instructing grammar so as to make appropriate connections between grammatical forms and the meanings.
Grammar and Its Teaching: Challenging the Myths
Institute of Scientific and Technical Information of China (English)
Diane Larsen-Freeman
2008-01-01
@@ Grammar is often misunderstood in the language teaching field.The misconception lies in the view that grammar is a collection of arbitrary rules about static structures in the language.Further questionable claims are that the structures do not have to be taught,learners will acquire them on their own,or if the structures are taught,the lessons that ensue will he boring.Consequently,communicative and proficiency-based teaching approaches sometimes unduly limit grammar instruction.Of the many claims about grammar that deserve to be called myths,this digest will challenge ten.
The relationship between grammar and the psychological ...
African Journals Online (AJOL)
The relationship between grammar and the psychological processing of language. ... manner in which speakers perceive and psycholinguistically process information. ... order, metaphorical extensions, processing constraints, end-focus theory
The minimalist grammar of action
Pastra, Katerina; Aloimonos, Yiannis
2012-01-01
Language and action have been found to share a common neural basis and in particular a common ‘syntax’, an analogous hierarchical and compositional organization. While language structure analysis has led to the formulation of different grammatical formalisms and associated discriminative or generative computational models, the structure of action is still elusive and so are the related computational models. However, structuring action has important implications on action learning and generalization, in both human cognition research and computation. In this study, we present a biologically inspired generative grammar of action, which employs the structure-building operations and principles of Chomsky's Minimalist Programme as a reference model. In this grammar, action terminals combine hierarchically into temporal sequences of actions of increasing complexity; the actions are bound with the involved tools and affected objects and are governed by certain goals. We show, how the tool role and the affected-object role of an entity within an action drives the derivation of the action syntax in this grammar and controls recursion, merge and move, the latter being mechanisms that manifest themselves not only in human language, but in human action too. PMID:22106430
Baker, W.R.
1959-08-25
Transformers of a type adapted for use with extreme high power vacuum tubes where current requirements may be of the order of 2,000 to 200,000 amperes are described. The transformer casing has the form of a re-entrant section being extended through an opening in one end of the cylinder to form a coaxial terminal arrangement. A toroidal multi-turn primary winding is disposed within the casing in coaxial relationship therein. In a second embodiment, means are provided for forming the casing as a multi-turn secondary. The transformer is characterized by minimized resistance heating, minimized external magnetic flux, and an economical construction.
Pragmatic Graph Rewriting Modifications
Rodgers, Peter; Vidal, Natalia
1999-01-01
We present new pragmatic constructs for easing programming in visual graph rewriting programming languages. The first is a modification to the rewriting process for nodes the host graph, where nodes specified as 'Once Only' in the LHS of a rewrite match at most once with a corresponding node in the host graph. This reduces the previously common use of tags to indicate the progress of matching in the graph. The second modification controls the application of LHS graphs, where those specified a...
Bapat, Ravindra B
2014-01-01
This new edition illustrates the power of linear algebra in the study of graphs. The emphasis on matrix techniques is greater than in other texts on algebraic graph theory. Important matrices associated with graphs (for example, incidence, adjacency and Laplacian matrices) are treated in detail. Presenting a useful overview of selected topics in algebraic graph theory, early chapters of the text focus on regular graphs, algebraic connectivity, the distance matrix of a tree, and its generalized version for arbitrary graphs, known as the resistance matrix. Coverage of later topics include Laplacian eigenvalues of threshold graphs, the positive definite completion problem and matrix games based on a graph. Such an extensive coverage of the subject area provides a welcome prompt for further exploration. The inclusion of exercises enables practical learning throughout the book. In the new edition, a new chapter is added on the line graph of a tree, while some results in Chapter 6 on Perron-Frobenius theory are reo...
Teaching english grammar through interactive methods
Aminova N.
2016-01-01
The article is devoted for the effective ways of teaching grammar. Actuality of the theme is justified as it sets conditions for revealing high progress in teaching a foreign language and for developing effective methods which can be helpful for foreign language teachers. Different progressive methods of teaching English grammar are given in this paper as well.
Research into Practice: Grammar Learning and Teaching
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).…
Left-forbidding cooperating distributed grammar systems
Czech Academy of Sciences Publication Activity Database
Goldefus, F.; Masopust, Tomáš; Meduna, A.
2010-01-01
Roč. 411, 40-42 (2010), s. 3661-3667 ISSN 0304-3975 Institutional research plan: CEZ:AV0Z10190503 Keywords : cooperating distributed grammar system * cooperating derivation mode * left-forbidding grammar * generative power * descriptional complexity Subject RIV: BA - General Mathematics Impact factor: 0.838, year: 2010 http://www.sciencedirect.com/science/article/pii/S0304397510003440
Grammar and Usage: History and Myth
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…
Propelling Students into Active Grammar Participation
Jurhill, Dennis A.
2011-01-01
"O! this learning, what a thing it is." -W. Shakespeare, "The Taming of the Shrew." The aim of this action research was to find out if active grammar involvement amongst students might lead to better results. My approach was to activate my students during grammar instruction by using cooperative learning: that is a form of…
Probe into Methods of Teaching English Grammar
Institute of Scientific and Technical Information of China (English)
刘春华
2011-01-01
@@ 1 Definition of grammar People sometlmes descibe grammaras the "rules" of a language, to be accurate,grammar is the science dealing with thesystematic rules of a language,its forms,inflections,syntax,and the rules of usingthem correctly.It is summarized from lan-guage use and practice,and reflects thelogic of thinking in people's speech orwriting.
Studying Grammar in the Technological Age
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…
Flexible Processing and the Design of Grammar
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…
Towards a Pedagogy of Grammar Instruction
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…
Reading and Grammar Learning through Mobile Phones
Wang, Shudong; Smith, Simon
2013-01-01
This paper describes an ongoing language-learning project, three years into its development. We examine both the feasibility and the limitations of developing English reading and grammar skills through the interface of mobile phones. Throughout the project, reading and grammar materials were regularly sent to students' mobile phones. Students read…
HIGHER ORDER THINKING IN TEACHING GRAMMAR
Directory of Open Access Journals (Sweden)
Citra Dewi
2017-04-01
Full Text Available The aim of this paper discussed about how to enhance students’ higher order thinking that should be done by teacher in teaching grammar. Usually teaching grammar was boring and has the same way to learn like change the pattern of sentence into positive, negative and introgative while the students’ need more various way to develop their thinking. The outcome of students’ competence in grammar sometimes not sufficient enough when the students’ occured some test international standart like Test of English Foreign Language, International English Language Testing. Whereas in TOEFL test it needed higher order thinking answer, so teacher should develop students’ higher order thingking in daily teaching grammar in order to make the students’ enhance their thinking are higher. The method was used in this paper by using field study based on the experience of teaching grammar. It can be shown by students’ toefl score was less in stucture and written expression. The result of this paper was after teacher gave some treatments to enhance students’ higher order thinking in teaching grammar, the students’ toefl scores are sufficient enough as a part of stucture and written expression. It can concluded that it needed some strategies to enhancce students higher order thinking by teaching grammar it can make students’ higher toefl score. Teachers should be creative and inovative to teach the students’ started from giving the students’ question or test in teaching grammar.
Adaptive Graph Convolutional Neural Networks
Li, Ruoyu; Wang, Sheng; Zhu, Feiyun; Huang, Junzhou
2018-01-01
Graph Convolutional Neural Networks (Graph CNNs) are generalizations of classical CNNs to handle graph data such as molecular data, point could and social networks. Current filters in graph CNNs are built for fixed and shared graph structure. However, for most real data, the graph structures varies in both size and connectivity. The paper proposes a generalized and flexible graph CNN taking data of arbitrary graph structure as input. In that way a task-driven adaptive graph is learned for eac...
Directory of Open Access Journals (Sweden)
C. Dalfo
2015-10-01
Full Text Available We study a family of graphs related to the $n$-cube. The middle cube graph of parameter k is the subgraph of $Q_{2k-1}$ induced by the set of vertices whose binary representation has either $k-1$ or $k$ number of ones. The middle cube graphs can be obtained from the well-known odd graphs by doubling their vertex set. Here we study some of the properties of the middle cube graphs in the light of the theory of distance-regular graphs. In particular, we completely determine their spectra (eigenvalues and their multiplicities, and associated eigenvectors.
Kolodny, Oren; Lotem, Arnon; Edelman, Shimon
2015-03-01
We introduce a set of biologically and computationally motivated design choices for modeling the learning of language, or of other types of sequential, hierarchically structured experience and behavior, and describe an implemented system that conforms to these choices and is capable of unsupervised learning from raw natural-language corpora. Given a stream of linguistic input, our model incrementally learns a grammar that captures its statistical patterns, which can then be used to parse or generate new data. The grammar constructed in this manner takes the form of a directed weighted graph, whose nodes are recursively (hierarchically) defined patterns over the elements of the input stream. We evaluated the model in seventeen experiments, grouped into five studies, which examined, respectively, (a) the generative ability of grammar learned from a corpus of natural language, (b) the characteristics of the learned representation, (c) sequence segmentation and chunking, (d) artificial grammar learning, and (e) certain types of structure dependence. The model's performance largely vindicates our design choices, suggesting that progress in modeling language acquisition can be made on a broad front-ranging from issues of generativity to the replication of human experimental findings-by bringing biological and computational considerations, as well as lessons from prior efforts, to bear on the modeling approach. Copyright © 2014 Cognitive Science Society, Inc.
Generation of components for software renovation factories from context-free grammars
Brand, van den M.G.J.; Sellink, M.P.A.; Verhoef, C.
2000-01-01
We present an approach for the generation of components for a software renovation factory. These components are generated from a contex-free grammar definition that recognizes the code that has to be renovated. We generate analysis and transformation components that can be instantiated with a
Using a Linguistic Theory of Humour in Teaching English Grammar
Abdulmajeed, Rufaidah Kamal; Hameed, Sarab Khalil
2017-01-01
Teachers who teach a new language grammar do not usually have the time and the proper situation to introduce humour when starting a new topic in grammar. There are many different opinions about teaching grammar. Many teachers seem to believe in the importance of grammar lessons devoted to a study of language rules and practical exercises. Other…
The Importance of English Grammar Teaching at College
Institute of Scientific and Technical Information of China (English)
孙丽伟
2012-01-01
This paper attempts to elaborate the importance of grammar teaching at college through the four linguistic skills: listening, speaking, reading,and writing.The nature of grammar determines the significance of grammar teaching. This paper shows the importance of grammar teaching from its relationship with listening,speaking,reading and writing.
A Survey of Grammar Instruction from Scholastic Perspective
Peng, Yanghua
2017-01-01
The study of grammar has been paid much attention and the grammar instruction becomes an emphasis and key problem in English language teaching and learning. How to instruct students grammar appropriately becomes controversial for some English teachers increasingly. Some linguistics, theorists and teachers hold that the grammar instruction should…
English Grammar and Thai University Students: An Insurmountable Linguistic Battle?
Saengboon, Saksit
2017-01-01
This study aimed at investigating English grammar knowledge of a group of Thai university students. The three main research questions revolved around their knowledge of English grammar, the kinds of difficulties they had encountered in using the grammar as well as their perceptions of the roles of grammar in using English. The participants were…
What English Teachers Need to Know about Grammar.
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)
The equivalence problem for LL- and LR-regular grammars
Nijholt, Antinus
1982-01-01
The equivalence problem for context-free grammars is "given two arbitrary grammars, do they generate the same language?" Since this is undecidable in general, attention has been restricted to decidable subclasses of the context-free grammars. For example, the classes of LL(k) grammars and real-time
Ambiguity Detection Methods for Context-Free Grammars
H.J.S. Basten (Bas)
2007-01-01
textabstractThe Meta-Environment enables the creation of grammars using the SDF formalism. From these grammars an SGLR parser can be generated. One of the advantages of these parsers is that they can handle the entire class of context-free grammars (CFGs). The grammar developer does not have to
Multi-rate equivalents of cyclo-static synchronous dataflow graphs
de Groote, Robert; Holzenspies, P.K.F.; Kuper, Jan; Smit, Gerardus Johannes Maria
In this paper, we present a transformation that takes a cyclo-static dataflow (CSDF) graph and produces an equivalent multi-rate synchronous dataflow (MRSDF) graph. This fills a gap in existing analysis techniques for synchronous dataflow graphs; transformations into equivalent homogeneous
Creation Myths of Generative Grammar and the Mathematics of Syntactic Structures
Pullum, Geoffrey K.
Syntactic Structures (Chomsky [6]) is widely believed to have laid the foundations of a cognitive revolution in linguistic science, and to have presented (i) the first use in linguistics of powerful new ideas regarding grammars as generative systems, (ii) a proof that English was not a regular language, (iii) decisive syntactic arguments against context-free phrase structure grammar description, and (iv) a demonstration of how transformational rules could provide a formal solution to those problems. None of these things are true. This paper offers a retrospective analysis and evaluation.
Kuźnik, Krzysztof
2013-06-01
This paper introduces a grammar-based model for developing a multi-thread multi-frontal parallel direct solver for one- dimensional isogeometric finite element method. The model includes the integration of B-splines for construction of the element local matrices and the multi-frontal solver algorithm. The integration and the solver algorithm are partitioned into basic indivisible tasks, namely the grammar productions, that can be executed squentially. The partial order of execution of the basic tasks is analyzed to provide the scheduling for the execution of the concurrent integration and multi-frontal solver algo- rithm. This graph grammar analysis allows for optimal concurrent execution of all tasks. The model has been implemented and tested on NVIDIA CUDA GPU, delivering logarithmic execution time for linear, quadratic, cubic and higher order B-splines. Thus, the CUDA implementation delivers the optimal performance predicted by our graph grammar analysis. We utilize the solver for multiple right hand sides related to the solution of non-stationary or inverse problems.
Chargaff's "Grammar of Biology": New Fractal-like Rules
Yamagishi, Michel Eduardo Beleza; Herai, Roberto H.
2011-01-01
Chargaff once said that "I saw before me in dark contours the beginning of a grammar of Biology". In linguistics, "grammar" is the set of natural language rules, but we do not know for sure what Chargaff meant by "grammar" of Biology. Nevertheless, assuming the metaphor, Chargaff himself started a "grammar of Biology" discovering the so called Chargaff's rules. In this work, we further develop his grammar. Using new concepts, we were able to discovery new genomic rules that seem to be invaria...
Soetevent, A.R.
2010-01-01
This paper extends Hotelling's model of price competition with quadratic transportation costs from a line to graphs. I propose an algorithm to calculate firm-level demand for any given graph, conditional on prices and firm locations. One feature of graph models of price competition is that spatial
Graphing Inequalities, Connecting Meaning
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…
Directory of Open Access Journals (Sweden)
Amine Labriji
2017-07-01
Full Text Available The topic of identifying the similarity of graphs was considered as highly recommended research field in the Web semantic, artificial intelligence, the shape recognition and information research. One of the fundamental problems of graph databases is finding similar graphs to a graph query. Existing approaches dealing with this problem are usually based on the nodes and arcs of the two graphs, regardless of parental semantic links. For instance, a common connection is not identified as being part of the similarity of two graphs in cases like two graphs without common concepts, the measure of similarity based on the union of two graphs, or the one based on the notion of maximum common sub-graph (SCM, or the distance of edition of graphs. This leads to an inadequate situation in the context of information research. To overcome this problem, we suggest a new measure of similarity between graphs, based on the similarity measure of Wu and Palmer. We have shown that this new measure satisfies the properties of a measure of similarities and we applied this new measure on examples. The results show that our measure provides a run time with a gain of time compared to existing approaches. In addition, we compared the relevance of the similarity values obtained, it appears that this new graphs measure is advantageous and offers a contribution to solving the problem mentioned above.
van Dam, Edwin R.; Koolen, Jack H.; Tanaka, Hajime
2016-01-01
This is a survey of distance-regular graphs. We present an introduction to distance-regular graphs for the reader who is unfamiliar with the subject, and then give an overview of some developments in the area of distance-regular graphs since the monograph 'BCN'[Brouwer, A.E., Cohen, A.M., Neumaier,
Fuzzy Graph Language Recognizability
Kalampakas , Antonios; Spartalis , Stefanos; Iliadis , Lazaros
2012-01-01
Part 5: Fuzzy Logic; International audience; Fuzzy graph language recognizability is introduced along the lines of the established theory of syntactic graph language recognizability by virtue of the algebraic structure of magmoids. The main closure properties of the corresponding class are investigated and several interesting examples of fuzzy graph languages are examined.
Brouwer, A.E.; Haemers, W.H.
2012-01-01
This book gives an elementary treatment of the basic material about graph spectra, both for ordinary, and Laplace and Seidel spectra. The text progresses systematically, by covering standard topics before presenting some new material on trees, strongly regular graphs, two-graphs, association
Unsupervised grammar induction of clinical report sublanguage.
Kate, Rohit J
2012-10-05
Clinical reports are written using a subset of natural language while employing many domain-specific terms; such a language is also known as a sublanguage for a scientific or a technical domain. Different genres of clinical reports use different sublaguages, and in addition, different medical facilities use different medical language conventions. This makes supervised training of a parser for clinical sentences very difficult as it would require expensive annotation effort to adapt to every type of clinical text. In this paper, we present an unsupervised method which automatically induces a grammar and a parser for the sublanguage of a given genre of clinical reports from a corpus with no annotations. In order to capture sentence structures specific to clinical domains, the grammar is induced in terms of semantic classes of clinical terms in addition to part-of-speech tags. Our method induces grammar by minimizing the combined encoding cost of the grammar and the corresponding sentence derivations. The probabilities for the productions of the induced grammar are then learned from the unannotated corpus using an instance of the expectation-maximization algorithm. Our experiments show that the induced grammar is able to parse novel sentences. Using a dataset of discharge summary sentences with no annotations, our method obtains 60.5% F-measure for parse-bracketing on sentences of maximum length 10. By varying a parameter, the method can induce a range of grammars, from very specific to very general, and obtains the best performance in between the two extremes.
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.
The Lattice-Valued Turing Machines and the Lattice-Valued Type 0 Grammars
Directory of Open Access Journals (Sweden)
Juan Tang
2014-01-01
Full Text Available Purpose. The purpose of this paper is to study a class of the natural languages called the lattice-valued phrase structure languages, which can be generated by the lattice-valued type 0 grammars and recognized by the lattice-valued Turing machines. Design/Methodology/Approach. From the characteristic of natural language, this paper puts forward a new concept of the l-valued Turing machine. It can be used to characterize recognition, natural language processing, and dynamic characteristics. Findings. The mechanisms of both the generation of grammars for the lattice-valued type 0 grammar and the dynamic transformation of the lattice-valued Turing machines were given. Originality/Value. This paper gives a new approach to study a class of natural languages by using lattice-valued logic theory.
Associative Cognitive CREED for Successful Grammar Learning
Directory of Open Access Journals (Sweden)
Andrias Tri Susanto
2016-06-01
Full Text Available This research article reports a qualitative study which was conducted to investigate ways successful EFL learners learned English grammar. The subjects of this research were eight successful EFL learners from six different countries in Asia: China, Indonesia, Japan, South Korea, Thailand, and Vietnam. The data was collected by interviewing each subject in person individually at an agreed time and place. The result showed that all the grammar learning processes described by the subjects were closely linked to the framework of Associative Cognitive CREED. There were also some contributing factors that could be integrally combined salient to the overall grammar learning process. However, interestingly, each subject emphasized different aspects of learning.
Hell, Pavol
2004-01-01
This is a book about graph homomorphisms. Graph theory is now an established discipline but the study of graph homomorphisms has only recently begun to gain wide acceptance and interest. The subject gives a useful perspective in areas such as graph reconstruction, products, fractional and circular colourings, and has applications in complexity theory, artificial intelligence, telecommunication, and, most recently, statistical physics.Based on the authors' lecture notes for graduate courses, this book can be used as a textbook for a second course in graph theory at 4th year or master's level an
Simplicial complexes of graphs
Jonsson, Jakob
2008-01-01
A graph complex is a finite family of graphs closed under deletion of edges. Graph complexes show up naturally in many different areas of mathematics, including commutative algebra, geometry, and knot theory. Identifying each graph with its edge set, one may view a graph complex as a simplicial complex and hence interpret it as a geometric object. This volume examines topological properties of graph complexes, focusing on homotopy type and homology. Many of the proofs are based on Robin Forman's discrete version of Morse theory. As a byproduct, this volume also provides a loosely defined toolbox for attacking problems in topological combinatorics via discrete Morse theory. In terms of simplicity and power, arguably the most efficient tool is Forman's divide and conquer approach via decision trees; it is successfully applied to a large number of graph and digraph complexes.
Introduction to quantum graphs
Berkolaiko, Gregory
2012-01-01
A "quantum graph" is a graph considered as a one-dimensional complex and equipped with a differential operator ("Hamiltonian"). Quantum graphs arise naturally as simplified models in mathematics, physics, chemistry, and engineering when one considers propagation of waves of various nature through a quasi-one-dimensional (e.g., "meso-" or "nano-scale") system that looks like a thin neighborhood of a graph. Works that currently would be classified as discussing quantum graphs have been appearing since at least the 1930s, and since then, quantum graphs techniques have been applied successfully in various areas of mathematical physics, mathematics in general and its applications. One can mention, for instance, dynamical systems theory, control theory, quantum chaos, Anderson localization, microelectronics, photonic crystals, physical chemistry, nano-sciences, superconductivity theory, etc. Quantum graphs present many non-trivial mathematical challenges, which makes them dear to a mathematician's heart. Work on qu...
Inferring ontology graph structures using OWL reasoning
Rodriguez-Garcia, Miguel Angel
2018-01-05
Ontologies are representations of a conceptualization of a domain. Traditionally, ontologies in biology were represented as directed acyclic graphs (DAG) which represent the backbone taxonomy and additional relations between classes. These graphs are widely exploited for data analysis in the form of ontology enrichment or computation of semantic similarity. More recently, ontologies are developed in a formal language such as the Web Ontology Language (OWL) and consist of a set of axioms through which classes are defined or constrained. While the taxonomy of an ontology can be inferred directly from the axioms of an ontology as one of the standard OWL reasoning tasks, creating general graph structures from OWL ontologies that exploit the ontologies\\' semantic content remains a challenge.We developed a method to transform ontologies into graphs using an automated reasoner while taking into account all relations between classes. Searching for (existential) patterns in the deductive closure of ontologies, we can identify relations between classes that are implied but not asserted and generate graph structures that encode for a large part of the ontologies\\' semantic content. We demonstrate the advantages of our method by applying it to inference of protein-protein interactions through semantic similarity over the Gene Ontology and demonstrate that performance is increased when graph structures are inferred using deductive inference according to our method. Our software and experiment results are available at http://github.com/bio-ontology-research-group/Onto2Graph .Onto2Graph is a method to generate graph structures from OWL ontologies using automated reasoning. The resulting graphs can be used for improved ontology visualization and ontology-based data analysis.
Inferring ontology graph structures using OWL reasoning.
Rodríguez-García, Miguel Ángel; Hoehndorf, Robert
2018-01-05
Ontologies are representations of a conceptualization of a domain. Traditionally, ontologies in biology were represented as directed acyclic graphs (DAG) which represent the backbone taxonomy and additional relations between classes. These graphs are widely exploited for data analysis in the form of ontology enrichment or computation of semantic similarity. More recently, ontologies are developed in a formal language such as the Web Ontology Language (OWL) and consist of a set of axioms through which classes are defined or constrained. While the taxonomy of an ontology can be inferred directly from the axioms of an ontology as one of the standard OWL reasoning tasks, creating general graph structures from OWL ontologies that exploit the ontologies' semantic content remains a challenge. We developed a method to transform ontologies into graphs using an automated reasoner while taking into account all relations between classes. Searching for (existential) patterns in the deductive closure of ontologies, we can identify relations between classes that are implied but not asserted and generate graph structures that encode for a large part of the ontologies' semantic content. We demonstrate the advantages of our method by applying it to inference of protein-protein interactions through semantic similarity over the Gene Ontology and demonstrate that performance is increased when graph structures are inferred using deductive inference according to our method. Our software and experiment results are available at http://github.com/bio-ontology-research-group/Onto2Graph . Onto2Graph is a method to generate graph structures from OWL ontologies using automated reasoning. The resulting graphs can be used for improved ontology visualization and ontology-based data analysis.
Abstract Expression Grammar Symbolic Regression
Korns, Michael F.
This chapter examines the use of Abstract Expression Grammars to perform the entire Symbolic Regression process without the use of Genetic Programming per se. The techniques explored produce a symbolic regression engine which has absolutely no bloat, which allows total user control of the search space and output formulas, which is faster, and more accurate than the engines produced in our previous papers using Genetic Programming. The genome is an all vector structure with four chromosomes plus additional epigenetic and constraint vectors, allowing total user control of the search space and the final output formulas. A combination of specialized compiler techniques, genetic algorithms, particle swarm, aged layered populations, plus discrete and continuous differential evolution are used to produce an improved symbolic regression sytem. Nine base test cases, from the literature, are used to test the improvement in speed and accuracy. The improved results indicate that these techniques move us a big step closer toward future industrial strength symbolic regression systems.
Cognitive grammar and aphasic discourse.
Manning, Molly; Franklin, Sue
2016-01-01
In cognitive grammar (CG), there is no clear division between language and other cognitive processes; all linguistic form is conceptually meaningful. In this pilot study, a CG approach was applied to investigate whether people with aphasia (PWA) have cognitive linguistic difficulty not predicted from traditional, componential models of aphasia. Narrative samples from 22 PWA (6 fluent, 16 non-fluent) were compared with samples from 10 participants without aphasia. Between-group differences were tested statistically. PWA had significant difficulty with temporal sequencing, suggesting problems that are not uniquely linguistic. For some, these problems were doubly dissociated with naming, used as a general measure of severity, which indicates that cognitive linguistic difficulties are not linked with more widespread brain damage. Further investigation may lead to a richer account of aphasia in line with contemporary linguistics and cognitive science approaches.
Measuring strategic control in artificial grammar learning.
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. Copyright © 2011 Elsevier Inc. All rights reserved.
Shape Grammars for Innovative Hybrid Typological Design
DEFF Research Database (Denmark)
Al-kazzaz, Dhuha; Bridges, Alan; Chase, Scott Curland
2010-01-01
This paper describes a new methodology of deriving innovative hybrid designs using shape grammars of heterogeneous designs. The method is detailed within three phases of shape grammars: analysis, synthesis and evaluation. In the analysis phase, the research suggests that original rules of each...... design component are grouped in subclass rule sets to facilitate rule choices. Additionally, adding new hybrid rules to original rules expands the options available to the grammar user. In the synthesis phase, the research adopts state labels and markers to drive the design generation. The former...... is implemented with a user guide grammar to ensure hybridity in the generated design, while the latter aims to ensure feasible designs. Lastly evaluation criteria are added to measure the degree of innovation of the hybrid designs. This paper describes the derivation of hybrid minaret designs from a corpus...
RAISING YOUNG LEARNERS‟ AWARENESS OF GRAMMAR THROUGH CREATIVE LANGUAGE ACTIVITIES
Directory of Open Access Journals (Sweden)
C. Murni Wahyanti
2017-04-01
Full Text Available Current developments in foreign language teaching have shown the need to reconsider the role of grammar. It is argued that grammar understanding can promote more precise use of the foreign language. This belief has led to an increased interest in grammar teaching, including grammar teaching for young learners. In teaching English to young learners, activities that can promote grammar awareness are needed. The activities should be presented in context to make sure that the meaning is clear. The activities should also be creatively designed in order to challenge students‘ motivation and involvement. Grammar activities presented creatively in meaningful contexts are useful for noticing the language patterns. This paper focuses on the changing status of grammar, the importance of grammar in the young learner classroom, and how to raise grammar awareness through creative language activities. It also reports the result of a small-scale study on implementing grammarawareness activities for teaching English to Elementary School students.
Simplifying Scalable Graph Processing with a Domain-Specific Language
Hong, Sungpack; Salihoglu, Semih; Widom, Jennifer; Olukotun, Kunle
2014-01-01
Large-scale graph processing, with its massive data sets, requires distributed processing. However, conventional frameworks for distributed graph processing, such as Pregel, use non-traditional programming models that are well-suited for parallelism and scalability but inconvenient for implementing non-trivial graph algorithms. In this paper, we use Green-Marl, a Domain-Specific Language for graph analysis, to intuitively describe graph algorithms and extend its compiler to generate equivalent Pregel implementations. Using the semantic information captured by Green-Marl, the compiler applies a set of transformation rules that convert imperative graph algorithms into Pregel's programming model. Our experiments show that the Pregel programs generated by the Green-Marl compiler perform similarly to manually coded Pregel implementations of the same algorithms. The compiler is even able to generate a Pregel implementation of a complicated graph algorithm for which a manual Pregel implementation is very challenging.
Simplifying Scalable Graph Processing with a Domain-Specific Language
Hong, Sungpack
2014-01-01
Large-scale graph processing, with its massive data sets, requires distributed processing. However, conventional frameworks for distributed graph processing, such as Pregel, use non-traditional programming models that are well-suited for parallelism and scalability but inconvenient for implementing non-trivial graph algorithms. In this paper, we use Green-Marl, a Domain-Specific Language for graph analysis, to intuitively describe graph algorithms and extend its compiler to generate equivalent Pregel implementations. Using the semantic information captured by Green-Marl, the compiler applies a set of transformation rules that convert imperative graph algorithms into Pregel\\'s programming model. Our experiments show that the Pregel programs generated by the Green-Marl compiler perform similarly to manually coded Pregel implementations of the same algorithms. The compiler is even able to generate a Pregel implementation of a complicated graph algorithm for which a manual Pregel implementation is very challenging.
Nigel: A Systemic Grammar for Text Generation.
1983-02-01
presumed. Basic references on the systemic framework include [Berry 75, Berry 77, Halliday 76a, Halliday 76b, Hudson 76, Halliday 81, de Joia 80...Edinburgh, 1979. [do Joia 80] de Joia , A., and A. Stanton, Terms in Systemic Linguistics, Batsford Academic and Educational, Ltd., London, 1980. -’C...1 A Grammar for Text Generation- -The Challenge ................................. 1 *1.2 A Grammar for Text Generation--The Design
The elements of grammar in 90 minutes
Hollander, Robert
2011-01-01
An eminent scholar explains the essentials of English grammar to those who never studied the basics as well as those who need a refresher course. Inspired by Strunk & White's classic The Elements of Style, this user-friendly guide focuses exclusively on grammar, explaining the individual parts of speech and their proper arrangement in sentence form. A modest investment of 90 minutes can provide readers of all ages with simple but important tools that will improve their communication skills. Dover (2011) original publication.
A Communicative Approach to College English Grammar Teaching and Learning
Institute of Scientific and Technical Information of China (English)
LI Yong-xian
2016-01-01
In response to the misconception that Communicative Language Teaching means no teaching of grammar, it is argued that grammar is as important as traffic rules for safe and smooth traffic on the road. To achieve appropriate and effective commu-nication, a communicative approach to college grammar teaching and learning is proposed. Both teachers and learners should change their attitudes toward and conceptions about grammar teaching and learning;additionally, teaching grammar in the com-pany of reading and writing helps learners learn and acquire grammar in meaningful contexts.
Winkler, A.P.
2016-01-01
The grammar written in Latin, in 1668, by the Jesuit missionary Father Diego Luis de Sanvitores (1627-1672) is the oldest description we have of Chamorro, a language spoken on the Mariana islands. The grammar received a number of bad reviews and as a consequence has become neglected and almost
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…
Chartrand, Gary
1984-01-01
Graph theory is used today in the physical sciences, social sciences, computer science, and other areas. Introductory Graph Theory presents a nontechnical introduction to this exciting field in a clear, lively, and informative style. Author Gary Chartrand covers the important elementary topics of graph theory and its applications. In addition, he presents a large variety of proofs designed to strengthen mathematical techniques and offers challenging opportunities to have fun with mathematics. Ten major topics - profusely illustrated - include: Mathematical Models, Elementary Concepts of Grap
Adriaan R. Soetevent
2010-01-01
This paper extends Hotelling's model of price competition with quadratic transportation costs from a line to graphs. I propose an algorithm to calculate firm-level demand for any given graph, conditional on prices and firm locations. One feature of graph models of price competition is that spatial discontinuities in firm-level demand may occur. I show that the existence result of D'Aspremont et al. (1979) does not extend to simple star graphs. I conjecture that this non-existence result holds...
Pim Heijnen; Adriaan Soetevent
2014-01-01
This paper extends Hotelling's model of price competition with quadratic transportation costs from a line to graphs. We derive an algorithm to calculate firm-level demand for any given graph, conditional on prices and firm locations. These graph models of price competition may lead to spatial discontinuities in firm-level demand. We show that the existence result of D'Aspremont et al. (1979) does not extend to simple star graphs and conjecture that this non-existence result holds more general...
Directory of Open Access Journals (Sweden)
Aleks Kissinger
2014-03-01
Full Text Available String diagrams are a powerful tool for reasoning about physical processes, logic circuits, tensor networks, and many other compositional structures. Dixon, Duncan and Kissinger introduced string graphs, which are a combinatoric representations of string diagrams, amenable to automated reasoning about diagrammatic theories via graph rewrite systems. In this extended abstract, we show how the power of such rewrite systems can be greatly extended by introducing pattern graphs, which provide a means of expressing infinite families of rewrite rules where certain marked subgraphs, called !-boxes ("bang boxes", on both sides of a rule can be copied any number of times or removed. After reviewing the string graph formalism, we show how string graphs can be extended to pattern graphs and how pattern graphs and pattern rewrite rules can be instantiated to concrete string graphs and rewrite rules. We then provide examples demonstrating the expressive power of pattern graphs and how they can be applied to study interacting algebraic structures that are central to categorical quantum mechanics.
Gelfand, I M; Shnol, E E
1969-01-01
The second in a series of systematic studies by a celebrated mathematician I. M. Gelfand and colleagues, this volume presents students with a well-illustrated sequence of problems and exercises designed to illuminate the properties of functions and graphs. Since readers do not have the benefit of a blackboard on which a teacher constructs a graph, the authors abandoned the customary use of diagrams in which only the final form of the graph appears; instead, the book's margins feature step-by-step diagrams for the complete construction of each graph. The first part of the book employs simple fu
Creating more effective graphs
Robbins, Naomi B
2012-01-01
A succinct and highly readable guide to creating effective graphs The right graph can be a powerful tool for communicating information, improving a presentation, or conveying your point in print. If your professional endeavors call for you to present data graphically, here's a book that can help you do it more effectively. Creating More Effective Graphs gives you the basic knowledge and techniques required to choose and create appropriate graphs for a broad range of applications. Using real-world examples everyone can relate to, the author draws on her years of experience in gr
Energy Technology Data Exchange (ETDEWEB)
Lothian, Joshua [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Powers, Sarah S. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Sullivan, Blair D. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Baker, Matthew B. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Schrock, Jonathan [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States); Poole, Stephen W. [Oak Ridge National Lab. (ORNL), Oak Ridge, TN (United States)
2013-10-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 different 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.
DEFF Research Database (Denmark)
Mansutti, Alessio; Miculan, Marino; Peressotti, Marco
2017-01-01
We introduce loose graph simulations (LGS), a new notion about labelled graphs which subsumes in an intuitive and natural way subgraph isomorphism (SGI), regular language pattern matching (RLPM) and graph simulation (GS). Being a unification of all these notions, LGS allows us to express directly...... also problems which are “mixed” instances of previous ones, and hence which would not fit easily in any of them. After the definition and some examples, we show that the problem of finding loose graph simulations is NP-complete, we provide formal translation of SGI, RLPM, and GS into LGSs, and we give...
Directory of Open Access Journals (Sweden)
Alberto Apostolico
2009-08-01
Full Text Available The Web Graph is a large-scale graph that does not fit in main memory, so that lossless compression methods have been proposed for it. This paper introduces a compression scheme that combines efficient storage with fast retrieval for the information in a node. The scheme exploits the properties of the Web Graph without assuming an ordering of the URLs, so that it may be applied to more general graphs. Tests on some datasets of use achieve space savings of about 10% over existing methods.
A Qualitative Approach to Sketch the Graph of a Function.
Alson, Pedro
1992-01-01
Presents a qualitative and global method of graphing functions that involves transformations of the graph of a known function in the cartesian coordinate system referred to as graphic operators. Explains how the method has been taught to students and some comments about the results obtained. (MDH)
Unsupervised grammar induction of clinical report sublanguage
Directory of Open Access Journals (Sweden)
Kate Rohit J
2012-10-01
Full Text Available Abstract Background Clinical reports are written using a subset of natural language while employing many domain-specific terms; such a language is also known as a sublanguage for a scientific or a technical domain. Different genres of clinical reports use different sublaguages, and in addition, different medical facilities use different medical language conventions. This makes supervised training of a parser for clinical sentences very difficult as it would require expensive annotation effort to adapt to every type of clinical text. Methods In this paper, we present an unsupervised method which automatically induces a grammar and a parser for the sublanguage of a given genre of clinical reports from a corpus with no annotations. In order to capture sentence structures specific to clinical domains, the grammar is induced in terms of semantic classes of clinical terms in addition to part-of-speech tags. Our method induces grammar by minimizing the combined encoding cost of the grammar and the corresponding sentence derivations. The probabilities for the productions of the induced grammar are then learned from the unannotated corpus using an instance of the expectation-maximization algorithm. Results Our experiments show that the induced grammar is able to parse novel sentences. Using a dataset of discharge summary sentences with no annotations, our method obtains 60.5% F-measure for parse-bracketing on sentences of maximum length 10. By varying a parameter, the method can induce a range of grammars, from very specific to very general, and obtains the best performance in between the two extremes.
Graph Theory. 1. Fragmentation of Structural Graphs
Directory of Open Access Journals (Sweden)
Lorentz JÄNTSCHI
2002-12-01
Full Text Available The investigation of structural graphs has many fields of applications in engineering, especially in applied sciences like as applied chemistry and physics, computer sciences and automation, electronics and telecommunication. The main subject of the paper is to express fragmentation criteria in graph using a new method of investigation: terminal paths. Using terminal paths are defined most of the fragmentation criteria that are in use in molecular topology, but the fields of applications are more generally than that, as I mentioned before. Graphical examples of fragmentation are given for every fragmentation criteria. Note that all fragmentation is made with a computer program that implements a routine for every criterion.[1] A web routine for tracing all terminal paths in graph can be found at the address: http://vl.academicdirect.ro/molecular_topology/tpaths/ [1] M. V. Diudea, I. Gutman, L. Jäntschi, Molecular Topology, Nova Science, Commack, New York, 2001, 2002.
Current Developments in Research on the Teaching of Grammar
Institute of Scientific and Technical Information of China (English)
Hossein Nassaji; Sandra Fotos
2006-01-01
@@ With the rise of communicative methodology in the late 1970s, the role of grammar instruction in second language learning was downplayed, and it was even suggested that teaching grammar was not only unhelpful but might actually be detrimental.
A few thoughts about teaching listening and grammar
Institute of Scientific and Technical Information of China (English)
吴西
2014-01-01
Listening and grammar are the most difficult subjects for both teacher and students. This passage discussed how to visual aid and brain storming in the listening class;and the importance of confidence in the grammar teaching and learning.
A graph rewriting programming language for graph drawing
Rodgers, Peter
1998-01-01
This paper describes Grrr, a prototype visual graph drawing tool. Previously there were no visual languages for programming graph drawing algorithms despite the inherently visual nature of the process. The languages which gave a diagrammatic view of graphs were not computationally complete and so could not be used to implement complex graph drawing algorithms. Hence current graph drawing tools are all text based. Recent developments in graph rewriting systems have produced computationally com...
Cohen, A.M.; Beineke, L.W.; Wilson, R.J.; Cameron, P.J.
2004-01-01
In this chapter we investigate the classification of distance-transitive graphs: these are graphs whose automorphism groups are transitive on each of the sets of pairs of vertices at distance i, for i = 0, 1,.... We provide an introduction into the field. By use of the classification of finite
Joyner, W David
2017-01-01
This textbook acts as a pathway to higher mathematics by seeking and illuminating the connections between graph theory and diverse fields of mathematics, such as calculus on manifolds, group theory, algebraic curves, Fourier analysis, cryptography and other areas of combinatorics. An overview of graph theory definitions and polynomial invariants for graphs prepares the reader for the subsequent dive into the applications of graph theory. To pique the reader’s interest in areas of possible exploration, recent results in mathematics appear throughout the book, accompanied with examples of related graphs, how they arise, and what their valuable uses are. The consequences of graph theory covered by the authors are complicated and far-reaching, so topics are always exhibited in a user-friendly manner with copious graphs, exercises, and Sage code for the computation of equations. Samples of the book’s source code can be found at github.com/springer-math/adventures-in-graph-theory. The text is geared towards ad...
Perepelitsa, VA; Sergienko, [No Value; Kochkarov, AM
1999-01-01
Definitions of prefractal and fractal graphs are introduced, and they are used to formulate mathematical models in different fields of knowledge. The topicality of fractal-graph recognition from the point of view, of fundamental improvement in the efficiency of the solution of algorithmic problems
DEFF Research Database (Denmark)
Husfeldt, Thore
2015-01-01
This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aims to demonstrate the breadth of available...
Packing Degenerate Graphs Greedily
Czech Academy of Sciences Publication Activity Database
Allen, P.; Böttcher, J.; Hladký, J.; Piguet, Diana
2017-01-01
Roč. 61, August (2017), s. 45-51 ISSN 1571-0653 R&D Projects: GA ČR GJ16-07822Y Institutional support: RVO:67985807 Keywords : tree packing conjecture * graph packing * graph processes Subject RIV: BA - General Mathematics OBOR OECD: Pure mathematics
Analyses of Common Grammar Mistakes in High-school English
Institute of Scientific and Technical Information of China (English)
Yang Liou
2017-01-01
English has an important position in the basic education stage as a language subject. English teaching requires students to have the abilities of listening, speaking, reading and writing in high school. If students want to learn these skills well, they should not only memorize vocabularies, but also master grammar knowledge. This paper illustrates the importance of English grammar for learning English and lists the common grammar mistakes. It also introduces some skills of learning English grammar.
A Review of the Development of Systemic-Functional Grammar
Institute of Scientific and Technical Information of China (English)
张晶
2014-01-01
50 years has seen Systemic-Functional Grammar(SFG)growing into its prosperity. With the efforts of Halliday and many other linguists, SFG has developed from Scale and Category Grammar to Systemic Grammar and then to Functional Gram-mar. The development of this general linguistic theory’s features and framework is the main focus of this study. SFG views lan-guage as a social semiotic resource people use to express meanings in context.
Constraints and Logic Programming in Grammars and Language Analysis
DEFF Research Database (Denmark)
Christiansen, Henning
2014-01-01
Constraints are an important notion in grammars and language analysis, and constraint programming techniques have been developed concurrently for solving a variety of complex problems. In this chapter we consider the synthesis of these branches into practical and effective methods for language...... methods that combine constraints with logic grammars such as Definite Clause Grammars and CHR Grammars, and show also a direct relationship to abductive reasoning....
Grammar in Context using Comprehended Input
Directory of Open Access Journals (Sweden)
Mariam Mohamed Nor
2014-03-01
Full Text Available There have been so many ongoing disputes on different approaches to teaching grammar. This study aims to evaluate the effectiveness of teaching grammar using Gass comprehended Input technique (GCI (1997 (implicit and to explore the undergraduates’ perception on the GCI technique. The respondents consisted of 30 undergraduates’ who are currently pursuing their Bachelor of English. Using the qualitative method, the research instrument was a set of 23- item interview and content analysis of the students’ written work. Results showed that the teaching of grammar using explicit instructions was more preferred than implicit instruction for complex components in grammatical rules. However, implicit instruction is equally effective regardless of the proficiency levels to enable pedagogy to be executed. It is also noted that there is lots of room for improvement, since the undergraduates have a weak grasp of the basic tense aspect of English grammar. Therefore, the Malaysian Ministry of Education should consider having grammar formally taught in isolation as what was practised previously.
Generalized connectivity of graphs
Li, Xueliang
2016-01-01
Noteworthy results, proof techniques, open problems and conjectures in generalized (edge-) connectivity are discussed in this book. Both theoretical and practical analyses for generalized (edge-) connectivity of graphs are provided. Topics covered in this book include: generalized (edge-) connectivity of graph classes, algorithms, computational complexity, sharp bounds, Nordhaus-Gaddum-type results, maximum generalized local connectivity, extremal problems, random graphs, multigraphs, relations with the Steiner tree packing problem and generalizations of connectivity. This book enables graduate students to understand and master a segment of graph theory and combinatorial optimization. Researchers in graph theory, combinatorics, combinatorial optimization, probability, computer science, discrete algorithms, complexity analysis, network design, and the information transferring models will find this book useful in their studies.
LR-parsing of Extended Context-free Grammars
DEFF Research Database (Denmark)
Madsen, Ole Lehrmann; Kristensen, Bent Bruun
1976-01-01
To improve the readability of a grammar it is common to use extended context free grammars (ECFGs) which are context free grammars (CFGs) extended with the repetition operator (*), the alternation operator (¦) and parentheses to express the right hand sides of the productions. The topic treated h...
Difficulties in Teaching and Learning Grammar in an EFL Context
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…
The structure of modern standard French a student grammar
Hansen, Maj-Britt Mosegaard
2016-01-01
This book is an advanced student's grammar of French that integrates traditional grammar with knowledge and insights from modern linguistics. It assumes some prior knowledge of French grammar but is designed to be accessible to those with no background in linguistics.
Indirect Positive Evidence in the Acquisition of a Subset Grammar
Schwartz, Misha; Goad, Heather
2017-01-01
This article proposes that second language learners can use indirect positive evidence (IPE) to acquire a phonological grammar that is a subset of their L1 grammar. IPE is evidence from errors in the learner's L1 made by native speakers of the learner's L2. It has been assumed that subset grammars may be acquired using direct or indirect negative…
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…
Spoken Grammar and Its Role in the English Language Classroom
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…
Grammar as a Programming Language. Artificial Intelligence Memo 391.
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…
Communicating Grammatically: Evaluating a Learner Strategy Website for Spanish Grammar
Cohen, Andrew D.; Pinilla-Herrera, Angela; Thompson, Jonathan R.; Witzig, Lance E.
2011-01-01
After a brief introduction to language learner strategies and grammar strategies as a subcategory, it is pointed out that research on the use of grammar strategies by learners of a second language (L2) has been limited. The article then describes the construction of a website with strategies for learning and performing Spanish grammar, with a…
The equivalence problem for LL- and LR-regular grammars
Nijholt, Antinus; Gecsec, F.
It will be shown that the equivalence problem for LL-regular grammars is decidable. Apart from extending the known result for LL(k) grammar equivalence to LLregular grammar equivalence, we obtain an alternative proof of the decidability of LL(k) equivalence. The equivalence prob]em for LL-regular
Linearly Ordered Attribute Grammar Scheduling Using SAT-Solving
Bransen, Jeroen; van Binsbergen, L.Thomas; Claessen, Koen; Dijkstra, Atze
2015-01-01
Many computations over trees can be specified using attribute grammars. Compilers for attribute grammars need to find an evaluation order (or schedule) in order to generate efficient code. For the class of linearly ordered attribute grammars such a schedule can be found statically, but this problem
Transformation language integration based on profiles and higher order transformations
Van Gorp, P.M.E.; Keller, A.; Janssens, D.; Gaševic, D.; Lämmel, R.; Van Wyk, Eric
2009-01-01
For about two decades, researchers have been constructing tools for applying graph transformations on large model transformation case studies. Instead of incrementally extending a common core, these competitive tool builders have repeatedly reconstructed mechanisms that were already supported by
Autoregressive Moving Average Graph Filtering
Isufi, Elvin; Loukas, Andreas; Simonetto, Andrea; Leus, Geert
2016-01-01
One of the cornerstones of the field of signal processing on graphs are graph filters, direct analogues of classical filters, but intended for signals defined on graphs. This work brings forth new insights on the distributed graph filtering problem. We design a family of autoregressive moving average (ARMA) recursions, which (i) are able to approximate any desired graph frequency response, and (ii) give exact solutions for tasks such as graph signal denoising and interpolation. The design phi...
Grammars with two-sided contexts
Directory of Open Access Journals (Sweden)
Mikhail Barash
2014-05-01
Full Text Available In a recent paper (M. Barash, A. Okhotin, "Defining contexts in context-free grammars", LATA 2012, the authors introduced an extension of the context-free grammars equipped with an operator for referring to the left context of the substring being defined. This paper proposes a more general model, in which context specifications may be two-sided, that is, both the left and the right contexts can be specified by the corresponding operators. The paper gives the definitions and establishes the basic theory of such grammars, leading to a normal form and a parsing algorithm working in time O(n^4, where n is the length of the input string.
The autonomy of grammar and semantic internalism
Directory of Open Access Journals (Sweden)
Dobler Tamara
2014-01-01
Full Text Available In his post-Tractatus work on natural language use, Wittgenstein defended the notion of what he dubbed the autonomy of grammar. According to this thought, grammar - or semantics, in a more recent idiom - is essentially autonomous from metaphysical considerations, and is not answerable to the nature of things. The argument has several related incarnations in Wittgenstein’s post-Tractatus writings, and has given rise to a number of important insights, both critical and constructive. In this paper I will argue for a potential connection between Wittgenstein’s autonomy argument and some more recent internalist arguments for the autonomy of semantics. My main motivation for establishing this connection comes from the fact that the later Wittgenstein’s comments on grammar and meaning stand in opposition to some of the core assumptions of semantic externalism.
Subgraph detection using graph signals
Chepuri, Sundeep Prabhakar
2017-03-06
In this paper we develop statistical detection theory for graph signals. In particular, given two graphs, namely, a background graph that represents an usual activity and an alternative graph that represents some unusual activity, we are interested in answering the following question: To which of the two graphs does the observed graph signal fit the best? To begin with, we assume both the graphs are known, and derive an optimal Neyman-Pearson detector. Next, we derive a suboptimal detector for the case when the alternative graph is not known. The developed theory is illustrated with numerical experiments.
Subgraph detection using graph signals
Chepuri, Sundeep Prabhakar; Leus, Geert
2017-01-01
In this paper we develop statistical detection theory for graph signals. In particular, given two graphs, namely, a background graph that represents an usual activity and an alternative graph that represents some unusual activity, we are interested in answering the following question: To which of the two graphs does the observed graph signal fit the best? To begin with, we assume both the graphs are known, and derive an optimal Neyman-Pearson detector. Next, we derive a suboptimal detector for the case when the alternative graph is not known. The developed theory is illustrated with numerical experiments.
Grammar-based Automatic 3D Model Reconstruction from Terrestrial Laser Scanning Data
Yu, Q.; Helmholz, P.; Belton, D.; West, G.
2014-04-01
The automatic reconstruction of 3D buildings has been an important research topic during the last years. In this paper, a novel method is proposed to automatically reconstruct the 3D building models from segmented data based on pre-defined formal grammar and rules. Such segmented data can be extracted e.g. from terrestrial or mobile laser scanning devices. Two steps are considered in detail. The first step is to transform the segmented data into 3D shapes, for instance using the DXF (Drawing Exchange Format) format which is a CAD data file format used for data interchange between AutoCAD and other program. Second, we develop a formal grammar to describe the building model structure and integrate the pre-defined grammars into the reconstruction process. Depending on the different segmented data, the selected grammar and rules are applied to drive the reconstruction process in an automatic manner. Compared with other existing approaches, our proposed method allows the model reconstruction directly from 3D shapes and takes the whole building into account.
EXPLAIN AND EXPLORE——THE INDUCTIVE APPROACH TO EFL GRAMMAR INSTRUCTION
Institute of Scientific and Technical Information of China (English)
YuGuoxing
2004-01-01
The new role of grammar instruction now is based on the increasing understandings that grammar per se is a comprehensive conglomerate. The paper examines the inductive approach to EFL grammar instruction. It starts with some theoretical considerations on inductive approach to formal grammar instruction, followed by its methodological considerations such as how to deal with grammar generalizations and exceptions, learner variables, and grammar complexity, and proposes a sensitive and dynamic balance of explorations and explanations in EFL grammar instruction.
Bollobas, Bela
2004-01-01
The ever-expanding field of extremal graph theory encompasses a diverse array of problem-solving methods, including applications to economics, computer science, and optimization theory. This volume, based on a series of lectures delivered to graduate students at the University of Cambridge, presents a concise yet comprehensive treatment of extremal graph theory.Unlike most graph theory treatises, this text features complete proofs for almost all of its results. Further insights into theory are provided by the numerous exercises of varying degrees of difficulty that accompany each chapter. A
DEVELOPING A SOUND POLICY FOR THE TREATMENT OF GRAMMAR
Institute of Scientific and Technical Information of China (English)
2001-01-01
Should grammar be taught at all?Is it a hindrance or anaid?Communicative language teaching approach seems to havecast doubts on the value of grammar teaching.The present paperargues that the positive effect of grammar in College Englishteaching and learning should not be overlooked.Grammar servesas a means to the final achievement of language proficiency.Itis time for language teachers to reconsider the role of grammarand to come up with a more appropriate and thus,moreeffective treatment of grammar in College English teaching.
A Contrastive Study of Two Approaches to Teach Grammar
Institute of Scientific and Technical Information of China (English)
Cai; Lin
2007-01-01
There are many kinds of methods of teaching grammar, no matter what they are, these approaches can generally be classified into two approaches-deductive and inductive. What an appropriate grammar teaching approach is by examining the inductive and deductive approaches to grammar teaching and learning. It starts with the definitions of inductive and deductive approaches to grammar teaching, followed by a contrastive study of these two approaches in terms of both the bases and the application. Finally, it explores the inductive approach and outlines the benefits of this approach and suggests an alternative view of grammar teaching.
Teaching Children Foreign-Language Grammar: Are Authentic Materials Appropriate?
Directory of Open Access Journals (Sweden)
Olga Malova
2016-10-01
Full Text Available The paper discusses authentic materials as a resource for teaching grammar to young learners. Difficulties in foreign-language grammar learning for Russian pupils are presented, and typical challenges are described. The paper provides a pre-/post-intervention study of the development of children’s grammar skills. The research question is, “How does one use authentic materials for teaching grammar in an English as a foreign language (EFL classroom?” A qualitative method is used to assess the learning outcomes of using authentic materials in teaching grammar to eight–nine-year-old pupils (the second year of studying English.
Transforming Graph Data for Statistical Relational Learning
2012-10-01
pairwise kernel for predicting links between proteins (protein-protein interactions). The pairwise kernel is a tensor -product of two linear kernels on...participate in the same “event,” such as both voting yes for the same political bill. Rather than directly labeling links (like ART), the GT model clusters...these nodes (such as people) into latent groups based on textual descriptions of the events/ votes . However, the GT model also simultaneously infers a set
Machine Translation Using Constraint-Based Synchronous Grammar
Institute of Scientific and Technical Information of China (English)
WONG Fai; DONG Mingchui; HU Dongcheng
2006-01-01
A synchronous grammar based on the formalism of context-free grammar was developed by generalizing the first component of production that models the source text. Unlike other synchronous grammars,the grammar allows multiple target productions to be associated to a single production rule which can be used to guide a parser to infer different possible translational equivalences for a recognized input string according to the feature constraints of symbols in the pattern. An extended generalized LR algorithm was adapted to the parsing of the proposed formalism to analyze the syntactic structure of a language. The grammar was used as the basis for building a machine translation system for Portuguese to Chinese translation. The empirical results show that the grammar is more expressive when modeling the translational equivalences of parallel texts for machine translation and grammar rewriting applications.
Directory of Open Access Journals (Sweden)
Haynes Teresa W.
2014-08-01
Full Text Available A path π = (v1, v2, . . . , vk+1 in a graph G = (V,E is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi ≥ deg(vi+1, where deg(vi denotes the degree of vertex vi ∈ V. The downhill domination number equals the minimum cardinality of a set S ⊆ V having the property that every vertex v ∈ V lies on a downhill path originating from some vertex in S. We investigate downhill domination numbers of graphs and give upper bounds. In particular, we show that the downhill domination number of a graph is at most half its order, and that the downhill domination number of a tree is at most one third its order. We characterize the graphs obtaining each of these bounds
Tailored Random Graph Ensembles
International Nuclear Information System (INIS)
Roberts, E S; Annibale, A; Coolen, A C C
2013-01-01
Tailored graph ensembles are a developing bridge between biological networks and statistical mechanics. The aim is to use this concept to generate a suite of rigorous tools that can be used to quantify and compare the topology of cellular signalling networks, such as protein-protein interaction networks and gene regulation networks. We calculate exact and explicit formulae for the leading orders in the system size of the Shannon entropies of random graph ensembles constrained with degree distribution and degree-degree correlation. We also construct an ergodic detailed balance Markov chain with non-trivial acceptance probabilities which converges to a strictly uniform measure and is based on edge swaps that conserve all degrees. The acceptance probabilities can be generalized to define Markov chains that target any alternative desired measure on the space of directed or undirected graphs, in order to generate graphs with more sophisticated topological features.
Alspach, BR
1985-01-01
This volume deals with a variety of problems involving cycles in graphs and circuits in digraphs. Leading researchers in this area present here 3 survey papers and 42 papers containing new results. There is also a collection of unsolved problems.
Wilson, Robin J
1985-01-01
Graph Theory has recently emerged as a subject in its own right, as well as being an important mathematical tool in such diverse subjects as operational research, chemistry, sociology and genetics. This book provides a comprehensive introduction to the subject.
Hyperbolicity in median graphs
Indian Academy of Sciences (India)
mic problems in hyperbolic spaces and hyperbolic graphs have been .... that in general the main obstacle is that we do not know the location of ...... [25] Jonckheere E and Lohsoonthorn P, A hyperbolic geometry approach to multipath routing,.
Resistance Distances in Vertex-Face Graphs
Shangguan, Yingmin; Chen, Haiyan
2018-01-01
The computation of two-point resistances in networks is a classical problem in electric circuit theory and graph theory. Let G be a triangulation graph with n vertices embedded on an orientable surface. Define K(G) to be the graph obtained from G by inserting a new vertex vϕ to each face ϕ of G and adding three new edges (u, vϕ), (v, vϕ) and (w, vϕ), where u, v and w are three vertices on the boundary of ϕ. In this paper, using star-triangle transformation and resistance local-sum rules, explicit relations between resistance distances in K(G) and those in G are obtained. These relations enable us to compute resistance distance between any two points of Kk(G) recursively. As explanation examples, some resistances in several networks are computed, including the modified Apollonian network and networks constructed from tetrahedron, octahedron and icosahedron, respectively.
Uniform Single Valued Neutrosophic Graphs
Directory of Open Access Journals (Sweden)
S. Broumi
2017-09-01
Full Text Available In this paper, we propose a new concept named the uniform single valued neutrosophic graph. An illustrative example and some properties are examined. Next, we develop an algorithmic approach for computing the complement of the single valued neutrosophic graph. A numerical example is demonstrated for computing the complement of single valued neutrosophic graphs and uniform single valued neutrosophic graph.
Collective Rationality in Graph Aggregation
Endriss, U.; Grandi, U.; Schaub, T.; Friedrich, G.; O'Sullivan, B.
2014-01-01
Suppose a number of agents each provide us with a directed graph over a common set of vertices. Graph aggregation is the problem of computing a single “collective” graph that best represents the information inherent in this profile of individual graphs. We consider this aggregation problem from the
Bollobás, Béla
1998-01-01
The time has now come when graph theory should be part of the education of every serious student of mathematics and computer science, both for its own sake and to enhance the appreciation of mathematics as a whole. This book is an in-depth account of graph theory, written with such a student in mind; it reflects the current state of the subject and emphasizes connections with other branches of pure mathematics. The volume grew out of the author's earlier book, Graph Theory -- An Introductory Course, but its length is well over twice that of its predecessor, allowing it to reveal many exciting new developments in the subject. Recognizing that graph theory is one of several courses competing for the attention of a student, the book contains extensive descriptive passages designed to convey the flavor of the subject and to arouse interest. In addition to a modern treatment of the classical areas of graph theory such as coloring, matching, extremal theory, and algebraic graph theory, the book presents a detailed ...
Phrasal alignment in Functional Discourse Grammar
van Rijn, M.
2011-01-01
Although the term is alignment is typically associated with morphosyntactic expression of arguments of the Clause, alignment is also relevant to units of the Phrase. In Functional Discourse Grammar a basic distinction is made between two kinds of dependency relations obtaining both within Phrases
On defining semantics of extended attribute grammars
DEFF Research Database (Denmark)
Madsen, Ole Lehrmann
1980-01-01
Knuth has introduced attribute grammars (AGs) as a tool to define the semanitcs of context-free languages. The use of AGs in connection with programming language definitions has mostly been to define the context-sensitive syntax of the language and to define a translation in code for a hypothetic...
On restricted context-free grammars
Czech Academy of Sciences Publication Activity Database
Dassow, J.; Masopust, Tomáš
2012-01-01
Roč. 78, č. 1 (2012), s. 293-304 ISSN 0022-0000 Institutional research plan: CEZ:AV0Z10190503 Keywords : context-free grammars * derivation restriction * normal forms Subject RIV: BA - General Mathematics Impact factor: 1.000, year: 2012 http://www.sciencedirect.com/science/article/pii/S0022000011000572
Case Grammar in Philippine Languages. Preliminary Draft.
Stevens, Alan M.
This paper presents evidence from Philippine languages which suggests a number of modifications in the theory of case grammar. Philippine languages and adjacent related languages mark the case relationship between the verb and one noun phrase in the sentence by a particle on the noun phrase and an affix on the verb, a phenomenon which in recent…
Assessing Primary Literacy through Grammar Tests
Hodgson, John
2017-01-01
Originally an editorial for "English in Education," this short article summarises key issues in the imposition of a separate test for grammar, punctuation and spelling. It illustrates the poor foundations, lack of clarity and distortion of curriculum which invalidate the test.
A BRIEF HINDI REFERENCE GRAMMAR. PRELIMINARY VERSION.
GUMPERZ, JOHN J.; MISRA, VIDYA NIWAS
THIS BRIEF OUTLINE OF HINDI PHONOLOGY AND GRAMMAR IS INTENDED FOR FIRST AND SECOND YEAR STUDENTS OF HINDI WHO HAVE SOME PREVIOUS KNOWLEDGE OF THE ORAL AND WRITTEN LANGUAGE BUT WHO MAY HAVE HAD NO PREVIOUS TRAINING IN LINGUISTIC TERMINOLOGY. THE AUTHORS HAVE THEREFORE EMPHASIZED SIMPLICITY AND READABILITY RATHER THAN EXHAUSTIVENESS OR ORIGINALITY…
Ontological semantics in modified categorial grammar
DEFF Research Database (Denmark)
Szymczak, Bartlomiej Antoni
2009-01-01
Categorial Grammar is a well established tool for describing natural language semantics. In the current paper we discuss some of its drawbacks and how it could be extended to overcome them. We use the extended version for deriving ontological semantics from text. A proof-of-concept implementation...
A Grammar of Spoken Brazilian Portuguese.
Thomas, Earl W.
This is a first-year text of Portuguese grammar based on the Portuguese of moderately educated Brazilians from the area around Rio de Janeiro. Spoken idiomatic usage is emphasized. An important innovation is found in the presentation of verb tenses; they are presented in the order in which the native speaker learns them. The text is intended to…
English Grammar for Students of French.
Morton, Jacqueline
This grammar is a self-study manual intended to aid native speakers of English who are beginning the study of French. It is designed to supplement the French textbook, not to replace it. The common grammatical terms that are necessary for learning to speak and write French are explained in English and illustrated by examples in both French and…
Ch(k) grammars: A characterization of LL(k) languages
Becvar, J.; Nijholt, Antinus; Soisalon-Soininen, E.
In this paper we introduce the class of so called Ch(k) grammars [pronounced "chain k grammars"]. This class of grammars is properly contained in the class of LR(k) grammars and it properly contains the LL(k) grammars. However, the family of Ch[k) languages coincides with the family of LL(k)
Interactive Russian Grammar: The Case System
Directory of Open Access Journals (Sweden)
Rimma Gam
2009-01-01
Full Text Available My paper addresses a problem many of us in North American college language programs confront regularly, the solution to which regularly and frustratingly remains just out of our reach. I refer to the teaching of the most basic and most crucial element of Russian grammar, namely, its case system, and teaching it to our students whose native language, English, does not have such a system. As I teach the Russian cases, I see vividly the disconnect between grammar presented for students (simplified, episodic, based on the "pick it up along the way" principle and the learned papers on Russian grammar by linguists, which are barely comprehensible to a non-linguist. Materials in the middle are lacking-materials to help a literature professor acting as a "de facto" language instructor understand and address the needs of students as they learn this crucial segment of basic Russian grammar. This core element of Russian grammar is presented to students in the first year of college language study, is revisited in the second year, and very often by the third year students either manage to completely block it out from their memory (as if it were some traumatic experience that happened "a long time ago"-that is, before .summer break-but most importantly due to the lack of practice or demonstrate a partial or even complete lack of understanding or misunderstanding of this system forcing us to deal with it again in the third year. Not only is it frustrating for both the students and the language instructor; but from the point of view of their overall proficiency, the lack of control of the case system holds our students back. There can be no talk of advanced language proficiency without a complete and automatic mastery of this basic system. Unfortunately, regardless of the specific textbooks used, the students very often manage not to have a general idea and mastery of this system even by the third year of study.
Transforming the Way We Teach Function Transformations
Faulkenberry, Eileen Durand; Faulkenberry, Thomas J.
2010-01-01
In this article, the authors discuss "function," a well-defined rule that relates inputs to outputs. They have found that by using the input-output definition of "function," they can examine transformations of functions simply by looking at changes to input or output and the respective changes to the graph. Applying transformations to the input…
Proxy Graph: Visual Quality Metrics of Big Graph Sampling.
Nguyen, Quan Hoang; Hong, Seok-Hee; Eades, Peter; Meidiana, Amyra
2017-06-01
Data sampling has been extensively studied for large scale graph mining. Many analyses and tasks become more efficient when performed on graph samples of much smaller size. The use of proxy objects is common in software engineering for analysis and interaction with heavy objects or systems. In this paper, we coin the term 'proxy graph' and empirically investigate how well a proxy graph visualization can represent a big graph. Our investigation focuses on proxy graphs obtained by sampling; this is one of the most common proxy approaches. Despite the plethora of data sampling studies, this is the first evaluation of sampling in the context of graph visualization. For an objective evaluation, we propose a new family of quality metrics for visual quality of proxy graphs. Our experiments cover popular sampling techniques. Our experimental results lead to guidelines for using sampling-based proxy graphs in visualization.
On some covering graphs of a graph
Directory of Open Access Journals (Sweden)
Shariefuddin Pirzada
2016-10-01
Full Text Available For a graph $G$ with vertex set $V(G=\\{v_1, v_2, \\dots, v_n\\}$, let $S$ be the covering set of $G$ having the maximum degree over all the minimum covering sets of $G$. Let $N_S[v]=\\{u\\in S : uv \\in E(G \\}\\cup \\{v\\}$ be the closed neighbourhood of the vertex $v$ with respect to $S.$ We define a square matrix $A_S(G= (a_{ij},$ by $a_{ij}=1,$ if $\\left |N_S[v_i]\\cap N_S[v_j] \\right| \\geq 1, i\
The STAPL Parallel Graph Library
Harshvardhan,
2013-01-01
This paper describes the stapl Parallel Graph Library, a high-level framework that abstracts the user from data-distribution and parallelism details and allows them to concentrate on parallel graph algorithm development. It includes a customizable distributed graph container and a collection of commonly used parallel graph algorithms. The library introduces pGraph pViews that separate algorithm design from the container implementation. It supports three graph processing algorithmic paradigms, level-synchronous, asynchronous and coarse-grained, and provides common graph algorithms based on them. Experimental results demonstrate improved scalability in performance and data size over existing graph libraries on more than 16,000 cores and on internet-scale graphs containing over 16 billion vertices and 250 billion edges. © Springer-Verlag Berlin Heidelberg 2013.
White, AT
1985-01-01
The field of topological graph theory has expanded greatly in the ten years since the first edition of this book appeared. The original nine chapters of this classic work have therefore been revised and updated. Six new chapters have been added, dealing with: voltage graphs, non-orientable imbeddings, block designs associated with graph imbeddings, hypergraph imbeddings, map automorphism groups and change ringing.Thirty-two new problems have been added to this new edition, so that there are now 181 in all; 22 of these have been designated as ``difficult'''' and 9 as ``unsolved''''. Three of the four unsolved problems from the first edition have been solved in the ten years between editions; they are now marked as ``difficult''''.
Ribes, Luis
2017-01-01
This book offers a detailed introduction to graph theoretic methods in profinite groups and applications to abstract groups. It is the first to provide a comprehensive treatment of the subject. The author begins by carefully developing relevant notions in topology, profinite groups and homology, including free products of profinite groups, cohomological methods in profinite groups, and fixed points of automorphisms of free pro-p groups. The final part of the book is dedicated to applications of the profinite theory to abstract groups, with sections on finitely generated subgroups of free groups, separability conditions in free and amalgamated products, and algorithms in free groups and finite monoids. Profinite Graphs and Groups will appeal to students and researchers interested in profinite groups, geometric group theory, graphs and connections with the theory of formal languages. A complete reference on the subject, the book includes historical and bibliographical notes as well as a discussion of open quest...
Subdominant pseudoultrametric on graphs
Energy Technology Data Exchange (ETDEWEB)
Dovgoshei, A A; Petrov, E A [Institute of Applied Mathematics and Mechanics, National Academy of Sciences of Ukraine, Donetsk (Ukraine)
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.
On the Balance of Grammar and Communication Teaching for Chinese Students
Institute of Scientific and Technical Information of China (English)
秦耀咏
2002-01-01
To the problem of neglecting grammar teaching when the Communicative approach is encouraged,this paper tries to analyze the position of teaching grammar and put forward some suggestions on how to balance grammar and communication teaching.
Graph based communication analysis for hardware/software codesign
DEFF Research Database (Denmark)
Knudsen, Peter Voigt; Madsen, Jan
1999-01-01
In this paper we present a coarse grain CDFG (Control/Data Flow Graph) model suitable for hardware/software partitioning of single processes and demonstrate how it is necessary to perform various transformations on the graph structure before partitioning in order to achieve a structure that allows...... for accurate estimation of communication overhead between nodes mapped to different processors. In particular, we demonstrate how various transformations of control structures can lead to a more accurate communication analysis and more efficient implementations. The purpose of the transformations is to obtain...
Quantitative graph theory mathematical foundations and applications
Dehmer, Matthias
2014-01-01
The first book devoted exclusively to quantitative graph theory, Quantitative Graph Theory: Mathematical Foundations and Applications presents and demonstrates existing and novel methods for analyzing graphs quantitatively. Incorporating interdisciplinary knowledge from graph theory, information theory, measurement theory, and statistical techniques, this book covers a wide range of quantitative-graph theoretical concepts and methods, including those pertaining to real and random graphs such as:Comparative approaches (graph similarity or distance)Graph measures to characterize graphs quantitat
Institute of Scientific and Technical Information of China (English)
廖芳
2016-01-01
Grammar is the guiding rules of language, and a good mastery of grammar is the basis of English learning. This paper starts from the problems in college students' current grammar learning and put forwards some strategies to improve their English grammar.
Cheung, King Sing
2014-01-01
Petri nets are a formal and theoretically rich model for the modelling and analysis of systems. A subclass of Petri nets, augmented marked graphs possess a structure that is especially desirable for the modelling and analysis of systems with concurrent processes and shared resources.This monograph consists of three parts: Part I provides the conceptual background for readers who have no prior knowledge on Petri nets; Part II elaborates the theory of augmented marked graphs; finally, Part III discusses the application to system integration. The book is suitable as a first self-contained volume
Dayal, Amit; Brock, David
2018-01-01
Prashant Chandrasekar, a lead developer for the Social Interactome project, has tasked the team with creating a graph representation of the data collected from the social networks involved in that project. The data is currently stored in a MySQL database. The client requested that the graph database be Cayley, but after a literature review, Neo4j was chosen. The reasons for this shift will be explained in the design section. Secondarily, the team was tasked with coming up with three scena...
Stevanovic, Dragan
2015-01-01
Spectral Radius of Graphs provides a thorough overview of important results on the spectral radius of adjacency matrix of graphs that have appeared in the literature in the preceding ten years, most of them with proofs, and including some previously unpublished results of the author. The primer begins with a brief classical review, in order to provide the reader with a foundation for the subsequent chapters. Topics covered include spectral decomposition, the Perron-Frobenius theorem, the Rayleigh quotient, the Weyl inequalities, and the Interlacing theorem. From this introduction, the
Graph embedding with rich information through heterogeneous graph
Sun, Guolei
2017-01-01
Graph embedding, aiming to learn low-dimensional representations for nodes in graphs, has attracted increasing attention due to its critical application including node classification, link prediction and clustering in social network analysis. Most
An Overview of the Nigel Text Generation Grammar.
1983-04-01
34 76b, Hudson 76, Halliday 81, de Joia 80, Fawcett 80].3 1.2. Design Goals for the Grammar Three kinds of goals have guided the work of creating Nigel...Davey 79] Davey, A., Discourse Production, Edinburgh University Press, Edinburgh, 1979. [ de Joia 80] de Joia , A., and A. Stenton, Terms in Systemic...1 1.1. The Text Generation Task as a Stimulus for Grammar Design .........................1I -1.2. Design Goals for the Grammar
Using Graph and Vertex Entropy to Compare Empirical Graphs with Theoretical Graph Models
Directory of Open Access Journals (Sweden)
Tomasz Kajdanowicz
2016-09-01
Full Text Available Over the years, several theoretical graph generation models have been proposed. Among the most prominent are: the Erdős–Renyi random graph model, Watts–Strogatz small world model, Albert–Barabási preferential attachment model, Price citation model, and many more. Often, researchers working with real-world data are interested in understanding the generative phenomena underlying their empirical graphs. They want to know which of the theoretical graph generation models would most probably generate a particular empirical graph. In other words, they expect some similarity assessment between the empirical graph and graphs artificially created from theoretical graph generation models. Usually, in order to assess the similarity of two graphs, centrality measure distributions are compared. For a theoretical graph model this means comparing the empirical graph to a single realization of a theoretical graph model, where the realization is generated from the given model using an arbitrary set of parameters. The similarity between centrality measure distributions can be measured using standard statistical tests, e.g., the Kolmogorov–Smirnov test of distances between cumulative distributions. However, this approach is both error-prone and leads to incorrect conclusions, as we show in our experiments. Therefore, we propose a new method for graph comparison and type classification by comparing the entropies of centrality measure distributions (degree centrality, betweenness centrality, closeness centrality. We demonstrate that our approach can help assign the empirical graph to the most similar theoretical model using a simple unsupervised learning method.
Topics in graph theory graphs and their Cartesian product
Imrich, Wilfried; Rall, Douglas F
2008-01-01
From specialists in the field, you will learn about interesting connections and recent developments in the field of graph theory by looking in particular at Cartesian products-arguably the most important of the four standard graph products. Many new results in this area appear for the first time in print in this book. Written in an accessible way, this book can be used for personal study in advanced applications of graph theory or for an advanced graph theory course.
Verbal prefixation, construction grammar, and semantic compatibility
DEFF Research Database (Denmark)
Lewandowski, Wojciech
2016-01-01
This paper aims to analyze the interaction between prefixes, verbs, and abstract argument structure constructions, using as a testing ground the locative alternation. It has been assumed that in order to participate in the locative alternation, a verb must specify a manner of motion from which a ...... between resultative prefixes, alternating verbs, and the more abstract change-of-state variant is driven by semantic coherence. Keywords: resultative prefixes, construction grammar, semantic coherence, locative alternation, Polish...
Dependency Grammar in Lithuanian Language Processing
Grigonytė, Gintarė
2006-01-01
Lithuanian language is quite in an early stage of language processing. And therefore has a high demand on automated tools like taggers, parsers, word sense disambiguators etc. During the last 10 years only a few researchers were attempting to create a parser for Lithuanian language. However none of them are used in practices nowadays. The process of designing and implementing rule based parser for Lithuanian language is presented in this paper. Rules and constraints of the formal grammar foll...
Experimental functional realization of attribute grammar system
Directory of Open Access Journals (Sweden)
I. Attali
2002-07-01
Full Text Available In this paper we present an experimental functional realization of attribute grammar(AG system for personal computers. For AG system functioning only Turbo Prolog compiler is required. The system functioning is based on a specially elaborated metalanguage for AG description, universal syntactic and semantic constructors. The AG system provides automatic generation of target compiler (syntax--oriented software using Turbo Prolog as object language.
Kiss my asterisk a feisty guide to punctuation and grammar
Baranick, Jenny
2014-01-01
Grammar has finally let its hair down! Unlike uptight grammar books that overwhelm us with every single grammar rule, Kiss My Asterisk is like a bikini: it's fun, flirty, and covers only the most important bits. Its lessons, which are 100 percent free of complicated grammar jargon, have been carefully selected to include today's most common, noticeable errors—the ones that confuse our readers or make them wonder if we are, in fact, smarter than a fifth grader. What is the proper use of an apostrophe? When should an ellipsis be used instead of an em dash? Why do we capitalize President Obama bu
Teaching English Grammar Through Communicative Language Teaching Approach
Institute of Scientific and Technical Information of China (English)
王玮
2013-01-01
Grammar is an important part of language learning. In order for students to have a functional knowledge of a language (in other words, that they can spontaneously produce language) they must have at least some knowledge about the grammatical con⁃structs of the language in question. How grammar can be taught? Considering various second language teaching methods, teaching grammar through Communicative Language Teaching Approach is the most talked. Emphasis in this article is put on the applica⁃tion of Communicative Language Teaching Approach in grammar teaching in college English classes.
Bisseling, R.H.; Byrka, J.; Cerav-Erbas, S.; Gvozdenovic, N.; Lorenz, M.; Pendavingh, R.A.; Reeves, C.; Röger, M.; Verhoeven, A.; Berg, van den J.B.; Bhulai, S.; Hulshof, J.; Koole, G.; Quant, C.; Williams, J.F.
2006-01-01
Splitting a large software system into smaller and more manageable units has become an important problem for many organizations. The basic structure of a software system is given by a directed graph with vertices representing the programs of the system and arcs representing calls from one program to
Coloring geographical threshold graphs
Energy Technology Data Exchange (ETDEWEB)
Bradonjic, Milan [Los Alamos National Laboratory; Percus, Allon [Los Alamos National Laboratory; Muller, Tobias [EINDHOVEN UNIV. OF TECH
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.
Budhiraja, A.S.; Mukherjee, D.; Wu, R.
2017-01-01
We consider a variation of the supermarket model in which the servers can communicate with their neighbors and where the neighborhood relationships are described in terms of a suitable graph. Tasks with unit-exponential service time distributions arrive at each vertex as independent Poisson
DEFF Research Database (Denmark)
Kucharik, Marcel; Hofacker, Ivo; Stadler, Peter
2014-01-01
of the folding free energy landscape, however, can provide the relevant information. Results We introduce the basin hopping graph (BHG) as a novel coarse-grained model of folding landscapes. Each vertex of the BHG is a local minimum, which represents the corresponding basin in the landscape. Its edges connect...
The STAPL Parallel Graph Library
Harshvardhan,; Fidel, Adam; Amato, Nancy M.; Rauchwerger, Lawrence
2013-01-01
This paper describes the stapl Parallel Graph Library, a high-level framework that abstracts the user from data-distribution and parallelism details and allows them to concentrate on parallel graph algorithm development. It includes a customizable
Winkler, A.P.
2016-01-01
The grammar written in Latin, in 1668, by the Jesuit missionary Father Diego Luis de Sanvitores (1627-1672) is the oldest description we have of Chamorro, a language spoken on the Mariana islands. The grammar received a number of bad reviews and as a consequence has become neglected and almost forgotten. The main point of criticism has been that Sanvitores used the Latin grammatical framework to explain a language that in many ways does not fit this framework. In this thesis it is argued inst...
Directory of Open Access Journals (Sweden)
Kaoru Takahashi
2013-08-01
Full Text Available In order for intermediate students poor at English grammar to enjoy learning it, a unique methodology has been improved in the classroom. In this article illustrated vehicles relevant to the five basic sentence patterns are presented in order to show how helpful this method is to understand English grammar. Also, more enhanced areas of this theory are discussed, which clarifies the feasibility of this methodology. The items to be introduced in my method are gerund, the passive voice, the relative pronoun and so on.
Energy Technology Data Exchange (ETDEWEB)
Winlaw, Manda [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States); De Sterck, Hans [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States); Sanders, Geoffrey [Lawrence Livermore National Lab. (LLNL), Livermore, CA (United States)
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.
Groupies in multitype random graphs
Shang, Yilun
2016-01-01
A groupie in a graph is a vertex whose degree is not less than the average degree of its neighbors. Under some mild conditions, we show that the proportion of groupies is very close to 1/2 in multitype random graphs (such as stochastic block models), which include Erd?s-R?nyi random graphs, random bipartite, and multipartite graphs as special examples. Numerical examples are provided to illustrate the theoretical results.
Groupies in multitype random graphs.
Shang, Yilun
2016-01-01
A groupie in a graph is a vertex whose degree is not less than the average degree of its neighbors. Under some mild conditions, we show that the proportion of groupies is very close to 1/2 in multitype random graphs (such as stochastic block models), which include Erdős-Rényi random graphs, random bipartite, and multipartite graphs as special examples. Numerical examples are provided to illustrate the theoretical results.
Temporal Representation in Semantic Graphs
Energy Technology Data Exchange (ETDEWEB)
Levandoski, J J; Abdulla, G M
2007-08-07
A wide range of knowledge discovery and analysis applications, ranging from business to biological, make use of semantic graphs when modeling relationships and concepts. Most of the semantic graphs used in these applications are assumed to be static pieces of information, meaning temporal evolution of concepts and relationships are not taken into account. Guided by the need for more advanced semantic graph queries involving temporal concepts, this paper surveys the existing work involving temporal representations in semantic graphs.
Quantum walks on quotient graphs
International Nuclear Information System (INIS)
Krovi, Hari; Brun, Todd A.
2007-01-01
A discrete-time quantum walk on a graph Γ 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
Heimbauer, Lisa A; Conway, Christopher M; Christiansen, Morten H; Beran, Michael J; Owren, Michael J
2018-03-01
Humans and nonhuman primates can learn about the organization of stimuli in the environment using implicit sequential pattern learning capabilities. However, most previous artificial grammar learning studies with nonhuman primates have involved relatively simple grammars and short input sequences. The goal in the current experiments was to assess the learning capabilities of monkeys on an artificial grammar-learning task that was more complex than most others previously used with nonhumans. Three experiments were conducted using a joystick-based, symmetrical-response serial reaction time task in which two monkeys were exposed to grammar-generated sequences at sequence lengths of four in Experiment 1, six in Experiment 2, and eight in Experiment 3. Over time, the monkeys came to respond faster to the sequences generated from the artificial grammar compared to random versions. In a subsequent generalization phase, subjects generalized their knowledge to novel sequences, responding significantly faster to novel instances of sequences produced using the familiar grammar compared to those constructed using an unfamiliar grammar. These results reveal that rhesus monkeys can learn and generalize the statistical structure inherent in an artificial grammar that is as complex as some used with humans, for sequences up to eight items long. These findings are discussed in relation to whether or not rhesus macaques and other primate species possess implicit sequence learning abilities that are similar to those that humans draw upon to learn natural language grammar.
Institute of Scientific and Technical Information of China (English)
余媛
2016-01-01
The present essay studies the role of grammar in young learners' classroom, perceived by the English teachers in China. The study gives a detailed description of what the role of grammar is like in young learners' classroom, by interviewing primary school teachers both from a city in a developed coastal city and a less developed city in central China. It highlights the differences in the perceptions of teachers on the prominence of grammar in their classes. These differences may indicate regional disparity and potential factors for teachers' teaching approaches to grammar instruction.
A generalization of total graphs
Indian Academy of Sciences (India)
M Afkhami
2018-04-12
Apr 12, 2018 ... product of any lower triangular matrix with the transpose of any element of U belongs to U. The ... total graph of R, which is denoted by T( (R)), is a simple graph with all elements of R as vertices, and ...... [9] Badawi A, On dot-product graph of a commutative ring, Communications in Algebra 43 (2015). 43–50.
On dominator colorings in graphs
Indian Academy of Sciences (India)
colors required for a dominator coloring of G is called the dominator .... Theorem 1.3 shows that the complete graph Kn is the only connected graph of order n ... Conversely, if a graph G satisfies condition (i) or (ii), it is easy to see that χd(G) =.
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.
Algorithms for Planar Graphs and Graphs in Metric Spaces
DEFF Research Database (Denmark)
Wulff-Nilsen, Christian
structural properties that can be exploited. For instance, a road network or a wire layout on a microchip is typically (near-)planar and distances in the network are often defined w.r.t. the Euclidean or the rectilinear metric. Specialized algorithms that take advantage of such properties are often orders...... of magnitude faster than the corresponding algorithms for general graphs. The first and main part of this thesis focuses on the development of efficient planar graph algorithms. The most important contributions include a faster single-source shortest path algorithm, a distance oracle with subquadratic...... for geometric graphs and graphs embedded in metric spaces. Roughly speaking, the stretch factor is a real value expressing how well a (geo-)metric graph approximates the underlying complete graph w.r.t. distances. We give improved algorithms for computing the stretch factor of a given graph and for augmenting...
Classification of group behaviors in social media via social behavior grammars
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.
A survey and comparison of transformation tools based on the transformation tool contest
Jakumeit, E.; Van Gorp, P.; Buchwald, S.; Rose, L.; Wagelaar, D.; Dan, L.; Hegedüs, Á; Hermannsdörfer, M.; Horn, T.; Kalnina, E.; Krause, C.; Lano, K.; Lepper, M.; Rensink, Arend; Rose, L.M.; Wätzoldt, S.; Mazanek, S.
Model transformation is one of the key tasks in model-driven engineering and relies on the efficient matching and modification of graph-based data structures; its sibling graph rewriting has been used to successfully model problems in a variety of domains. Over the last years, a wide range of graph
Harary, Frank
2015-01-01
Presented in 1962-63 by experts at University College, London, these lectures offer a variety of perspectives on graph theory. Although the opening chapters form a coherent body of graph theoretic concepts, this volume is not a text on the subject but rather an introduction to the extensive literature of graph theory. The seminar's topics are geared toward advanced undergraduate students of mathematics.Lectures by this volume's editor, Frank Harary, include ""Some Theorems and Concepts of Graph Theory,"" ""Topological Concepts in Graph Theory,"" ""Graphical Reconstruction,"" and other introduc
Spectral fluctuations of quantum graphs
International Nuclear Information System (INIS)
Pluhař, Z.; Weidenmüller, H. A.
2014-01-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
Dynamic Representations of Sparse Graphs
DEFF Research Database (Denmark)
Brodal, Gerth Stølting; Fagerberg, Rolf
1999-01-01
We present a linear space data structure for maintaining graphs with bounded arboricity—a large class of sparse graphs containing e.g. planar graphs and graphs of bounded treewidth—under edge insertions, edge deletions, and adjacency queries. The data structure supports adjacency queries in worst...... case O(c) time, and edge insertions and edge deletions in amortized O(1) and O(c+log n) time, respectively, where n is the number of nodes in the graph, and c is the bound on the arboricity....
Domination criticality in product graphs
Directory of Open Access Journals (Sweden)
M.R. Chithra
2015-07-01
Full Text Available A connected dominating set is an important notion and has many applications in routing and management of networks. Graph products have turned out to be a good model of interconnection networks. This motivated us to study the Cartesian product of graphs G with connected domination number, γc(G=2,3 and characterize such graphs. Also, we characterize the k−γ-vertex (edge critical graphs and k−γc-vertex (edge critical graphs for k=2,3 where γ denotes the domination number of G. We also discuss the vertex criticality in grids.
Study of Chromatic parameters of Line, Total, Middle graphs and Graph operators of Bipartite graph
Nagarathinam, R.; Parvathi, N.
2018-04-01
Chromatic parameters have been explored on the basis of graph coloring process in which a couple of adjacent nodes receives different colors. But the Grundy and b-coloring executes maximum colors under certain restrictions. In this paper, Chromatic, b-chromatic and Grundy number of some graph operators of bipartite graph has been investigat
Directory of Open Access Journals (Sweden)
Hussein Islam Abdullah
2015-01-01
Full Text Available Over the years, there has been a decline in the competency of the English Language in Malaysian schools. Many parties among them the Ministry of Education, relevant NGOs, academicians and people have expressed concern over the matter. The Education Ministry through its transformational policy has taken several measures to overcome the matter. It is employing appropriate strategies to solve the problems. The focus is on learning and teaching strategies as well as the content of the language. There is no doubt that grammar is a very important component in acquiring the language in primary and secondary schools. The English teachers mostly use the communicative approach in teaching grammar. This is in line with the KBSR syllabus in mid 1980s which emphasized on the communicative method. Teachers’ training and materials such as textbooks cater for the covert method. However, some tend to ignore the structural approach which is equally effective and meaningful to increase the level of the students’ proficiency which was popular in the 1960s. The paper discusses on the two different approaches used – the covert and overt approaches – their strengths as well as weaknesses. Application of both approaches is also taken into consideration giving a better view of how grammar should be taught in schools.
The Role of Teaching Grammar in First Language Education
Demir, Sezgin; Erdogan, Ayse
2018-01-01
Grammar; while originating from the natural structure of the language also is the system which makes it possible for different language functions meet within the body of common rules especially communication. Having command of the language used, speaking and writing it correctly require strong grammar knowledge actually. However only knowing the…
Current Issues in the Teaching of Grammar: An SLA Perspective
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…
Grammar Engineering Support for Precedence Rule Recovery and Compatibility Checking
Bouwers, E.; Bravenboer, M.; Visser, E.
2007-01-01
A wide range of parser generators are used to generate parsers for programming languages. The grammar formalisms that come with parser generators provide different approaches for defining operator precedence. Some generators (e.g. YACC) support precedence declarations, others require the grammar to
Enhancing Empirical Research for Linguistically Motivated Precision Grammars
Fokkens, A.S.
2014-01-01
Grammars of natural language are highly complex objects. This complexity is reflected in formal analyses found in both syntactic theory and computational grammars. In particular, there are two factors that make it notoriously difficult to make strong assertions about analyses for natural language
Environmental Peace Education in Foreign Language Learners' English Grammar Lessons
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…
Linearly Ordered Attribute Grammars : With Automatic Augmenting Dependency Selection
van Binsbergen, L. Thomas; Bransen, Jeroen; Dijkstra, Atze
2015-01-01
Attribute Grammars (AGs) extend Context-Free Grammars with attributes: information gathered on the syntax tree that adds semantics to the syntax. AGs are very well suited for describing static analyses, code-generation and other phases incorporated in a compiler. AGs are divided into classes based
Where Is She? Gender Occurrences in Online Grammar Guides
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…
The Effects of Using Online Concordancers on Teaching Grammar
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…
What is the Spirit of the English Grammar Teaching?
Institute of Scientific and Technical Information of China (English)
Haijiang Zhao
2016-01-01
In China,English is a foreign language,not a second language.Chinese students can't learn English well without learning its gram?mar first.As for English teachers,the most important is to help the students to grasp the spirit of English grammar learning.
Effect of Direct Grammar Instruction on Student Writing Skills
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…
Triumph through Texting: Restoring Learners' Interest in Grammar
Hedjazi Moghari, Mona; Marandi, S. Susan
2017-01-01
It is usually the case that learners of English as a foreign language (EFL) are exposed to language materials in class only, and of course in such a short space of time, they do not always find enough chance to practice English grammar features and become aware of their grammar mistakes. As a potential solution to this problem, the current study…
Sensing the Sentence: An Embodied Simulation Approach to Rhetorical Grammar
Rule, Hannah J.
2017-01-01
This article applies the neuroscientific concept of embodied simulation--the process of understanding language through visual, motor, and spatial modalities of the body--to rhetorical grammar and sentence-style pedagogies. Embodied simulation invigorates rhetorical grammar instruction by attuning writers to the felt effects of written language,…
ncRNA consensus secondary structure derivation using grammar strings.
Achawanantakun, Rujira; Sun, Yanni; Takyar, Seyedeh Shohreh
2011-04-01
Many noncoding RNAs (ncRNAs) function through both their sequences and secondary structures. Thus, secondary structure derivation is an important issue in today's RNA research. The state-of-the-art structure annotation tools are based on comparative analysis, which derives consensus structure of homologous ncRNAs. Despite promising results from existing ncRNA aligning and consensus structure derivation tools, there is a need for more efficient and accurate ncRNA secondary structure modeling and alignment methods. In this work, we introduce a consensus structure derivation approach based on grammar string, a novel ncRNA secondary structure representation that encodes an ncRNA's sequence and secondary structure in the parameter space of a context-free grammar (CFG) and a full RNA grammar including pseudoknots. Being a string defined on a special alphabet constructed from a grammar, grammar string converts ncRNA alignment into sequence alignment. We derive consensus secondary structures from hundreds of ncRNA families from BraliBase 2.1 and 25 families containing pseudoknots using grammar string alignment. Our experiments have shown that grammar string-based structure derivation competes favorably in consensus structure quality with Murlet and RNASampler. Source code and experimental data are available at http://www.cse.msu.edu/~yannisun/grammar-string.
Towards a Rationale for Research into Grammar Teaching in Schools
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…
Does Teaching Grammar Really Hinder Students＇ Speaking Abilities？
Institute of Scientific and Technical Information of China (English)
Kazumi Araki
2015-01-01
In the history of formal English education in Japan, grammar used to be the mainstream. In the secondary education system, teachers used to spend many hours teaching grammar to the students. However, it has been replaced by the aural/oral method of teaching a foreign language. There was even a remark that teaching grammar hinders students from communicating fluently. Literally, there was a time when grammar was set aside in formal English education. However, the author noticed that in grammar classes, the students speak English more loudly and confidently without much hesitation than in other types of English classes. One of the reasons is that they are not worried about the contents of the speeches. They are simply concentrating on the forms. They are not afraid of making major mistakes, and the errors they make are minor so they do not feel embarrassed in public. The atmosphere of the grammar classes is very positive and the students enjoy speaking English. In this paper, the author shows how grammar classes can contribute to the acquisition of the students＇ speaking abilities and manners. ＂Learning grammar was a precious experience＂, one student reported after the course.
Linguistics deviation, a tool for teaching English grammar: evidence ...
African Journals Online (AJOL)
We have always advocated that those teaching the Use of English must seek out novel ways of teaching the grammar of English to take out the drudgery of the present approach. Here, we proposed using Linguistic deviation as a tool for teaching English grammar. This approach will produce students who are both strong in ...
Construction Morphology and the Parallel Architecture of Grammar
Booij, Geert; Audring, Jenny
2017-01-01
This article presents a systematic exposition of how the basic ideas of Construction Grammar (CxG) (Goldberg, 2006) and the Parallel Architecture (PA) of grammar (Jackendoff, 2002]) provide the framework for a proper account of morphological phenomena, in particular word formation. This framework is referred to as Construction Morphology (CxM). As…
Spoken Grammar: An Urgent Necessity in the EFL Context
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…
Functional Grammar and Its Implications for English Teaching and Learning
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…
Metagrammar Engineering: Towards systematic exploration of implemented grammars
Fokkens, A.S.
2011-01-01
When designing grammars of natural language, typically, more than one formal analysis can account for a given phenomenon. Moreover, because analyses interact, the choices made by the engineer influence the possibilities available in further grammar development. The order in which phenomena are
John Ash and the Rise of the Children's Grammar
Navest, Karlijn Marianne
2011-01-01
From the second half of the eighteenth century onwards a knowledge of grammar served as an important marker of class in England. In order to enable their children to rise in society, middle-class parents expected their sons and daughters to learn English grammar. Since England did not have an
Concept-Based Grammar Teaching: An Academic Responds to Azar
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…
On the Equivalence of Formal Grammars and Machines.
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)
A Pure Object-Oriented Embedding of Attribute Grammars
Sloane, A.M.; Kats, L.C.L.; Visser, E.
2010-01-01
Attribute grammars are a powerful specification paradigm for many language processing tasks, particularly semantic analysis of programming languages. Recent attribute grammar systems use dynamic scheduling algorithms to evaluate attributes by need. In this paper, we show how to remove the need for a
Grammar for College Writing: A Sentence-Composing Approach
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…
The place of exclamatives and miratives in grammar: a functional discourse grammar view
Olbertz, H.
2012-01-01
The concept of mirativity has come to interfere in the recently developed framework of Functional Discourse Grammar with what would be considered to be exclamative elsewhere. In addition, the concept of exclamative itself turns out to be ill-defined in various studies within the functional paradigm.
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…
Graph Sampling for Covariance Estimation
Chepuri, Sundeep Prabhakar
2017-04-25
In this paper the focus is on subsampling as well as reconstructing the second-order statistics of signals residing on nodes of arbitrary undirected graphs. Second-order stationary graph signals may be obtained by graph filtering zero-mean white noise and they admit a well-defined power spectrum whose shape is determined by the frequency response of the graph filter. Estimating the graph power spectrum forms an important component of stationary graph signal processing and related inference tasks such as Wiener prediction or inpainting on graphs. The central result of this paper is that by sampling a significantly smaller subset of vertices and using simple least squares, we can reconstruct the second-order statistics of the graph signal from the subsampled observations, and more importantly, without any spectral priors. To this end, both a nonparametric approach as well as parametric approaches including moving average and autoregressive models for the graph power spectrum are considered. The results specialize for undirected circulant graphs in that the graph nodes leading to the best compression rates are given by the so-called minimal sparse rulers. A near-optimal greedy algorithm is developed to design the subsampling scheme for the non-parametric and the moving average models, whereas a particular subsampling scheme that allows linear estimation for the autoregressive model is proposed. Numerical experiments on synthetic as well as real datasets related to climatology and processing handwritten digits are provided to demonstrate the developed theory.
Hendrix, William; Jenkins, John; Padmanabhan, Kanchana; Chakraborty, Arpan
2014-01-01
Practical Graph Mining with R presents a "do-it-yourself" approach to extracting interesting patterns from graph data. It covers many basic and advanced techniques for the identification of anomalous or frequently recurring patterns in a graph, the discovery of groups or clusters of nodes that share common patterns of attributes and relationships, the extraction of patterns that distinguish one category of graphs from another, and the use of those patterns to predict the category of new graphs. Hands-On Application of Graph Data Mining Each chapter in the book focuses on a graph mining task, such as link analysis, cluster analysis, and classification. Through applications using real data sets, the book demonstrates how computational techniques can help solve real-world problems. The applications covered include network intrusion detection, tumor cell diagnostics, face recognition, predictive toxicology, mining metabolic and protein-protein interaction networks, and community detection in social networks. De...
Canonical Labelling of Site Graphs
Directory of Open Access Journals (Sweden)
Nicolas Oury
2013-06-01
Full Text Available We investigate algorithms for canonical labelling of site graphs, i.e. graphs in which edges bind vertices on sites with locally unique names. We first show that the problem of canonical labelling of site graphs reduces to the problem of canonical labelling of graphs with edge colourings. We then present two canonical labelling algorithms based on edge enumeration, and a third based on an extension of Hopcroft's partition refinement algorithm. All run in quadratic worst case time individually. However, one of the edge enumeration algorithms runs in sub-quadratic time for graphs with "many" automorphisms, and the partition refinement algorithm runs in sub-quadratic time for graphs with "few" bisimulation equivalences. This suite of algorithms was chosen based on the expectation that graphs fall in one of those two categories. If that is the case, a combined algorithm runs in sub-quadratic worst case time. Whether this expectation is reasonable remains an interesting open problem.
Learning heat diffusion graphs
Thanou, Dorina; Dong, Xiaowen; Kressner, Daniel; Frossard, Pascal
2016-01-01
Effective information analysis generally boils down to properly identifying the structure or geometry of the data, which is often represented by a graph. In some applications, this structure may be partly determined by design constraints or pre-determined sensing arrangements, like in road transportation networks for example. In general though, the data structure is not readily available and becomes pretty difficult to define. In particular, the global smoothness assumptions, that most of the...
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…
Understanding Charts and Graphs.
1987-07-28
Farenheit degrees, which have no Onaturalo zero ); finally, ratio scales have numbers that are ordered so that the magnitudes of differences are important and...system. They have to do with the very nature of how marks serve as meaningful symbols. In the ideal case, a chart or graph will be absolutely unambiguous...and these laws comprise this principle (see Stevens, 1974). Absolute discriminability: A minimal magnitude of a mark is necessary for it to be detected
Directory of Open Access Journals (Sweden)
Francesco P Battaglia
2011-08-01
Full Text Available 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.
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
Essential grammar for today's writers, students, and teachers
Sullivan, Nancy
2014-01-01
This innovative grammar text is an ideal resource for writers, language students, and current and future classroom teachers who need an accessible "refresher" in a step-by-step guide to essential grammar. Rather than becoming mired in overly detailed linguistic definitions, Nancy Sullivan helps writers and students understand and apply grammatical concepts and develop the skills they need to enhance their own writing. Along with engaging discussions of both contemporary and traditional terminology, Sullivan's text provides clear explanations of the basics of English grammar and a highly practical, hands-on approach to mastering the use of language. Complementing the focus on constructing excellent sentences, every example and exercise set is contextually grounded in language themes. Teachers, students, and writers will appreciate the streamlined, easy-to-understand coverage of essential grammar, as well as the affordable price. This is an ideal textbook for future teachers enrolled in an upper-level grammar c...
GRAMMAR IN TEFL: A CRITIQUE OF INDONESIAN HIGH SCHOOL TEXTBOOKS
Directory of Open Access Journals (Sweden)
Peter Collins
2006-01-01
Full Text Available Abstract: The aim of this paper is to critically assess the presentation of English grammar in textbooks used in secondary schools in Indonesia. The influence of the Communicative Approach is in evidence in the books examined, and yet the importance of explicit grammar instruction is not ignored, reflecting the view of many today that grammatical forms cannot be successfully learnt merely on the basis of comprehensible input. Despite recognition of its central role, the grammar instruction presented in the textbooks invites questions as to its linguistic adequacy and accuracy. Writers often seem unwilling to take on board the insights recorded in the influential and authoritative descriptive grammars of recent years, continuing to accept tacitly the principles exposed in Traditional Grammar.
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…
Formation of Robust Multi-Agent Networks through Self-Organizing Random Regular Graphs
Yasin Yazicioǧlu, A.; Egerstedt, Magnus; Shamma, Jeff S.
2015-01-01
Multi-Agent networks are often modeled as interaction graphs, where the nodes represent the agents and the edges denote some direct interactions. The robustness of a multi-Agent network to perturbations such as failures, noise, or malicious attacks largely depends on the corresponding graph. In many applications, networks are desired to have well-connected interaction graphs with relatively small number of links. One family of such graphs is the random regular graphs. In this paper, we present a decentralized scheme for transforming any connected interaction graph with a possibly non-integer average degree of k into a connected random m-regular graph for some m ϵ [k+k ] 2. Accordingly, the agents improve the robustness of the network while maintaining a similar number of links as the initial configuration by locally adding or removing some edges. © 2015 IEEE.
Formation of Robust Multi-Agent Networks through Self-Organizing Random Regular Graphs
Yasin Yazicioǧlu, A.
2015-11-25
Multi-Agent networks are often modeled as interaction graphs, where the nodes represent the agents and the edges denote some direct interactions. The robustness of a multi-Agent network to perturbations such as failures, noise, or malicious attacks largely depends on the corresponding graph. In many applications, networks are desired to have well-connected interaction graphs with relatively small number of links. One family of such graphs is the random regular graphs. In this paper, we present a decentralized scheme for transforming any connected interaction graph with a possibly non-integer average degree of k into a connected random m-regular graph for some m ϵ [k+k ] 2. Accordingly, the agents improve the robustness of the network while maintaining a similar number of links as the initial configuration by locally adding or removing some edges. © 2015 IEEE.
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…
The Effectiveness of Teaching Traditional Grammar on Writing Composition at the High School Level
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…
Understanding the Complex Processes in Developing Student Teachers' Knowledge about Grammar
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…
A brief analysis of the necessity of grammar teaching in CLT
Institute of Scientific and Technical Information of China (English)
胡晓; 王榛
2017-01-01
Grammar teaching is the important component of communicative language teaching, and also the teaching content of communicative approach. This study is going to analyze the status of English grammar learning, the theoretical basis of CLT, and some difficulties with regard to grammar education in China, while discussing teachers might try to adjust the current grammar approach in communicative English teaching.
How Should English Grammar Be Taught in Middle Schools By Wang Shikun
Institute of Scientific and Technical Information of China (English)
王仕坤
2014-01-01
This paper mainly deals with the idea that whether grammar teaching should be weakened or not ,the importance of grammar teaching,the present situation of grammar and some suggestions on how to teach grammar ,aiming at the improvement of English teaching and learning.
System dynamics and control with bond graph modeling
Kypuros, Javier
2013-01-01
Part I Dynamic System ModelingIntroduction to System DynamicsIntroductionSystem Decomposition and Model ComplexityMathematical Modeling of Dynamic SystemsAnalysis and Design of Dynamic SystemsControl of Dynamic SystemsDiagrams of Dynamic SystemsA Graph-Centered Approach to ModelingSummaryPracticeExercisesBasic Bond Graph ElementsIntroductionPower and Energy VariablesBasic 1-Port ElementsBasic 2-Ports ElementsJunction ElementsSimple Bond Graph ExamplesSummaryPracticeExercisesBond Graph Synthesis and Equation DerivationIntroductionGeneral GuidelinesMechanical TranslationMechanical RotationElectrical CircuitsHydraulic CircuitsMixed SystemsState Equation DerivationState-Space RepresentationsAlgebraic Loops and Derivative CausalitySummaryPracticeExercisesImpedance Bond GraphsIntroductionLaplace Transform of the State-Space EquationBasic 1-Port ImpedancesImpedance Bond Graph SynthesisJunctions, Transformers, and GyratorsEffort and Flow DividersSign ChangesTransfer Function DerivationAlternative Derivation of Transf...
Applied and computational harmonic analysis on graphs and networks
Irion, Jeff; Saito, Naoki
2015-09-01
In recent years, the advent of new sensor technologies and social network infrastructure has provided huge opportunities and challenges for analyzing data recorded on such networks. In the case of data on regular lattices, computational harmonic analysis tools such as the Fourier and wavelet transforms have well-developed theories and proven track records of success. It is therefore quite important to extend such tools from the classical setting of regular lattices to the more general setting of graphs and networks. In this article, we first review basics of graph Laplacian matrices, whose eigenpairs are often interpreted as the frequencies and the Fourier basis vectors on a given graph. We point out, however, that such an interpretation is misleading unless the underlying graph is either an unweighted path or cycle. We then discuss our recent effort of constructing multiscale basis dictionaries on a graph, including the Hierarchical Graph Laplacian Eigenbasis Dictionary and the Generalized Haar-Walsh Wavelet Packet Dictionary, which are viewed as generalizations of the classical hierarchical block DCTs and the Haar-Walsh wavelet packets, respectively, to the graph setting. Finally, we demonstrate the usefulness of our dictionaries by using them to simultaneously segment and denoise 1-D noisy signals sampled on regular lattices, a problem where classical tools have difficulty.
Graphs cospectral with a friendship graph or its complement
Directory of Open Access Journals (Sweden)
Alireza Abdollahi
2013-12-01
Full Text Available Let $n$ be any positive integer and let $F_n$ be the friendship (or Dutch windmill graph with $2n+1$ vertices and $3n$ edges. Here we study graphs with the same adjacency spectrum as the $F_n$. Two graphs are called cospectral if the eigenvalues multiset of their adjacency matrices are the same. Let $G$ be a graph cospectral with $F_n$. Here we prove that if $G$ has no cycle of length $4$ or $5$, then $Gcong F_n$. Moreover if $G$ is connected and planar then $Gcong F_n$.All but one of connected components of $G$ are isomorphic to $K_2$.The complement $overline{F_n}$ of the friendship graph is determined by its adjacency eigenvalues, that is, if $overline{F_n}$ is cospectral with a graph $H$, then $Hcong overline{F_n}$.
Design and validation of dynamic hierarchies and adaptive layouts using spatial graph grammars
Liao, K.; Kong, J.; Zhang, K.; de Vries, B.; Griffth, D.A.; Chun, Y.; Dean, D.J.
2017-01-01
With the thinking paradigm shifting on the evolution of complex adaptive systems, a pattern-based design approach is reviewed and reinterpreted. Although a variety of long-term and lasting explorations on patterns in geographical analysis, environmental planning, and design exist, in-depth
Industrial case study on the integration of SysML and AUTOSAR with triple graph grammars
Giese, Holger (Prof. Dr.); Hildebrandt, Stephan; Neumann, Stefan; Wätzoldt, Sebastian
2012-01-01
During the overall development of complex engineering systems different modeling notations are employed. For example, in the domain of automotive systems system engineering models are employed quite early to capture the requirements and basic structuring of the entire system, while software engineering models are used later on to describe the concrete software architecture. Each model helps in addressing the specific design issue with appropriate notations and at a suitable level of abstracti...
Decomposing Oriented Graphs into Six Locally Irregular Oriented Graphs
DEFF Research Database (Denmark)
Bensmail, Julien; Renault, Gabriel
2016-01-01
An undirected graph G is locally irregular if every two of its adjacent vertices have distinct degrees. We say that G is decomposable into k locally irregular graphs if there exists a partition E1∪E2∪⋯∪Ek of the edge set E(G) such that each Ei induces a locally irregular graph. It was recently co...
X-Graphs: Language and Algorithms for Heterogeneous Graph Streams
2017-09-01
are widely used by academia and industry. 15. SUBJECT TERMS Data Analytics, Graph Analytics, High-Performance Computing 16. SECURITY CLASSIFICATION...form the core of the DeepDive Knowledge Construction System. 2 INTRODUCTION The goal of the X-Graphs project was to develop computational techniques...memory multicore machine. Ringo is based on Snap.py and SNAP, and uses Python . Ringo now allows the integration of Delite DSL Framework Graph
A Contribution Towards A Grammar of Code
Directory of Open Access Journals (Sweden)
David M. Berry
2008-01-01
Full Text Available Over the past thirty years there has been an increasing interest in the social and cultural implications of digital technologies and ‘informationalism’ from the social sciences and humanities. Generally this has concentrated on the implications of the “convergence” of digital devices and services, understood as linked to the discrete processing capabilities of computers, which rely on logical operations, binary processing and symbolic representation. In this paper, I wish to suggest that a ‘grammar of code’ might provide a useful way of thinking about the way in which digital technologies operate as a medium and can contribute usefully to this wider debate. I am interested in the way in which the dynamic properties of code can be understood as operating according to a grammar reflected in its materialisation and operation in the lifeworld – the discretisation of the phenomenal world. As part of that contribution in this paper I develop some tentative Weberian ‘ideal-types’. These ideal-types are then applied to the work of the Japanese composer, Masahiro Miwa, whose innovative ‘Reverse-Simulation music’ models the operation of basic low-level digital circuitry for the performance and generation of musical pieces.
Information packaging in Functional Discourse Grammar
Directory of Open Access Journals (Sweden)
Niels Smit
2007-07-01
Full Text Available
The paper addresses the modelling of information packaging in Functional Discourse Grammar (FDG, in particular the treatment of Topic, Comment and Focus. Current FDG has inherited the traditional Functional Grammar (FG representation of these categories as functions, which attach to Subacts of evocation. However, arguments of a formal, notional and descriptive nature can be advanced against pragmatic function assignment and in favour of an alternative analysis in which informational and evocational structures are dissociated so as to command their own primitives. In the context of a model of discourse knowledge organisation in which communicated contents are associated with packaging instructions that tell the Addressee how to treat the evoked knowledge, it is argued that focality can be modelled by means of a Focus operator that can attach to various constituents at the Interpersonal Level. Topicality, on the other hand, concerns binomial and monomial modes of presenting communicated contents. This can be rendered by means of the dedicated informational units Topic (Top and Comment (Cm, that interact in frames.
Style grammars for interactive visualization of architecture.
Aliaga, Daniel G; Rosen, Paul A; Bekins, Daniel R
2007-01-01
Interactive visualization of architecture provides a way to quickly visualize existing or novel buildings and structures. Such applications require both fast rendering and an effortless input regimen for creating and changing architecture using high-level editing operations that automatically fill in the necessary details. Procedural modeling and synthesis is a powerful paradigm that yields high data amplification and can be coupled with fast-rendering techniques to quickly generate plausible details of a scene without much or any user interaction. Previously, forward generating procedural methods have been proposed where a procedure is explicitly created to generate particular content. In this paper, we present our work in inverse procedural modeling of buildings and describe how to use an extracted repertoire of building grammars to facilitate the visualization and quick modification of architectural structures and buildings. We demonstrate an interactive application where the user draws simple building blocks and, using our system, can automatically complete the building "in the style of" other buildings using view-dependent texture mapping or nonphotorealistic rendering techniques. Our system supports an arbitrary number of building grammars created from user subdivided building models and captured photographs. Using only edit, copy, and paste metaphors, the entire building styles can be altered and transferred from one building to another in a few operations, enhancing the ability to modify an existing architectural structure or to visualize a novel building in the style of the others.
Design Transformations for Rule-based Procedural Modeling
Lienhard, Stefan; Lau, Cheryl; Mü ller, Pascal; Wonka, Peter; Pauly, Mark
2017-01-01
We introduce design transformations for rule-based procedural models, e.g., for buildings and plants. Given two or more procedural designs, each specified by a grammar, a design transformation combines elements of the existing designs to generate new designs. We introduce two technical components to enable design transformations. First, we extend the concept of discrete rule switching to rule merging, leading to a very large shape space for combining procedural models. Second, we propose an algorithm to jointly derive two or more grammars, called grammar co-derivation. We demonstrate two applications of our work: we show that our framework leads to a larger variety of models than previous work, and we show fine-grained transformation sequences between two procedural models.
Design Transformations for Rule-based Procedural Modeling
Lienhard, Stefan
2017-05-24
We introduce design transformations for rule-based procedural models, e.g., for buildings and plants. Given two or more procedural designs, each specified by a grammar, a design transformation combines elements of the existing designs to generate new designs. We introduce two technical components to enable design transformations. First, we extend the concept of discrete rule switching to rule merging, leading to a very large shape space for combining procedural models. Second, we propose an algorithm to jointly derive two or more grammars, called grammar co-derivation. We demonstrate two applications of our work: we show that our framework leads to a larger variety of models than previous work, and we show fine-grained transformation sequences between two procedural models.
Endomorphisms of graph algebras
DEFF Research Database (Denmark)
Conti, Roberto; Hong, Jeong Hee; Szymanski, Wojciech
2012-01-01
We initiate a systematic investigation of endomorphisms of graph C*-algebras C*(E), extending several known results on endomorphisms of the Cuntz algebras O_n. Most but not all of this study is focused on endomorphisms which permute the vertex projections and globally preserve the diagonal MASA D...... that the restriction to the diagonal MASA of an automorphism which globally preserves both D_E and the core AF-subalgebra eventually commutes with the corresponding one-sided shift. Secondly, we exhibit several properties of proper endomorphisms, investigate invertibility of localized endomorphisms both on C...
Yap, Hian-Poh
1996-01-01
This book provides an up-to-date and rapid introduction to an important and currently active topic in graph theory. The author leads the reader to the forefront of research in this area. Complete and easily readable proofs of all the main theorems, together with numerous examples, exercises and open problems are given. The book is suitable for use as a textbook or as seminar material for advanced undergraduate and graduate students. The references are comprehensive and so it will also be useful for researchers as a handbook.
Implicit learning of recursive context-free grammars.
Rohrmeier, Martin; Fu, Qiufang; Dienes, Zoltan
2012-01-01
Context-free grammars are fundamental for the description of linguistic syntax. However, most artificial grammar learning experiments have explored learning of simpler finite-state grammars, while studies exploring context-free grammars have not assessed awareness and implicitness. This paper explores the implicit learning of context-free grammars employing features of hierarchical organization, recursive embedding and long-distance dependencies. The grammars also featured the distinction between left- and right-branching structures, as well as between centre- and tail-embedding, both distinctions found in natural languages. People acquired unconscious knowledge of relations between grammatical classes even for dependencies over long distances, in ways that went beyond learning simpler relations (e.g. n-grams) between individual words. The structural distinctions drawn from linguistics also proved important as performance was greater for tail-embedding than centre-embedding structures. The results suggest the plausibility of implicit learning of complex context-free structures, which model some features of natural languages. They support the relevance of artificial grammar learning for probing mechanisms of language learning and challenge existing theories and computational models of implicit learning.
Grammar-Based Specification and Parsing of Binary File Formats
Directory of Open Access Journals (Sweden)
William Underwood
2012-03-01
Full Text Available The capability to validate and view or play binary file formats, as well as to convert binary file formats to standard or current file formats, is critically important to the preservation of digital data and records. This paper describes the extension of context-free grammars from strings to binary files. Binary files are arrays of data types, such as long and short integers, floating-point numbers and pointers, as well as characters. The concept of an attribute grammar is extended to these context-free array grammars. This attribute grammar has been used to define a number of chunk-based and directory-based binary file formats. A parser generator has been used with some of these grammars to generate syntax checkers (recognizers for validating binary file formats. Among the potential benefits of an attribute grammar-based approach to specification and parsing of binary file formats is that attribute grammars not only support format validation, but support generation of error messages during validation of format, validation of semantic constraints, attribute value extraction (characterization, generation of viewers or players for file formats, and conversion to current or standard file formats. The significance of these results is that with these extensions to core computer science concepts, traditional parser/compiler technologies can potentially be used as a part of a general, cost effective curation strategy for binary file formats.
Implicit Learning of Recursive Context-Free Grammars
Rohrmeier, Martin; Fu, Qiufang; Dienes, Zoltan
2012-01-01
Context-free grammars are fundamental for the description of linguistic syntax. However, most artificial grammar learning experiments have explored learning of simpler finite-state grammars, while studies exploring context-free grammars have not assessed awareness and implicitness. This paper explores the implicit learning of context-free grammars employing features of hierarchical organization, recursive embedding and long-distance dependencies. The grammars also featured the distinction between left- and right-branching structures, as well as between centre- and tail-embedding, both distinctions found in natural languages. People acquired unconscious knowledge of relations between grammatical classes even for dependencies over long distances, in ways that went beyond learning simpler relations (e.g. n-grams) between individual words. The structural distinctions drawn from linguistics also proved important as performance was greater for tail-embedding than centre-embedding structures. The results suggest the plausibility of implicit learning of complex context-free structures, which model some features of natural languages. They support the relevance of artificial grammar learning for probing mechanisms of language learning and challenge existing theories and computational models of implicit learning. PMID:23094021
Implicit learning of recursive context-free grammars.
Directory of Open Access Journals (Sweden)
Martin Rohrmeier
Full Text Available Context-free grammars are fundamental for the description of linguistic syntax. However, most artificial grammar learning experiments have explored learning of simpler finite-state grammars, while studies exploring context-free grammars have not assessed awareness and implicitness. This paper explores the implicit learning of context-free grammars employing features of hierarchical organization, recursive embedding and long-distance dependencies. The grammars also featured the distinction between left- and right-branching structures, as well as between centre- and tail-embedding, both distinctions found in natural languages. People acquired unconscious knowledge of relations between grammatical classes even for dependencies over long distances, in ways that went beyond learning simpler relations (e.g. n-grams between individual words. The structural distinctions drawn from linguistics also proved important as performance was greater for tail-embedding than centre-embedding structures. The results suggest the plausibility of implicit learning of complex context-free structures, which model some features of natural languages. They support the relevance of artificial grammar learning for probing mechanisms of language learning and challenge existing theories and computational models of implicit learning.
Graph Algorithm Animation with Grrr
Rodgers, Peter; Vidal, Natalia
2000-01-01
We discuss geometric positioning, highlighting of visited nodes and user defined highlighting that form the algorithm animation facilities in the Grrr graph rewriting programming language. The main purpose of animation was initially for the debugging and profiling of Grrr code, but recently it has been extended for the purpose of teaching algorithms to undergraduate students. The animation is restricted to graph based algorithms such as graph drawing, list manipulation or more traditional gra...
Optimization Problems on Threshold Graphs
Directory of Open Access Journals (Sweden)
Elena Nechita
2010-06-01
Full Text Available During the last three decades, different types of decompositions have been processed in the field of graph theory. Among these we mention: decompositions based on the additivity of some characteristics of the graph, decompositions where the adjacency law between the subsets of the partition is known, decompositions where the subgraph induced by every subset of the partition must have predeterminate properties, as well as combinations of such decompositions. In this paper we characterize threshold graphs using the weakly decomposition, determine: density and stability number, Wiener index and Wiener polynomial for threshold graphs.
Eulerian Graphs and Related Topics
Fleischner, Herbert
1990-01-01
The two volumes comprising Part 1 of this work embrace the theme of Eulerian trails and covering walks. They should appeal both to researchers and students, as they contain enough material for an undergraduate or graduate graph theory course which emphasizes Eulerian graphs, and thus can be read by any mathematician not yet familiar with graph theory. But they are also of interest to researchers in graph theory because they contain many recent results, some of which are only partial solutions to more general problems. A number of conjectures have been included as well. Various problems (such a
Directory of Open Access Journals (Sweden)
Deptuła Adam
2017-01-01
Full Text Available Analysis and synthesis of mechanisms is one of the fundamental tasks of engineering. Mechanisms can suffer from errors due to versatile reasons. Graph-based methods of analysis and synthesis of planetary gears constitute an alternative method for checking their correctness. Previous applications of the graph theory concerned modelling gears for dynamic analysis, kinematic analysis, synthesis, structural analysis, gearshift optimization and automatic design based on so-called graph grammars. Some tasks may be performed only with the methods resulting from the graph theory, e.g. enumeration of structural solutions. The contour plot method consists in distinguishing a series of consecutive rigid units of the analysed mechanism, forming a closed loop (so-called contour. At a later stage, it is possible to analyze the obtained contour graph as a directed graph of dependence. This work presents an example of the application of game-tree structures in describing the contour graph of a planetary gear. In addition, complex parametric tree structures are included.
Using Webquest in Learning Grammar: Students' Perceptions in Higher Education
Directory of Open Access Journals (Sweden)
Ira Irzawati
2013-01-01
Full Text Available Webquest is an internet based learning tool that can be used by students in learning English. This study investigates students’ perceptions about the use of Webquest to support learning grammar in Higher Education. Seventy-two of second semester students were involved as participants in this study. Questionnaire and interview were used to collect the data. The data were analyzed quantitatively and qualitatively. The result of this study revealed that students had positive perceptions toward the use of Webquest in learning grammar. They believed that Webquest can be used as one of effective internet based learning tools in studying grammar.
The Role of Grammar Instruction in Language Teaching
Institute of Scientific and Technical Information of China (English)
无
2001-01-01
@@ The role of grammar instruction in foreign or second language acquisition is one of the most con troversial issues in foreign/second language teach ing and learning research. The advocators of gram mar instruction argue that grammar should be the core of language instruction and formal instruction enhances formal accuracy. On the other hand, crit ics naintain that the grammar knowledge has lim ited uses and may hinder the students from acquir ing the communicative competence and efficiency. Undoubtedly these two extreme theories often put teachers into a dilemma. What theory should they believe then? Do they accept the one and ignore the other?
Energy Technology Data Exchange (ETDEWEB)
Maunz, Peter Lukas Wilhelm [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Sterk, Jonathan David [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Lobser, Daniel [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Parekh, Ojas D. [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States); Ryan-Anderson, Ciaran [Sandia National Lab. (SNL-NM), Albuquerque, NM (United States)
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%.
Asymptote Misconception on Graphing Functions: Does Graphing Software Resolve It?
Directory of Open Access Journals (Sweden)
Mehmet Fatih Öçal
2017-01-01
Full Text Available Graphing function is an important issue in mathematics education due to its use in various areas of mathematics and its potential roles for students to enhance learning mathematics. The use of some graphing software assists students’ learning during graphing functions. However, the display of graphs of functions that students sketched by hand may be relatively different when compared to the correct forms sketched using graphing software. The possible misleading effects of this situation brought a discussion of a misconception (asymptote misconception on graphing functions. The purpose of this study is two- fold. First of all, this study investigated whether using graphing software (GeoGebra in this case helps students to determine and resolve this misconception in calculus classrooms. Second, the reasons for this misconception are sought. The multiple case study was utilized in this study. University students in two calculus classrooms who received instructions with (35 students or without GeoGebra assisted instructions (32 students were compared according to whether they fell into this misconception on graphing basic functions (1/x, lnx, ex. In addition, students were interviewed to reveal the reasons behind this misconception. Data were analyzed by means of descriptive and content analysis methods. The findings indicated that those who received GeoGebra assisted instruction were better in resolving it. In addition, the reasons behind this misconception were found to be teacher-based, exam-based and some other factors.
ON BIPOLAR SINGLE VALUED NEUTROSOPHIC GRAPHS
Said Broumi; Mohamed Talea; Assia Bakali; Florentin Smarandache
2016-01-01
In this article, we combine the concept of bipolar neutrosophic set and graph theory. We introduce the notions of bipolar single valued neutrosophic graphs, strong bipolar single valued neutrosophic graphs, complete bipolar single valued neutrosophic graphs, regular bipolar single valued neutrosophic graphs and investigate some of their related properties.
Graph Theory. 2. Vertex Descriptors and Graph Coloring
Directory of Open Access Journals (Sweden)
Lorentz JÄNTSCHI
2002-12-01
Full Text Available This original work presents the construction of a set of ten sequence matrices and their applications for ordering vertices in graphs. For every sequence matrix three ordering criteria are applied: lexicographic ordering, based on strings of numbers, corresponding to every vertex, extracted as rows from sequence matrices; ordering by the sum of path lengths from a given vertex; and ordering by the sum of paths, starting from a given vertex. We also examine a graph that has different orderings for the above criteria. We then proceed to demonstrate that every criterion induced its own partition of graph vertex. We propose the following theoretical result: both LAVS and LVDS criteria generate identical partitioning of vertices in any graph. Finally, a coloring of graph vertices according to introduced ordering criteria was proposed.
On an edge partition and root graphs of some classes of line graphs
Directory of Open Access Journals (Sweden)
K Pravas
2017-04-01
Full Text Available The Gallai and the anti-Gallai graphs of a graph $G$ are complementary pairs of spanning subgraphs of the line graph of $G$. In this paper we find some structural relations between these graph classes by finding a partition of the edge set of the line graph of a graph $G$ into the edge sets of the Gallai and anti-Gallai graphs of $G$. Based on this, an optimal algorithm to find the root graph of a line graph is obtained. Moreover, root graphs of diameter-maximal, distance-hereditary, Ptolemaic and chordal graphs are also discussed.
Occupation times distribution for Brownian motion on graphs
Desbois, J
2002-01-01
Considering a Brownian motion on a general graph, we study the joint law for the occupation times on all the bonds. In particular, we show that the Laplace transform of this distribution can be expressed as the ratio of two determinants. We give two formulations, with arc or vertex matrices, for this result and discuss a simple example. (letter to the editor)
Reconfiguring Independent Sets in Claw-Free Graphs
Bonsma, P.S.; Kamiński, Marcin; Wrochna, Marcin; Ravi, R.; Gørtz, Inge Li
We present a polynomial-time algorithm that, given two independent sets in a claw-free graph G, decides whether one can be transformed into the other by a sequence of elementary steps. Each elementary step is to remove a vertex v from the current independent set S and to add a new vertex w (not in
The planar cubic Cayley graphs
Georgakopoulos, Agelos
2018-01-01
The author obtains a complete description of the planar cubic Cayley graphs, providing an explicit presentation and embedding for each of them. This turns out to be a rich class, comprising several infinite families. He obtains counterexamples to conjectures of Mohar, Bonnington and Watkins. The author's analysis makes the involved graphs accessible to computation, corroborating a conjecture of Droms.
Groupies in random bipartite graphs
Yilun Shang
2010-01-01
A vertex $v$ of a graph $G$ is called a groupie if its degree is notless than the average of the degrees of its neighbors. In thispaper we study the influence of bipartition $(B_1,B_2)$ on groupiesin random bipartite graphs $G(B_1,B_2,p)$ with both fixed $p$ and$p$ tending to zero.
Nested Dynamic Condition Response Graphs
DEFF Research Database (Denmark)
Hildebrandt, Thomas; Mukkamala, Raghava Rao; Slaats, Tijs
2012-01-01
We present an extension of the recently introduced declarative process model Dynamic Condition Response Graphs ( DCR Graphs) to allow nested subgraphs and a new milestone relation between events. The extension was developed during a case study carried out jointly with our industrial partner...
Bell inequalities for graph states
International Nuclear Information System (INIS)
Toth, G.; Hyllus, P.; Briegel, H.J.; Guehne, O.
2005-01-01
Full text: In the last years graph states have attracted an increasing interest in the field of quantum information theory. Graph states form a family of multi-qubit states which comprises many popular states such as the GHZ states and the cluster states. They also play an important role in applications. For instance, measurement based quantum computation uses graph states as resources. From a theoretical point of view, it is remarkable that graph states allow for a simple description in terms of stabilizing operators. In this contribution, we investigate the non-local properties of graph states. We derive a family of Bell inequalities which require three measurement settings for each party and are maximally violated by graph states. In turn, any graph state violates at least one of the inequalities. We show that for certain types of graph states the violation of these inequalities increases exponentially with the number of qubits. We also discuss connections to other entanglement properties such as the positively of the partial transpose or the geometric measure of entanglement. (author)
Graph Sampling for Covariance Estimation
Chepuri, Sundeep Prabhakar; Leus, Geert
2017-01-01
specialize for undirected circulant graphs in that the graph nodes leading to the best compression rates are given by the so-called minimal sparse rulers. A near-optimal greedy algorithm is developed to design the subsampling scheme for the non
Network reconstruction via graph blending
Estrada, Rolando
2016-05-01
Graphs estimated from empirical data are often noisy and incomplete due to the difficulty of faithfully observing all the components (nodes and edges) of the true graph. This problem is particularly acute for large networks where the number of components may far exceed available surveillance capabilities. Errors in the observed graph can render subsequent analyses invalid, so it is vital to develop robust methods that can minimize these observational errors. Errors in the observed graph may include missing and spurious components, as well fused (multiple nodes are merged into one) and split (a single node is misinterpreted as many) nodes. Traditional graph reconstruction methods are only able to identify missing or spurious components (primarily edges, and to a lesser degree nodes), so we developed a novel graph blending framework that allows us to cast the full estimation problem as a simple edge addition/deletion problem. Armed with this framework, we systematically investigate the viability of various topological graph features, such as the degree distribution or the clustering coefficients, and existing graph reconstruction methods for tackling the full estimation problem. Our experimental results suggest that incorporating any topological feature as a source of information actually hinders reconstruction accuracy. We provide a theoretical analysis of this phenomenon and suggest several avenues for improving this estimation problem.
A cluster algorithm for graphs
S. van Dongen
2000-01-01
textabstractA cluster algorithm for graphs called the emph{Markov Cluster algorithm (MCL~algorithm) is introduced. The algorithm provides basically an interface to an algebraic process defined on stochastic matrices, called the MCL~process. The graphs may be both weighted (with nonnegative weight)
Stream Processing Using Grammars and Regular Expressions
DEFF Research Database (Denmark)
Rasmussen, Ulrik Terp
disambiguation. The first algorithm operates in two passes in a semi-streaming fashion, using a constant amount of working memory and an auxiliary tape storage which is written in the first pass and consumed by the second. The second algorithm is a single-pass and optimally streaming algorithm which outputs...... as much of the parse tree as is semantically possible based on the input prefix read so far, and resorts to buffering as many symbols as is required to resolve the next choice. Optimality is obtained by performing a PSPACE-complete pre-analysis on the regular expression. In the second part we present...... Kleenex, a language for expressing high-performance streaming string processing programs as regular grammars with embedded semantic actions, and its compilation to streaming string transducers with worst-case linear-time performance. Its underlying theory is based on transducer decomposition into oracle...
A cognitively plausible model for grammar induction
Directory of Open Access Journals (Sweden)
Roni Katzir
2015-01-01
Full Text Available This paper aims to bring theoretical linguistics and cognition-general theories of learning into closer contact. I argue that linguists' notions of rich UGs are well-founded, but that cognition-general learning approaches are viable as well and that the two can and should co-exist and support each other. Specifically, I use the observation that any theory of UG provides a learning criterion -- the total memory space used to store a grammar and its encoding of the input -- that supports learning according to the principle of Minimum Description-Length. This mapping from UGs to learners maintains a minimal ontological commitment: the learner for a particular UG uses only what is already required to account for linguistic competence in adults. I suggest that such learners should be our null hypothesis regarding the child's learning mechanism, and that furthermore, the mapping from theories of UG to learners provides a framework for comparing theories of UG.
A grammar checker based on web searching
Directory of Open Access Journals (Sweden)
Joaquim Moré
2006-05-01
Full Text Available This paper presents an English grammar and style checker for non-native English speakers. The main characteristic of this checker is the use of an Internet search engine. As the number of web pages written in English is immense, the system hypothesises that a piece of text not found on the Web is probably badly written. The system also hypothesises that the Web will provide examples of how the content of the text segment can be expressed in a grammatically correct and idiomatic way. Thus, when the checker warns the user about the odd nature of a text segment, the Internet engine searches for contexts that can help the user decide whether he/she should correct the segment or not. By means of a search engine, the checker also suggests use of other expressions that appear on the Web more often than the expression he/she actually wrote.
An entropy model for artificial grammar learning
Directory of Open Access Journals (Sweden)
Emmanuel Pothos
2010-06-01
Full Text Available A model is proposed to characterize the type of knowledge acquired in Artificial Grammar Learning (AGL. In particular, Shannon entropy is employed to compute the complexity of different test items in an AGL task, relative to the training items. According to this model, the more predictable a test item is from the training items, the more likely it is that this item should be selected as compatible with the training items. The predictions of the entropy model are explored in relation to the results from several previous AGL datasets and compared to other AGL measures. This particular approach in AGL resonates well with similar models in categorization and reasoning which also postulate that cognitive processing is geared towards the reduction of entropy.
An Introduction of Three-dimensional Grammar
Directory of Open Access Journals (Sweden)
Fan Xiao
2017-12-01
Full Text Available This paper introduces some key points of Three-dimensional Grammar. As for the structure, it can be distinguished into syntactic structure, semantic structure and pragmatic structure from the perspectives of syntax, semantics and pragmatics. And the same is true with the followings, such as grammatical constituents, grammatical functions, grammatical meanings, grammatical focuses. Sentence types which is called sentence pattern, sentence model and sentence types respectively, and analysis methods. This paper proposes that grammatical researches should be done in accordance with the four principles, that is form and meaning co-verified, static and dynamic co-referenced, structure and function co-testified and description and interpretation co-promoted.
Dissertation Notice: A Grammar of Wutun
Directory of Open Access Journals (Sweden)
Reviewed by Benjamin Brosig
2018-05-01
Full Text Available Erika Sandman. 2016. A Grammar of Wutun. Helsinki: University of Helsinki. Doctoral dissertation, xii, 370 p. [http://bit.ly/2C0jMCY, accessed 13 December 2017]. An occasional problem when doing research on the languages of northern China is that while there are medium-sized structuralist, historical, and contemporary grammars for many local non-Sinitic varieties (e.g., Todaeva 1966, Chen and Cinggeltei 1986, and Fried 2010 for Bonan, the same does not seem to be equally true for their Sinitic contact varieties. A Grammar of Wutun, a dissertation written by Erika Sandman at the two departments of World Culture and Modern Languages at the University of Helsinki, helps close this gap for what has since Chen (1981 been known as one of the most idiosyncratic varieties of North-Western Mandarin. This language formed as part of the Amdo Sprachbund in intensive contact with Amdo Tibetan and, to some extent, Qinghai Bonan. A Grammar of Wutun is based on Basic Linguistic Theory (Dixon 1997, 2010 and tends to make use of well-established classics for individual linguistic domains (e.g., Lamprecht 1994 for information structure, Yap et al. 2011 for nominalization. Based on a corpus of approximately 1,300 naturally attested and 1,100 elicited clauses mostly collected by the author herself, it first describes the sociolinguistic and research context (1-18, the phonology (19-41, following Janhunen et al. 2008 and word classes (42-175, nouns, verbs, minor of Wutun. After attested morphological forms are thus accounted for, it continues by describing functional domains such as aspect (176-205; evidentiality and egophoricity (206-239; clausal word order, valency, and information structure (240-286; clause-type-related morphological mechanisms for interrogating, ordering, and negating (287-310; and clause connection (311-348. The book closes with glossed and translated transcriptions of three short procedural monologues (349-361. In the nominal domain, Wutun
DIFFICULTIES IN TEACHING AND LEARNING GRAMMAR IN AN EFL CONTEXT
Directory of Open Access Journals (Sweden)
Abdu Mohammed Al-Mekhlafi
2011-07-01
Full Text Available 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 reports a study undertaken to investigate the difficulties teachers face in teaching grammar to EFL students as well as those faced by students in learning it, in the teachers' perception. The study aimed to find out whether there are significant differences in teachers' perceptions of difficulties in relation to their gender, qualification, teaching experience, and the level they teach in school, thus providing insights into their own and their students' difficulties. Mean scores and t-test were used to interpret the data. The main findings are reported with implications.
Interactive design of probability density functions for shape grammars
Dang, Minh; Lienhard, Stefan; Ceylan, Duygu; Neubert, Boris; Wonka, Peter; Pauly, Mark
2015-01-01
A shape grammar defines a procedural shape space containing a variety of models of the same class, e.g. buildings, trees, furniture, airplanes, bikes, etc. We present a framework that enables a user to interactively design a probability density
On the interaction of Linguistic Typology and Functional Grammar
DEFF Research Database (Denmark)
Rijkhoff, J.
2002-01-01
of adjectives as a distinct word class. Conversely it will be shown that facts from many different languages have played an important role in the development of a layered model of the noun phrase in Functional Grammar and how currently these facts are used to test hypotheses concerning parallels between NPs...... empirical research in a wide variety of languages as practiced in the context of linguistic typology and one particular theory, Simon Dik's theory of Functional Grammar. In my view, the relationship between Functional Grammar and linguistic typology is an excellent example of the fruitful combination...... of theory driven data collection and data driven hypothesis formation. Furthermore, typological facts do not only serve to confirm the theory of Functional Grammar, but they also serve as a heuristics for an extension of the theory.Research conducted within the wider theoretical framework of Dik...
Information theory and artificial grammar learning: inferring grammaticality from redundancy.
Jamieson, Randall K; Nevzorova, Uliana; Lee, Graham; Mewhort, D J K
2016-03-01
In artificial grammar learning experiments, participants study strings of letters constructed using a grammar and then sort novel grammatical test exemplars from novel ungrammatical ones. The ability to distinguish grammatical from ungrammatical strings is often taken as evidence that the participants have induced the rules of the grammar. We show that judgements of grammaticality are predicted by the local redundancy of the test strings, not by grammaticality itself. The prediction holds in a transfer test in which test strings involve different letters than the training strings. Local redundancy is usually confounded with grammaticality in stimuli widely used in the literature. The confounding explains why the ability to distinguish grammatical from ungrammatical strings has popularized the idea that participants have induced the rules of the grammar, when they have not. We discuss the judgement of grammaticality task in terms of attribute substitution and pattern goodness. When asked to judge grammaticality (an inaccessible attribute), participants answer an easier question about pattern goodness (an accessible attribute).
Teacher beliefs and practices of grammar teaching: focusing on ...
African Journals Online (AJOL)
focused communicative approaches over the years, studies report that most language teachers still follow transmission-based grammar-oriented approaches. It is known that the success of any curriculum innovation is dependent on teachers.
Construction Grammar as a tool for diachronic analysis
Czech Academy of Sciences Publication Activity Database
Fried, Mirjam
2009-01-01
Roč. 1, č. 2 (2009), s. 262-291 ISSN 1876-1933 Institutional research plan: CEZ:AV0Z90610518 Keywords : grammatical change * gradualness of change * internal reconstruction * Construction Grammar Subject RIV: AI - Linguistics
XPath Node Selection over Grammar-Compressed Trees
Directory of Open Access Journals (Sweden)
Sebastian Maneth
2013-11-01
Full Text Available XML document markup is highly repetitive and therefore well compressible using grammar-based compression. Downward, navigational XPath can be executed over grammar-compressed trees in PTIME: the query is translated into an automaton which is executed in one pass over the grammar. This result is well-known and has been mentioned before. Here we present precise bounds on the time complexity of this problem, in terms of big-O notation. For a given grammar and XPath query, we consider three different tasks: (1 to count the number of nodes selected by the query, (2 to materialize the pre-order numbers of the selected nodes, and (3 to serialize the subtrees at the selected nodes.
Planar graphs theory and algorithms
Nishizeki, T
1988-01-01
Collected in this volume are most of the important theorems and algorithms currently known for planar graphs, together with constructive proofs for the theorems. Many of the algorithms are written in Pidgin PASCAL, and are the best-known ones; the complexities are linear or 0(nlogn). The first two chapters provide the foundations of graph theoretic notions and algorithmic techniques. The remaining chapters discuss the topics of planarity testing, embedding, drawing, vertex- or edge-coloring, maximum independence set, subgraph listing, planar separator theorem, Hamiltonian cycles, and single- or multicommodity flows. Suitable for a course on algorithms, graph theory, or planar graphs, the volume will also be useful for computer scientists and graph theorists at the research level. An extensive reference section is included.
Quantum chaos on discrete graphs
International Nuclear Information System (INIS)
Smilansky, Uzy
2007-01-01
Adapting a method developed for the study of quantum chaos on quantum (metric) graphs (Kottos and Smilansky 1997 Phys. Rev. Lett. 79 4794, Kottos and Smilansky 1999 Ann. Phys., NY 274 76), spectral ζ functions and trace formulae for discrete Laplacians on graphs are derived. This is achieved by expressing the spectral secular equation in terms of the periodic orbits of the graph and obtaining functions which belong to the class of ζ functions proposed originally by Ihara (1966 J. Mat. Soc. Japan 18 219) and expanded by subsequent authors (Stark and Terras 1996 Adv. Math. 121 124, Kotani and Sunada 2000 J. Math. Sci. Univ. Tokyo 7 7). Finally, a model of 'classical dynamics' on the discrete graph is proposed. It is analogous to the corresponding classical dynamics derived for quantum graphs (Kottos and Smilansky 1997 Phys. Rev. Lett. 79 4794, Kottos and Smilansky 1999 Ann. Phys., NY 274 76). (fast track communication)
RJSplot: Interactive Graphs with R.
Barrios, David; Prieto, Carlos
2018-03-01
Data visualization techniques provide new methods for the generation of interactive graphs. These graphs allow a better exploration and interpretation of data but their creation requires advanced knowledge of graphical libraries. Recent packages have enabled the integration of interactive graphs in R. However, R provides limited graphical packages that allow the generation of interactive graphs for computational biology applications. The present project has joined the analytical power of R with the interactive graphical features of JavaScript in a new R package (RJSplot). It enables the easy generation of interactive graphs in R, provides new visualization capabilities, and contributes to the advance of computational biology analytical methods. At present, 16 interactive graphics are available in RJSplot, such as the genome viewer, Manhattan plots, 3D plots, heatmaps, dendrograms, networks, and so on. The RJSplot package is freely available online at http://rjsplot.net. © 2018 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim.
Overlapping community detection based on link graph using distance dynamics
Chen, Lei; Zhang, Jing; Cai, Li-Jun
2018-01-01
The distance dynamics model was recently proposed to detect the disjoint community of a complex network. To identify the overlapping structure of a network using the distance dynamics model, an overlapping community detection algorithm, called L-Attractor, is proposed in this paper. The process of L-Attractor mainly consists of three phases. In the first phase, L-Attractor transforms the original graph to a link graph (a new edge graph) to assure that one node has multiple distances. In the second phase, using the improved distance dynamics model, a dynamic interaction process is introduced to simulate the distance dynamics (shrink or stretch). Through the dynamic interaction process, all distances converge, and the disjoint community structure of the link graph naturally manifests itself. In the third phase, a recovery method is designed to convert the disjoint community structure of the link graph to the overlapping community structure of the original graph. Extensive experiments are conducted on the LFR benchmark networks as well as real-world networks. Based on the results, our algorithm demonstrates higher accuracy and quality than other state-of-the-art algorithms.
Addressing grammar in the interaction task-based learning environment
Directory of Open Access Journals (Sweden)
Davis Brent M.
2017-01-01
Full Text Available One of the major problems in language teaching is developing grammatical accuracy. This paper proposes that using error correction based on a functional grammar in a task-based learning approach may be a suitable solution. Towards this end an emic (using categories intrinsic to the language functional grammar of the verb phrase is proposed and a description of how this fits into the focus on form component of task-based learning is provided.
Bits of Experience in the Oral Practice of Teaching Grammar
Institute of Scientific and Technical Information of China (English)
王敏
2002-01-01
English learners may have such experience that most of them can't be able to speak English apropriately and fluently even if they have gained a lot of grammar knowledge. The approach of teaching grammar discussed in this paper focuses on training students' communicative ability. And it is benefical to stimulating the activeness and interest of students and fostering the ability to solve the problems independently.
A Theoretical Glimpse at Issues of Grammar Teaching
Institute of Scientific and Technical Information of China (English)
朱海涛
2012-01-01
When it comes to the description of the status of grammar in the field of second language teaching now,recent literature bears witness a good deal of discussion about a ’grammar revival’. More recently,theoretical perspectives on language teaching and learning have changed. The possibilities and feasibility of integrating form - focus instruction and meaningful communicative activities in the communicative language classroom have been explored.
THE USE OF THE GRAMMAR-TRANSLATION METHOD IN CHINA
Institute of Scientific and Technical Information of China (English)
1994-01-01
Introduction Among the plethora of foreign language teaching methods and approaches there are the grammar-translation method, the direct method, the audiolingual method and the communicative approach to name but a few. Of the major methods, grammar-translation gets the most criticism and is thought to be obsolete. However, in my view it is suitable for China given the country’s present language learning situation, and, in practice, is not at all ineffectual.
Compiling a corpus-based dictionary grammar: an example for ...
African Journals Online (AJOL)
In this article it is shown how a corpus-based dictionary grammar may be compiled — that is, a mini-grammar fully based on corpus data and specifically written for use in and inte-grated with a dictionary. Such an effort is, to the best of our knowledge, a world's first. We exem-plify our approach for a Northern Sotho ...
Normal ordering problem and the extensions of the Stirling grammar
Ma, S.-M.; Mansour, T.; Schork, M.
2014-04-01
The purpose of this paper is to investigate the connection between context-free grammars and normal ordered problem, and then to explore various extensions of the Stirling grammar. We present grammatical characterizations of several well known combinatorial sequences, including the generalized Stirling numbers of the second kind related to the normal ordered problem and the r-Dowling polynomials. Also, possible avenues for future research are described.
Grammar Learning Strategies and Language Attainment: Seeking a Relationship
Pawlak Mirosław
2009-01-01
Despite major advances in research on language learning strategies, there are still areas that have received only scant attention, and one of them is undoubtedly learning grammar. The paper contributes to the paucity of empirical investigations in this domain by presenting the findings of a study which sought to investigate the relationship between the use of grammar learning strategies (GLS) reported by 142 English Department students and target language attainment, operationalized as their ...
Multiple Grammars and the Logic of Learnability in L2
Directory of Open Access Journals (Sweden)
Tom W Roeper
2016-02-01
Full Text Available The goal of this article is to enhance the technical description of multi-lingual speakers in terms of a theoryof Multiple Grammars where more than one language utilizes a grammar. The challenge of V2 and itsimplications for interfaces from the perspective of the L2 learner is the focus. A number of constructionsare considered including: Quotation, Topicaliation, Empty subjects and Objects, Expletives, and Subject-auxiliary inversoni.
USING PREZI PRESENTATION AS INSTRUCTIONAL MATERIAL IN ENGLISH GRAMMAR CLASSROOM
Directory of Open Access Journals (Sweden)
Rahmat Yusny
2016-05-01
Full Text Available Utilizing digital technology as a medium for educational instruction has now become one of the 21 century pedagogy trends. Numerous researches suggested that using digital technology provides positive impacts as it gives more access to resources for the learning. In Foreign language pedagogy, using digital technology fosters learners’ autonomy by self-managing the amount of learning inputs outside the classroom. However, many studies emphasize more on the communicative and the vast resources accessible for the learners. Very limited attention given to the impact of the visual aid that focuses on aesthetic values of instructional design. English Grammar is one of many subjects that often received complaints by learners and claimed as a “boring” subject. Many English teachers especially in developing countries still utilize traditional method in teaching grammar. They introduce sentence structure using grammar formulas. Although, this method is still very popular, it often considered monotonous by many learners. This paper discusses about the study of using Prezi.com presentation to deliver grammar instruction materials in an English language classroom. From the study, it was found that the majority of the students involved in the study are fond of the materials and the post-test results showed grammar mastery improvement after receiving a grammar lesson that shows instructional materials using prezi. On the other hand, the control class that uses only writing boards and worksheets showed less improvement. This research provides new technique in developing grammar instruction design using a web tool called Prezi in enhancing the display of the instruction material. The experiment was given to students of English Language Education. The result of the study shows students’ positive perception toward the use of Prezi in English grammar instructional material.
On characterizing terrain visibility graphs
Directory of Open Access Journals (Sweden)
William Evans
2015-06-01
Full Text Available A terrain is an $x$-monotone polygonal line in the $xy$-plane. Two vertices of a terrain are mutually visible if and only if there is no terrain vertex on or above the open line segment connecting them. A graph whose vertices represent terrain vertices and whose edges represent mutually visible pairs of terrain vertices is called a terrain visibility graph. We would like to find properties that are both necessary and sufficient for a graph to be a terrain visibility graph; that is, we would like to characterize terrain visibility graphs.Abello et al. [Discrete and Computational Geometry, 14(3:331--358, 1995] showed that all terrain visibility graphs are “persistent”. They showed that the visibility information of a terrain point set implies some ordering requirements on the slopes of the lines connecting pairs of points in any realization, and as a step towards showing sufficiency, they proved that for any persistent graph $M$ there is a total order on the slopes of the (pseudo lines in a generalized configuration of points whose visibility graph is $M$.We give a much simpler proof of this result by establishing an orientation to every triple of vertices, reflecting some slope ordering requirements that are consistent with $M$ being the visibility graph, and prove that these requirements form a partial order. We give a faster algorithm to construct a total order on the slopes. Our approach attempts to clarify the implications of the graph theoretic properties on the ordering of the slopes, and may be interpreted as defining properties on an underlying oriented matroid that we show is a restricted type of $3$-signotope.
Graph embedding with rich information through heterogeneous graph
Sun, Guolei
2017-11-12
Graph embedding, aiming to learn low-dimensional representations for nodes in graphs, has attracted increasing attention due to its critical application including node classification, link prediction and clustering in social network analysis. Most existing algorithms for graph embedding only rely on the topology information and fail to use the copious information in nodes as well as edges. As a result, their performance for many tasks may not be satisfactory. In this thesis, we proposed a novel and general framework for graph embedding with rich text information (GERI) through constructing a heterogeneous network, in which we integrate node and edge content information with graph topology. Specially, we designed a novel biased random walk to explore the constructed heterogeneous network with the notion of flexible neighborhood. Our sampling strategy can compromise between BFS and DFS local search on heterogeneous graph. To further improve our algorithm, we proposed semi-supervised GERI (SGERI), which learns graph embedding in an discriminative manner through heterogeneous network with label information. The efficacy of our method is demonstrated by extensive comparison experiments with 9 baselines over multi-label and multi-class classification on various datasets including Citeseer, Cora, DBLP and Wiki. It shows that GERI improves the Micro-F1 and Macro-F1 of node classification up to 10%, and SGERI improves GERI by 5% in Wiki.
Business Rules Definition for Decision Support System Using Matrix Grammar
Directory of Open Access Journals (Sweden)
Eva Zámečníková
2016-06-01
Full Text Available This paper deals with formalization of business rules by formal grammars. In our work we focus on methods for high frequency data processing. We process data by using complex event platforms (CEP which allow to process high volume of data in nearly real time. Decision making process is contained by one level of processing of CEP. Business rules are used for decision making process description. For the business rules formalization we chose matrix grammar. The use of formal grammars is quite natural as the structure of rules and its rewriting is very similar both for the business rules and for formal grammar. In addition the matrix grammar allows to simulate dependencies and correlations between the rules. The result of this work is a model for data processing of knowledge-based decision support system described by the rules of formal grammar. This system will support the decision making in CEP. This solution may contribute to the speedup of decision making process in complex event processing and also to the formal verification of these systems.
CORECLUSTER: A Degeneracy Based Graph Clustering Framework
Giatsidis , Christos; Malliaros , Fragkiskos; Thilikos , Dimitrios M. ,; Vazirgiannis , Michalis
2014-01-01
International audience; Graph clustering or community detection constitutes an important task forinvestigating the internal structure of graphs, with a plethora of applications in several domains. Traditional tools for graph clustering, such asspectral methods, typically suffer from high time and space complexity. In thisarticle, we present \\textsc{CoreCluster}, an efficient graph clusteringframework based on the concept of graph degeneracy, that can be used along withany known graph clusteri...
The contribution of phonological short-term memory to artificial grammar learning.
Andrade, Jackie; Baddeley, Alan
2011-05-01
Three experiments investigated the contribution of phonological short-term memory (STM) to grammar learning by manipulating rehearsal during study of an auditory artificial grammar made up from a vocabulary of spoken Mandarin syllables. Experiment 1 showed that concurrent, irrelevant articulation impaired grammar learning compared with a nonverbal control task. Experiment 2 replicated and extended this finding, showing that repeating the grammatical strings at study improved grammar learning compared with suppressing rehearsal or remaining silent during learning. Experiment 3 found no effects of rehearsal on grammar learning once participants had learned the component syllables. The findings suggest that phonological STM aids artificial grammar learning via effects on vocabulary learning.
Hierarchy of modular graph identities
International Nuclear Information System (INIS)
D’Hoker, Eric; Kaidi, Justin
2016-01-01
The low energy expansion of Type II superstring amplitudes at genus one is organized in terms of modular graph functions associated with Feynman graphs of a conformal scalar field on the torus. In earlier work, surprising identities between two-loop graphs at all weights, and between higher-loop graphs of weights four and five were constructed. In the present paper, these results are generalized in two complementary directions. First, all identities at weight six and all dihedral identities at weight seven are obtained and proven. Whenever the Laurent polynomial at the cusp is available, the form of these identities confirms the pattern by which the vanishing of the Laurent polynomial governs the full modular identity. Second, the family of modular graph functions is extended to include all graphs with derivative couplings and worldsheet fermions. These extended families of modular graph functions are shown to obey a hierarchy of inhomogeneous Laplace eigenvalue equations. The eigenvalues are calculated analytically for the simplest infinite sub-families and obtained by Maple for successively more complicated sub-families. The spectrum is shown to consist solely of eigenvalues s(s−1) for positive integers s bounded by the weight, with multiplicities which exhibit rich representation-theoretic patterns.
Semantic graphs and associative memories
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.
Hierarchy of modular graph identities
Energy Technology Data Exchange (ETDEWEB)
D’Hoker, Eric; Kaidi, Justin [Mani L. Bhaumik Institute for Theoretical Physics, Department of Physics and Astronomy,University of California,Los Angeles, CA 90095 (United States)
2016-11-09
The low energy expansion of Type II superstring amplitudes at genus one is organized in terms of modular graph functions associated with Feynman graphs of a conformal scalar field on the torus. In earlier work, surprising identities between two-loop graphs at all weights, and between higher-loop graphs of weights four and five were constructed. In the present paper, these results are generalized in two complementary directions. First, all identities at weight six and all dihedral identities at weight seven are obtained and proven. Whenever the Laurent polynomial at the cusp is available, the form of these identities confirms the pattern by which the vanishing of the Laurent polynomial governs the full modular identity. Second, the family of modular graph functions is extended to include all graphs with derivative couplings and worldsheet fermions. These extended families of modular graph functions are shown to obey a hierarchy of inhomogeneous Laplace eigenvalue equations. The eigenvalues are calculated analytically for the simplest infinite sub-families and obtained by Maple for successively more complicated sub-families. The spectrum is shown to consist solely of eigenvalues s(s−1) for positive integers s bounded by the weight, with multiplicities which exhibit rich representation-theoretic patterns.
Image based Monument Recognition using Graph based Visual Saliency
DEFF Research Database (Denmark)
Kalliatakis, Grigorios; Triantafyllidis, Georgios
2013-01-01
This article presents an image-based application aiming at simple image classification of well-known monuments in the area of Heraklion, Crete, Greece. This classification takes place by utilizing Graph Based Visual Saliency (GBVS) and employing Scale Invariant Feature Transform (SIFT) or Speeded......, the images have been previously processed according to the Graph Based Visual Saliency model in order to keep either SIFT or SURF features corresponding to the actual monuments while the background “noise” is minimized. The application is then able to classify these images, helping the user to better...
EIT Imaging Regularization Based on Spectral Graph Wavelets.
Gong, Bo; Schullcke, Benjamin; Krueger-Ziolek, Sabine; Vauhkonen, Marko; Wolf, Gerhard; Mueller-Lisse, Ullrich; Moeller, Knut
2017-09-01
The objective of electrical impedance tomographic reconstruction is to identify the distribution of tissue conductivity from electrical boundary conditions. This is an ill-posed inverse problem usually solved under the finite-element method framework. In previous studies, standard sparse regularization was used for difference electrical impedance tomography to achieve a sparse solution. However, regarding elementwise sparsity, standard sparse regularization interferes with the smoothness of conductivity distribution between neighboring elements and is sensitive to noise. As an effect, the reconstructed images are spiky and depict a lack of smoothness. Such unexpected artifacts are not realistic and may lead to misinterpretation in clinical applications. To eliminate such artifacts, we present a novel sparse regularization method that uses spectral graph wavelet transforms. Single-scale or multiscale graph wavelet transforms are employed to introduce local smoothness on different scales into the reconstructed images. The proposed approach relies on viewing finite-element meshes as undirected graphs and applying wavelet transforms derived from spectral graph theory. Reconstruction results from simulations, a phantom experiment, and patient data suggest that our algorithm is more robust to noise and produces more reliable images.
XML Graphs in Program Analysis
DEFF Research Database (Denmark)
Møller, Anders; Schwartzbach, Michael I.
2011-01-01
of XML graphs against different XML schema languages, and provide a software package that enables others to make use of these ideas. We also survey the use of XML graphs for program analysis with four very different languages: XACT (XML in Java), Java Servlets (Web application programming), XSugar......XML graphs have shown to be a simple and effective formalism for representing sets of XML documents in program analysis. It has evolved through a six year period with variants tailored for a range of applications. We present a unified definition, outline the key properties including validation...
Rabern, Landon
2007-01-01
We improve upper bounds on the chromatic number proven independently in \\cite{reedNote} and \\cite{ingo}. Our main lemma gives a sufficient condition for two paths in graph to be completely joined. Using this, we prove that if a graph has an optimal coloring with more than $\\frac{\\omega}{2}$ singleton color classes, then it satisfies $\\chi \\leq \\frac{\\omega + \\Delta + 1}{2}$. It follows that a graph satisfying $n - \\Delta < \\alpha + \\frac{\\omega - 1}{2}$ must also satisfy $\\chi \\leq \\frac{\\ome...
Graphs with Eulerian unit spheres
Knill, Oliver
2015-01-01
d-spheres in graph theory are inductively defined as graphs for which all unit spheres S(x) are (d-1)-spheres and that the removal of one vertex renders the graph contractible. Eulerian d-spheres are geometric d-spheres which are d+1 colorable. We prove here that G is an Eulerian sphere if and only if the degrees of all the (d-2)-dimensional sub-simplices in G are even. This generalizes a Kempe-Heawood result for d=2 and is work related to the conjecture that all d-spheres have chromatic numb...
Szabó, György; Fáth, Gábor
2007-07-01
Game theory is one of the key paradigms behind many scientific disciplines from biology to behavioral sciences to economics. In its evolutionary form and especially when the interacting agents are linked in a specific social network the underlying solution concepts and methods are very similar to those applied in non-equilibrium statistical physics. This review gives a tutorial-type overview of the field for physicists. The first four sections introduce the necessary background in classical and evolutionary game theory from the basic definitions to the most important results. The fifth section surveys the topological complications implied by non-mean-field-type social network structures in general. The next three sections discuss in detail the dynamic behavior of three prominent classes of models: the Prisoner's Dilemma, the Rock-Scissors-Paper game, and Competing Associations. The major theme of the review is in what sense and how the graph structure of interactions can modify and enrich the picture of long term behavioral patterns emerging in evolutionary games.
Properly colored connectivity of graphs
Li, Xueliang; Qin, Zhongmei
2018-01-01
A comprehensive survey of proper connection of graphs is discussed in this book with real world applications in computer science and network security. Beginning with a brief introduction, comprising relevant definitions and preliminary results, this book moves on to consider a variety of properties of graphs that imply bounds on the proper connection number. Detailed proofs of significant advancements toward open problems and conjectures are presented with complete references. Researchers and graduate students with an interest in graph connectivity and colorings will find this book useful as it builds upon fundamental definitions towards modern innovations, strategies, and techniques. The detailed presentation lends to use as an introduction to proper connection of graphs for new and advanced researchers, a solid book for a graduate level topics course, or as a reference for those interested in expanding and further developing research in the area.
Graph anomalies in cyber communications
Energy Technology Data Exchange (ETDEWEB)
Vander Wiel, Scott A [Los Alamos National Laboratory; Storlie, Curtis B [Los Alamos National Laboratory; Sandine, Gary [Los Alamos National Laboratory; Hagberg, Aric A [Los Alamos National Laboratory; Fisk, Michael [Los Alamos National Laboratory
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.
Open Graphs and Computational Reasoning
Directory of Open Access Journals (Sweden)
Lucas Dixon
2010-06-01
Full Text Available We present a form of algebraic reasoning for computational objects which are expressed as graphs. Edges describe the flow of data between primitive operations which are represented by vertices. These graphs have an interface made of half-edges (edges which are drawn with an unconnected end and enjoy rich compositional principles by connecting graphs along these half-edges. In particular, this allows equations and rewrite rules to be specified between graphs. Particular computational models can then be encoded as an axiomatic set of such rules. Further rules can be derived graphically and rewriting can be used to simulate the dynamics of a computational system, e.g. evaluating a program on an input. Examples of models which can be formalised in this way include traditional electronic circuits as well as recent categorical accounts of quantum information.
Woeginger, G.J.
1998-01-01
In this short note we argue that the toughness of split graphs can be computed in polynomial time. This solves an open problem from a recent paper by Kratsch et al. (Discrete Math. 150 (1996) 231–245).
Generating random networks and graphs
Coolen, Ton; Roberts, Ekaterina
2017-01-01
This book supports researchers who need to generate random networks, or who are interested in the theoretical study of random graphs. The coverage includes exponential random graphs (where the targeted probability of each network appearing in the ensemble is specified), growth algorithms (i.e. preferential attachment and the stub-joining configuration model), special constructions (e.g. geometric graphs and Watts Strogatz models) and graphs on structured spaces (e.g. multiplex networks). The presentation aims to be a complete starting point, including details of both theory and implementation, as well as discussions of the main strengths and weaknesses of each approach. It includes extensive references for readers wishing to go further. The material is carefully structured to be accessible to researchers from all disciplines while also containing rigorous mathematical analysis (largely based on the techniques of statistical mechanics) to support those wishing to further develop or implement the theory of rand...
Transfer and access to universal grammar in adult second language acquisition
Sauter, Kim
2002-01-01
Summary This dissertation focuses on the roles of first language transfer and Universal Grammar in adult second (or foreign) language acquisition. It contributes to the ongoing debate whether second language acquisition is constrained by Universal Grammar. According to generative linguists,
The Role of Simple Semantics in the Process of Artificial Grammar Learning.
Öttl, Birgit; Jäger, Gerhard; Kaup, Barbara
2017-10-01
This study investigated the effect of semantic information on artificial grammar learning (AGL). Recursive grammars of different complexity levels (regular language, mirror language, copy language) were investigated in a series of AGL experiments. In the with-semantics condition, participants acquired semantic information prior to the AGL experiment; in the without-semantics control condition, participants did not receive semantic information. It was hypothesized that semantics would generally facilitate grammar acquisition and that the learning benefit in the with-semantics conditions would increase with increasing grammar complexity. Experiment 1 showed learning effects for all grammars but no performance difference between conditions. Experiment 2 replicated the absence of a semantic benefit for all grammars even though semantic information was more prominent during grammar acquisition as compared to Experiment 1. Thus, we did not find evidence for the idea that semantics facilitates grammar acquisition, which seems to support the view of an independent syntactic processing component.
Strategies Study On Communicative Awareness-raising Approachof Grammar Teaching for English Majors
Institute of Scientific and Technical Information of China (English)
吴俊芳; 童心
2013-01-01
The traditional grammar teaching method can’t make learners communicate in real contexts accurately and luently.The author will probe the effects of communicative approach applied in grammar teaching in this essay.
Graph theory and its applications
Gross, Jonathan L
2006-01-01
Gross and Yellen take a comprehensive approach to graph theory that integrates careful exposition of classical developments with emerging methods, models, and practical needs. Their unparalleled treatment provides a text ideal for a two-semester course and a variety of one-semester classes, from an introductory one-semester course to courses slanted toward classical graph theory, operations research, data structures and algorithms, or algebra and topology.
A faithful functor among algebras and graphs
Falcón Ganfornina, Óscar Jesús; Falcón Ganfornina, Raúl Manuel; Núñez Valdés, Juan; Pacheco Martínez, Ana María; Villar Liñán, María Trinidad; Vigo Aguiar, Jesús (Coordinador)
2016-01-01
The problem of identifying a functor between the categories of algebras and graphs is currently open. Based on a known algorithm that identifies isomorphisms of Latin squares with isomorphism of vertex-colored graphs, we describe here a pair of graphs that enable us to find a faithful functor between finite-dimensional algebras over finite fields and these graphs.
Graphs with branchwidth at most three
Bodlaender, H.L.; Thilikos, D.M.
1997-01-01
In this paper we investigate both the structure of graphs with branchwidth at most three, as well as algorithms to recognise such graphs. We show that a graph has branchwidth at most three, if and only if it has treewidth at most three and does not contain the three-dimensional binary cube graph
Graphs whose complement and square are isomorphic
DEFF Research Database (Denmark)
Pedersen, Anders Sune
2014-01-01
We study square-complementary graphs, that is, graphs whose complement and square are isomorphic. We prove several necessary conditions for a graph to be square-complementary, describe ways of building new square-complementary graphs from existing ones, construct infinite families of square-compl...
Acyclicity in edge-colored graphs
DEFF Research Database (Denmark)
Gutin, Gregory; Jones, Mark; Sheng, Bin
2017-01-01
A walk W in edge-colored graphs is called properly colored (PC) if every pair of consecutive edges in W is of different color. We introduce and study five types of PC acyclicity in edge-colored graphs such that graphs of PC acyclicity of type i is a proper superset of graphs of acyclicity of type...
Building Scalable Knowledge Graphs for Earth Science
Ramachandran, Rahul; Maskey, Manil; Gatlin, Patrick; Zhang, Jia; Duan, Xiaoyi; Miller, J. J.; Bugbee, Kaylin; Christopher, Sundar; Freitag, Brian
2017-01-01
Knowledge Graphs link key entities in a specific domain with other entities via relationships. From these relationships, researchers can query knowledge graphs for probabilistic recommendations to infer new knowledge. Scientific papers are an untapped resource which knowledge graphs could leverage to accelerate research discovery. Goal: Develop an end-to-end (semi) automated methodology for constructing Knowledge Graphs for Earth Science.
Port-Hamiltonian Systems on Open Graphs
Schaft, A.J. van der; Maschke, B.M.
2010-01-01
In this talk we discuss how to define in an intrinsic manner port-Hamiltonian dynamics on open graphs. Open graphs are graphs where some of the vertices are boundary vertices (terminals), which allow interconnection with other systems. We show that a directed graph carries two natural Dirac
Constructing Dense Graphs with Unique Hamiltonian Cycles
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…
Skew-adjacency matrices of graphs
Cavers, M.; Cioaba, S.M.; Fallat, S.; Gregory, D.A.; Haemers, W.H.; Kirkland, S.J.; McDonald, J.J.; Tsatsomeros, M.
2012-01-01
The spectra of the skew-adjacency matrices of a graph are considered as a possible way to distinguish adjacency cospectral graphs. This leads to the following topics: graphs whose skew-adjacency matrices are all cospectral; relations between the matchings polynomial of a graph and the characteristic
Chromatic polynomials of random graphs
International Nuclear Information System (INIS)
Van Bussel, Frank; Fliegner, Denny; Timme, Marc; Ehrlich, Christoph; Stolzenberg, Sebastian
2010-01-01
Chromatic polynomials and related graph invariants are central objects in both graph theory and statistical physics. Computational difficulties, however, have so far restricted studies of such polynomials to graphs that were either very small, very sparse or highly structured. Recent algorithmic advances (Timme et al 2009 New J. Phys. 11 023001) now make it possible to compute chromatic polynomials for moderately sized graphs of arbitrary structure and number of edges. Here we present chromatic polynomials of ensembles of random graphs with up to 30 vertices, over the entire range of edge density. We specifically focus on the locations of the zeros of the polynomial in the complex plane. The results indicate that the chromatic zeros of random graphs have a very consistent layout. In particular, the crossing point, the point at which the chromatic zeros with non-zero imaginary part approach the real axis, scales linearly with the average degree over most of the density range. While the scaling laws obtained are purely empirical, if they continue to hold in general there are significant implications: the crossing points of chromatic zeros in the thermodynamic limit separate systems with zero ground state entropy from systems with positive ground state entropy, the latter an exception to the third law of thermodynamics.
Commuting graphs of matrix algebras
International Nuclear Information System (INIS)
Akbari, S.; Bidkhori, H.; Mohammadian, A.
2006-08-01
The commuting graph of a ring R, denoted by Γ(R), is a graph whose vertices are all non- central elements of R and two distinct vertices x and y are adjacent if and only if xy = yx. The commuting graph of a group G, denoted by Γ(G), is similarly defined. In this paper we investigate some graph theoretic properties of Γ(M n (F)), where F is a field and n ≥ 2. Also we study the commuting graphs of some classical groups such as GL n (F) and SL n (F). We show that Γ(M n (F)) is a connected graph if and only if every field extension of F of degree n contains a proper intermediate field. We prove that apart from finitely many fields, a similar result is true for Γ(GL n (F)) and Γ(SL n (F)). Also we show that for two fields E and F and integers m, n ≥> 2, if Γ(M m (E)) ≅ Γ(M n (F)), then m = n and vertical bar E vertical bar = vertical bar F vertical bar. (author)
CLIL in physics lessons at grammar school
Štefančínová, Iveta; Valovičová, Ä½ubomíra
2017-01-01
Content and Language Integrated Learning (CLIL) is one of the most outstanding approaches in foreign language teaching. This teaching method has promising prospects for the future of modern education as teaching subject and foreign languages are combined to offer a better preparation for life in Europe, especially when the mobility is becoming a highly significant factor of everyday life. We realized a project called Foreign languages in popularizing science at grammar school. Within the project five teachers with approbation subjects of English, French, German and Physics attended the methodological courses abroad. The teachers applied the gained experience in teaching and linking science teaching with the teaching of foreign languages. Outputs of the project (e.g. English-German-French-Slovak glossary of natural science terminology, student activity sheets, videos with natural science orientation in a foreign language, physical experiments in foreign languages, multimedia fairy tales with natural contents, posters of some scientists) are prepared for the CLIL-oriented lessons. We collected data of the questionnaire for students concerning attitude towards CLIL. The questionnaire for teachers showed data about the attitude, experience, and needs of teachers employing CLIL in their lessons.
A constraint-based bottom-up counterpart to definite clause grammars
DEFF Research Database (Denmark)
Christiansen, Henning
2004-01-01
A new grammar formalism, CHR Grammars (CHRG), is proposed that provides a constraint-solving approach to language analysis, built on top of the programming language of Constraint Handling Rules in the same way as Definite Clause Grammars (DCG) on Prolog. CHRG works bottom-up and adds the following......, integrity constraints, operators a la assumption grammars, and to incorporate other constraint solvers. (iv)~Context-sensitive rules that apply for disambiguation, coordination in natural language and tagger-like rules....
Graph Quasicontinuous Functions and Densely Continuous Forms
Directory of Open Access Journals (Sweden)
Lubica Hola
2017-07-01
Full Text Available Let $X, Y$ be topological spaces. A function $f: X \\to Y$ is said to be graph quasicontinuous if there is a quasicontinuous function $g: X \\to Y$ with the graph of $g$ contained in the closure of the graph of $f$. There is a close relation between the notions of graph quasicontinuous functions and minimal usco maps as well as the notions of graph quasicontinuous functions and densely continuous forms. Every function with values in a compact Hausdorff space is graph quasicontinuous; more generally every locally compact function is graph quasicontinuous.
The Role of Grammar in the Writing Curriculum: A Review of the Literature
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;…
Functional Orientation and Practice of Inductive and Deductive Approaches to Grammar Teaching in EFL
Institute of Scientific and Technical Information of China (English)
邵阳
2011-01-01
To solve the ambiguous understanding of Grammar Teaching position,based on explicit grammatical knowledge,this paper discusses the grammar position in EFL,compares both its pros and cons between deductive and inductive approaches,and indicates that grammar teaching by either approach alone has disadvantages,should adopt a combination technique.
Impact of Consciousness-Raising Activities on Young English Language Learners' Grammar Performance
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…
Eckstein, Grant
2016-01-01
Although most writing centres maintain policies against providing grammar correction during writing tutorials, it is undeniable that students expect some level of grammar intervention there. Just how much students expect and receive is a matter of speculation. This article examines the grammar-correction issue by reporting on a survey of L1, L2,…
STUDENTS’ ATTITUDES TO EXPLICIT GRAMMAR TEACHING AND ITS RELATIONAHIP TO COMMUNICATION
Institute of Scientific and Technical Information of China (English)
2000-01-01
Grammar teaching is greatly emphasised in English language teaching in China, but does it really attain the goal the students desire? An investigation was made with overseas students about their attitudes to explicit grammar teaching. The investigation reveals that grammar teaching should focus on developing the learners’ communicative ability more than presenting and explaining grammatical rules.
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…