Abstract We present an algorithm for extracting a subclass of the context free grammars (CFGs) from a trained recurrent neural network (RNN). We develop a new framework,pattern rule sets(PRSs), which describe sequences of deterministic finite automata (DFAs) that approximate a non-regular language. We present an algorithm for recovering the PRS behind a sequence of such automata, and apply it to the sequences of automata extracted from trained RNNs using the $$L^{*}$$ L∗ algorithm. We then show how the PRS may converted into a CFG, enabling a familiar and useful presentation of the learned language. Extracting the learned language of an RNN is important to facilitate understanding of the RNN and to verify its correctness. Furthermore, the extracted CFG can augment the RNN in classifying correct sentences, as the RNN’s predictive accuracy decreases when the recursion depth and distance between matching delimiters of its input sequences increases.

IT system architectures and many other kinds of structured artifacts are often described by formal models or informal diagrams. In practice, there are often a number of versions of a model or diagram, such as a series of revisions, divergent variants, or multiple views of a system. Understanding how versions correspond or differ is crucial, and thus, automated assistance for matching models and diagrams is essential. We have designed a framework for finding these correspondences automatically based on Bayesian methods. We represent models and diagrams as graphs whose nodes have attributes such as name, type, connections to other nodes, and containment relations, and we have developed probabilistic models for rating the quality of candidate correspondences based on various features of the nodes in the graphs. Given the probabilistic models, we can find high-quality correspondences using search algorithms. Preliminary experiments focusing on architectural models suggest that the technique is promising.

IT system architectures, as well as other systems, are often described by formal models or informal diagrams. In practice, there are often a number of versions of a model, e.g. for different views of a system, divergent variants, or a series of revisions. Understanding how versions of a model correspond or differ is crucial, yet little work has been done on automated assistance for matching models and diagrams.We have designed a framework based on Bayesian methods for finding these correspondences automatically. We represent models and diagrams as graphs whose nodes have attributes such as name, type, connections, and containment relations, and we have developed probabilistic models for rating the quality of candidate correspondences based on various features of the nodes in the graphs. Given the probabilistic models, we can find high quality correspondences using search algorithms. Preliminary experiments focusing on architectural models suggest that the technique is promising.

We present a novel scheme that combines decision feedback equalization (DFE) with high-rate error-detection coding in an efficient manner. The proposed scheme is shown to considerably outperform the conventional practice on channels with high SNR, such as those encountered in twisted-pair telephony systems. In order to analyze the performance of our method, we introduce an approximate mathematical model taking into account the error propagation phenomenon. Based on this model, upper and lower bounds on the overall probability of error are developed. These show that a simple low-redundancy error-detecting code, when properly integrated with the equalizer, can make the overall probability of error several orders of magnitude lower than that obtained with the conventional DFE, or with a DFE followed by an error-correcting code. Computer simulations of the proposed method have been performed for several channels, including the so-called high-bit-rate digital subscriber line (HDSL) test-loop 4, which is known to have a considerable amount of intersymbol interference. For all these channels, our results show that a reduction in the probability of error by more than three orders of magnitude can be obtained using codes of rate 0.96 and above. This, in turn, translates into power savings (coding gain) of 2.5 to 3 dB.

In this article we examine the augmentation of application interfaces with enhanced specifications that include sequencing constraints called protocols.Protocols make explicit the relationship between messages (methods) supported by the application.These relationships are usually only given implicitly, either in the code or in textual comments.We define notions of interface compatibility based upon protocols and show how compatibility can be checked, discovering a class of errors that cannot be discovered via the type system alone.We then define software adaptors that can be used to bridge the difference between applications that have functionally compatible but type-and protocol-incompatible interfaces.We discuss what it means for an adaptor to be well formed.Leveraging the information provided by protocols, we show how adaptors can be automatically generated from a high-level description, called an interface mapping.

In this paper we show how to augment object-oriented application interfaces with enhanced specifications that include sequencing constraints called protocols. Protocols make explicit the relationship between messages (methods) supported by the application. These relationships are usually only given implicitly, either in the code or in textual comments. We define notions of interface compatibility based upon protocols and show how compatibility can be checked, discovering a class of errors that cannot be discovered via the type system alone. We then define software adaptors that can be used to bridge the difference between object-oriented applications that have functionally compatible but type incompatible interfaces. We discuss what it means for an adaptor to be well-formed. Leveraging the information provided by protocols, we show how adaptors can be automatically generated from a high-level description, called an interface mapping.

The authors present a practical extension to typestate checking, which is capable of proving programs free of uninitialized variable errors even when these programs contain conditionally initialized variables where the initialization of a variable depends upon the equality of one or more tag variables to a constant. The user need not predeclare the relationship between a conditionally initialized variable and its tags, and this relationship may change from one point in the program to another. The technique generalizes liveness analysis to conditional liveness analysis. Like typestate checking, this technique incorporates a dataflow analysis algorithm in which each point in a program is labeled with a lattice point describing statically tracked information, including the initialization of variables. The labeling is then used to check for programming errors such as referencing a variable which may be uninitialized.>

This paper introduces Composable Attribute Grammars (CAGs), a formalism that extends classical attribute grammars to allow for the modular composition of translation specifications and of translators. CAGs bring to complex translator writing systems the same benefits of modularity found in modern programming languages, including comprehensibility, reusability, and incremental meta-compilation.A CAG is built from several smaller component AGs, each of which solves a particular subproblem, such as name analysis or register allocation. A component AG is based upon a simplified phrase-structure that reflects the properties of its subproblem rather than the phrase-structure of the source language. Different component phrase-structures for various subproblems are combined by mapping them into a phrase-structure for the source language. Both input and output attributes can be associated with the terminal symbols of a component AG. Output attributes enable the results of solving a subproblem to be distributed back to anywhere that originally contributed part of the subproblem, e.g. transparently distributing the results of global name analysis back to every symbolic reference in the source program.After introducing CAGs by way of an example, we provide a formal definition of CAGs and their semantics. We describe a subclass of CAGs and their semantics. We describe a subclass of CAGs, called separable CAGs, that have favorable implementation properties. We discuss the novel aspects of CAGs, compare them to other proposals for inserting modularity into attribute grammars, and relate our experience using CAGs in the Linguist translator-writing system.

An incremental computation is one that is performed repeatedly on nearly identical inputs. Incremental computations occur naturally in many environments, such as compilers, language-based editors, spreadsheets, and formatters. This article describes a proposed tool for making it easy to write incremental programs. The tool consists of a programming language, INC, and a set of compile-time transformations for the primitive elements of INC. A programmer defines an algorithm in INC without regard to efficient incremental execution. The transformations automatically convert this algorithm into an efficient incremental algorithm. INC is a functional language. The implementation of an INC program is a network of processes. Each INC function is transformed into a process that receives and transmits messages describing changes to its inputs and outputs. We give an overview to the language and illustrate the incremental techniques employed by INC. We present the static and incremental complexity bounds for the primitive INC functions. We also present some example programs illustrating INC's flexibility.

article INC: a language for incremental computations Share on Authors: D. Yellin IBM T. J. Watson Research Center, Yorktown Heights, NY IBM T. J. Watson Research Center, Yorktown Heights, NYView Profile , R. Strom IBM T. J. Watson Research Center, Yorktown Heights, NY IBM T. J. Watson Research Center, Yorktown Heights, NYView Profile Authors Info & Claims ACM SIGPLAN NoticesVolume 23Issue 7July 1988 pp 115–124https://doi.org/10.1145/960116.54002Online:01 June 1988Publication History 16citation327DownloadsMetricsTotal Citations16Total Downloads327Last 12 Months4Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Attribute grammars constitute a formal mechanism for specifying translations between languages; from a formal description of the translation, a translator can be automatically constructed. This process is taken one step further; given an attribute grammar specifying the translation from languageL1to languageL2, the question of whether the inverse attribute grammar specifying the inverse translation fromL2toL1can be automatically generated is addressed. It is shown how to solve this problem for a restricted subset of attribute grammars. This inversion process allows compatible two-way translators to be generated from a single description. To show the practical feasibility of attribute grammar inversion, experience in inverting an attribute grammar used as an interface for a formal database accessing language, SQL, is related. The attributed grammar is used to paraphrase SQL database queries in English.