Stochastic syntax-directed translations in syntactic pattern processing

Stochastic context-free grammars are used in syntactic pattern processing to model sources of noise, ambiguity in pattern classes, and other random phenomena. Stochastic syntax-directed translation schemata take these concepts one step further by describing both the syntactic structure and the probabilities of grammar-based mappings between context-free languages.     

Some Statistical-Estimation Methods for Stochastic Finite-State Transducers

Formal translations constitute a suitable framework for dealing with many problems in pattern recognition and computational linguistics. The application of formal transducers to these areas requires a stochastic extension for dealing with noisy, distorted patterns with high variability. In this paper, some estimation criteria are proposed and developed for the parameter estimation of regular syntax-directed translation schemata. These criteria are: maximum likelihood estimation, minimum conditional entropy estimation and conditional maximum likelihood estimation. The last two criteria were proposed in order to deal with situations when training data is sparse. These criteria take into account the possibility of ambiguity in the translations: i.e., there can be different output strings for a single input string. In this case, the final goal of the stochastic framework is to find the highest probability translation of a given input string. These criteria were tested on a translation task which has a high degree of ambiguity.     

Defining syntax-directed translations by tree bimorphisms

We introduce a class of tree bimorphisms that define exactly the translations performed by syntax-directed translation schemata. We also show that these “quasi-alphabetic” tree bimorphisms preserve recognizability, and that their class is closed under composition and inverses.     

Grammar-based articulation for multimedia document design

This paper describes an approach to the problem of articulating multimedia information based on parsing and syntax-directed translation that uses Relational Grammars. This translation is followed by a constraint-solving mechanism to create the final layout. Grammatical rules provide the mechanism for mapping from a representation of the content and context of a presentation to forms that specify the media objects to be realized. These realization forms include sets of spatial and temporal constraints between elements of the presentation. Individual grammars encapsulate the “look and feel” of a presentation and can be used as generators of such a style. By making the grammars sensitive to the requirements of the output medium, parsing can introduce flexibility into the information realization process.     

A Method for the Syntax Directed Design of Multiprograms

A method of program design is described which leads naturally to the expression of a program as a pipeline network of simple processes. Starting from the problem statement the valid inputs and outputs are specified by grammars, which can be combined to define the requisite translation. A notation for translation grammars is described informally which allows a translation to take into account semantic as well as syntactic information. Terminal symbols may be attributed by data types and may be qualified by Boolean expressions. The notation is capable of direct compilation but in this paper we show how it may be used to derive a program in a conventional high level language such as Pascal or Cobol. It is shown that more complex problems can be solved by simple pipeline structures of simple translations. Provided that nonbacktracking grammars are used to specify translations, the pipeline structure is well-suited to concurrent execution on a multiprocessor. The method is illustrated by examples from data processing.     

A self-organizing knowledge representation scheme for extensibleheterogeneous information environment

The self-organizing knowledge representation aspects in heterogeneous information environments involving object-oriented databases, relational databases, and rulebases are investigated. The authors consider a facet of self-organizability which sustains the structural semantic integrity of an integrated schemea regardless of the dynamic nature of local schemata. To achieve this objective, they propose an overall scheme for schema translation and schema integration with an object-oriented data model as common data model, and it is shown that integrated schemata can be maintained effortlessly by propagating updates in local schemata to integrated schemata unambiguously     

Parsers for indexed grammars

Three classes of parsable indexed grammars are defined. The new parsing mechanisms are derived by extending those that have been most successful for contextfree grammars, the LR and LL algorithms. Design criteria for the new grammar classes include membership decidability and unambiguity. We show that all three parsers operate in linear time for at least some grammars in our new classes. One of our new classes generates all the deterministic contextfree languages, along with some noncontextfree languages. We also show that the flag strings generated by indexed grammars are regular sets. This is done by showing that they can be generated by regular canonical systems.     

Context-free hypergraph grammars have the same term-generating power as attribute grammars

Context-free hypergraph grammars and attribute grammars generate the same class of term languages. Extending the context-free hypergraph grammar with a context-free grammar and a semantic domain, a syntax-directed translation device is obtained that is equivalent to the attribute grammar.     

String and graph grammar characterizations of bounded regular languages

Two grammatical characterizations of the bounded regular languages are presented: one in terms of graph grammars, the other using string grammars. First it is shown that a class of state graphs recognizing the bounded regular languages can be generated by a particular second-order contextfree graph grammar. Next we call uniquely recursive a right-linear (string) grammar having at most one right-recursive production for each of its nonterminals. It is then established that the class of languages generated by uniquely recursive, sequential right-linear grammars is exactly the bounded regular languages. Some comments on the relationship between string and graph grammars are made.     

Reducing the search space for conceptual schema transformation

In this paper we focus on the transformation of a conceptual schema into an internal schema. For a given conceptual schema, quite a number of internal schemata can be derived. This number can be reduced by imposing restrictions on internal schemata.

We present a transformation algorithm that can generate internal schemata of several types (including the relational model and the NF² model). Guidance parameters are used to impose further restrictions.

We harmonise the different types of schemata by extending the conceptual language, such that both the conceptual and the internal models can be represented within the same language.     

Semantic schema refinements for multilevel schema integration

Within the database field, schema refinements have been proved useful for documentation and maintenance purposes; moreover, schemata describing the reality of interest at different levels of abstraction are extensively used in Computer Aided Software Engineering tools and visual query languages. So, much effort has been spent in analyzing schema transformations and schema refinements. Till now, however, while the syntaxof schema transformations has been deeply investigated, the semantics has been very often neglected. In this paper we present a full formal framework, supporting both the syntax and the semantics of schema refinements. Such a formal framework is used to support a methodology able to merge a set of schemata and the top-down chains of refinement planes produced during their design. The result of this kind of integration, that we call multilevel integration, is an integrated schema plus an associated top-down chain of schemata. The integrated schema and the chain are related to the input schemata by interesting properties, giving rise to a two-dimensional structure useful for exploring the data content of complex information systems.     

ω上下文无关语言和语言的附着之间的关系

文章研究了用重复集生成的ω语言和语言的附着之间的关系,指出并证明了上下文无关语言附着类是ω上下文无关语言类的真子类,正规语言附着类是ω正规语言类的真子类．作为上下文无关语言的一个真子类——线性语言的附着类是ω正规语言类的真子类.     

Die Verwandtschaft kontextfreier Grammatiken

We take up the question of relationship between grammars which has been initiated by G. Hotz. Two new theorems on factorization of arbitrary transformations into embeddings and reductions and on product constructions involving non-lengthpreserving homomorphisms are derived. With the help of these two theorems we can characterize the general relationship of unambiguous contextfree grammars by the relationship, defined by simulations. Simulations are wellknown in the case of normal-form-constructions. A necessary condition is given for the relationship of linear grammars, which is sufficient in the case of leftlinear grammars. A problem of G. Hotz, concerning the relationship of weakly equivalent linear grammars is answered negatively.     

Model correspondence as a basis for schema domination

Conceptual schemata each representing some component of a system in the making, can be integrated in a variety of ways. Herein, we explore some fundamental notions of this. In particular, we examine some ways in which integration using correspondence assertions affects the interrelationship of two component schemata. Our analysis of the logic leads us to reject the commonly asserted requirement of constraining correspondence assertions to single predicates from a source schema. Much previous work has focussed on dominance with regard to preservation of information capacity as a primary integration criterion. However, even though it is desirable that the information capacity of a combined schema dominate one or both of its constituent schemata, we here discuss some aspects of why domination based on information capacity alone is insufficient for the integration to be semantically satisfactory, and we provide a framework for detecting mappings that prevent schema domination.     

Global extensional assertions and local integrity constraints in federated schemata

Integrated access to multiple data sources requires a homogeneous interface provided by a federated schema. Such a federated schema should correctly reflect the semantics of the component schemata of which it is composed. Since the semantics of a database schema is also determined by a set of semantic integrity constraints, a correct schema integration has to deal with integrity constraints existing in the different component schemata. Traditionally, most schema integration approaches solely concentrate on the structural integration of given database schemata. Local integrity constraints are often simply neglected. Their relationship to global extensional assertions, which form the basic integration constraints, are even ignored completely. In this paper, we discuss the impact of global extensional assertions and local integrity constraints on federated schemata. In particular, we point out the correspondence between local integrity constraints and global extensional assertions. The knowledge about the correspondences between the given integrity constraints and extensional assertions can then be utilized for an augmented schema integration process.     

The parser generating system PGS

PGS is a parser generating system accepting LALR(1) and related grammars in extended BNF notation and producing parsers based on table-driven stack automata. To enable syntax-directed translation, semantic actions can be attached to rules of the input grammar. An attribution mechanism allows the transfer of information between rules. The generated parsers have an automatic error recovery which can be tailored to satisfy specific needs of the language to be accepted. PGS generates parsers written in Pascal, Modula-2, C or Ada. Compared with existing systems, e.g. YACC¹, a parser generated by PGS is twice as fast and the parse tables require 25 per cent less storage. This paper gives a survey of algorithms involved in the generator and the generated parsers, and compares them with algorithms used in other systems. In detail, it compares several parse-table representations and their implications for space and time efficiency of the generated parsers.     

A runtime approach to model-generic translation of schema and data

To support heterogeneity is a major requirement in current approaches to integration and transformation of data. This paper proposes a new approach to the translation of schema and data from one data model to another, and we illustrate its implementation in the tool MIDST-RT.We leverage on our previous work on MIDST, a platform conceived to perform translations in an off-line fashion. In such an approach, the source database (both schema and data) is imported into a repository, where it is stored in a universal model. Then, the translation is applied within the tool as a composition of elementary transformation steps, specified as Datalog programs. Finally, the result (again both schema and data) is exported into the operational system.Here we illustrate a new, lightweight approach where the database is not imported. MIDST-RT needs only to know the schema of the source database and the model of the target one, and generates views on the operational system that expose the underlying data according to the corresponding schema in the target model. Views are generated in an almost automatic way, on the basis of the Datalog rules for schema translation.The proposed solution can be applied to different scenarios, which include data and application migration, data interchange, and object-to-relational mapping between applications and databases.     

Examples of algorithms specification by means of attribute grammars

Attribute grammars gave rise to a great interest from many authors as a means of specifying syntax-directed translation because of their naturalness and declarative rather then algorithmic character which make the definition of a language easier to understand and more concise. In this paper the field of algorithms specification by means of attribute grammars is investigated with further ideas and examples. This paper is a further development of thecontent of my thesis in mathematics supported by a grant offered by the C.N.R.—Comitato Nazionale per le Scienze Matematiche. Proposto collaboratore per il Progetto Finalizzato Informatica—CNR. obiettivo Sofmat.     

Treating data privacy in distributed systems

This papers describes and is primarily concerned with the security data definition and management in a distributed data base of aggregated type, although the approach described may be applied to any distributed system architecture. A multi-level logical security architecture is presented reflecting the logical architecture of the distributed system. In particular, three security logical schemata are proposed: the network security schema, the external security schemata, and the intermediate security schemata. For each schema data models are introduced, allowing the definition and the management of security information. Mapping rules between the logical levels are discussed. Finally security mechanisms are analyzed.     

数据集成中XML Schema到关系模式的转换方法

根据XML Schema中组件的定义及组件之间的嵌套关系,建立一系列从XML Schema转换成关系模式的结构映射规则和语义映射规则。基于这些规则实现一种转换算法,从Schema中提取出关系模式,并且证明映射得到的关系模式满足4NF。结果表明得到的关系模式不仅包含了XML Schema中所有的结构和内容信息,还能保留大部分语义约束信息,减少存储冗余。