Giorgio Satta

TCS Journal 2021 Journal Article

Bottom-up unranked tree-to-graph transducers for translation into semantic graphs

• Johanna Björklund
• Shay B. Cohen
• Frank Drewes
• Giorgio Satta

We develop a finite-state transducer for translating unranked trees into general graphs. This work is motivated by recent progress in semantic parsing for natural language, where sentences are first mapped into tree-shaped syntactic representations, and then these trees are translated into graph semantic representations. We investigate formal properties of our tree-to-graph transducers and develop a polynomial time algorithm for translating a weighted language of input trees into a packed representation, from which best-score graphs can be efficiently recovered.

AAAI Conference 2018 Conference Paper

AMR Parsing With Cache Transition Systems

• Xiaochang Peng
• Daniel Gildea
• Giorgio Satta

In this paper, we present a transition system that generalizes transition-based dependency parsing techniques to generate AMR graphs rather than tree structures. In addition to a buffer and a stack, we use a fixed-size cache, and allow the system to build arcs to any vertices present in the cache at the same time. The size of the cache provides a parameter that can trade off between the complexity of the graphs that can be built and the ease of predicting actions during parsing. Our results show that a cache transition system can cover almost all AMR graphs with a small cache size, and our end-to-end system achieves competitive results in comparison with other transition-based approaches for AMR parsing.

TCS Journal 2008 Journal Article

Computation of distances for regular and context-free probabilistic languages

• Mark-Jan Nederhof
• Giorgio Satta

Several mathematical distances between probabilistic languages have been investigated in the literature, motivated by applications in language modeling, computational biology, syntactic pattern matching and machine learning. In most cases, only pairs of probabilistic regular languages were considered. In this paper we extend the previous results to pairs of languages generated by a probabilistic context-free grammar and a probabilistic finite automaton.

I&C Journal 2004 Journal Article

The language intersection problem for non-recursive context-free grammars

• Mark-Jan Nederhof
• Giorgio Satta

We prove that, given as input two context-free grammars, deciding non-emptiness of intersection of the two generated languages is PSPACE-complete if at least one grammar is non-recursive. The problem remains PSPACE-complete when both grammars are non-recursive and deterministic. Also investigated are generalizations of the problem to several context-free grammars, of which a certain number are non-recursive.

ECAI Conference 2000 Conference Paper

Bringing Information Extraction out of the Labs: the NoName Environment

• Fabio Ciravegna
• Alberto Lavelli
• Giorgio Satta

TCS Journal 1999 Journal Article

Independent parallelism in finite copying parallel rewriting systems

• Owen Rambow
• Giorgio Satta

We consider the class of parallel rewriting systems and investigate the interaction between two complexity measures, that in the literature have been called synchronized parallelism and independent parallelism. It is shown that, when the degree of synchronized parallelism is bounded by some constant greater than one, the degree of independent parallelism induces an infinite non-collapsing hierarchy within the family of generated languages. The result is obtained using an original characterization of parallel rewriting systems. Other language-theoretic properties of parallel rewriting systems are proved in this work, that together with our main result provide an answer to some questions that were left open in the literature.

AIJ Journal 1994 Journal Article

Bidirectional context-free grammar parsing for natural language processing

• Giorgio Satta
• Oliviero Stock

While natural language is usually analyzed from left to right, bidirectional parsing is very attractive for both theoretical and practical reasons. In this paper, we describe a formal framework for bidirectional tabular parsing of general context-free languages, and some applications to natural language processing are studied. The framework is general and permits a comparison between known approaches and the algorithms outlined here. A detailed analysis of the redundancy problem is given and a technique for improving the performance of bidirectional tabular parsers, whilst maintaining the flexibility of bidirectional strategies, is described. An algorithm for head-driven parsing and a general algorithm for island-driven parsing are studied. The former allows analyses of each constituent to be triggered by some fixed immediately dominated element, chosen on the basis of its information content. The latter permits analyses to start from any dynamically chosen positions within the input sentence, combining bottom-up and top-down processing without redundancy.

AAAI Conference 1991 Conference Paper

A Tabular Method for Island-Driven Context-Free Grammar Parsing

• Giorgio Satta

Island-driven parsing is of grea. t relevance for speech recognition/understanding and other na. tural language processing applications. A bidirectional algorithm is presented that efficiently solves this problem, allowing both any possible determination of the starting words in the input sentence and flexible control. In pazticular, a mixed bottom-to-top and top-down approach is followed, without leading to redunclantV partial analyses. The algorithm performance is discussed.

IJCAI Conference 1989 Conference Paper

Formal Properties and Implementation of Bidirectional Charts

• Giorgio Satta
• Oliviero Stock