Giorgio Satta

Biographic Data

ID6536270
NAMEGiorgio Satta
GIVEN NAMESGiorgio
FAMILY NAMESatta
SIGNATURESATTA G
AFFILIATIONSUniversity of Padua
ORCID0000-0001-7742-6438
VERIFIEDYes
TOTAL WORKS10
TOTAL CITATIONS7
WORKS AS AUTHOR10
WORKS AS EDITOR0
FIRST PUBLICATION YEAR2010
LATEST PUBLICATION YEAR2022
H-INDEX1

  • Tractable Parsing for CCGs of Bounded Degree

    Open AccessLena Katharina Schiffer, Marco Kuhlmann et al.ARTICLEComputational Linguistics2022References: 3

    Unlike other mildly context-sensitive formalisms, Combinatory Categorial Grammar (CCG) cannot be parsed in polynomial time when the size of the grammar is taken into account. Refining this result, we show that the parsing complexity of CCG is exponential only in the maximum degree of composition. When that degree is fixed, parsing can be carried out in polynomial time. Our finding is interesting from a linguistic perspective because a bounded deg…

  • Ordered Tree Decomposition for HRG Rule Extraction

    Open AccessDaniel Gildea, Giorgio Satta et al.ARTICLEComputational Linguistics2019References: 2

    We present algorithms for extracting Hyperedge Replacement Grammar (HRG) rules from a graph along with a vertex order. Our algorithms are based on finding a tree decomposition of smallest width, relative to the vertex order, and then extracting one rule for each node in this structure. The assumption of a fixed order for the vertices of the input graph makes it possible to solve the problem in polynomial time, in contrast to the fact that the pro…

  • On the Complexity of CCG Parsing

    Open AccessMarco Kuhlmann, Giorgio Satta et al.ARTICLEComputational Linguistics2018Cited by: 1References: 6

    We study the parsing complexity of Combinatory Categorial Grammar (CCG) in the formalism of Vijay-Shanker and Weir ( 1994 ). As our main result, we prove that any parsing algorithm for this formalism will take in the worst case exponential time when the size of the grammar, and not only the length of the input sentence, is included in the analysis. This sets the formalism of Vijay-Shanker and Weir ( 1994 ) apart from weakly equivalent formalisms …

  • Weighted DAG Automata for Semantic Graphs

    Open AccessDavid Chiang, Frank Drewes et al.ARTICLEComputational Linguistics2017

    Graphs have a variety of uses in natural language processing, particularly as representations of linguistic meaning. A deficit in this area of research is a formal framework for creating, combining, and using models involving graphs that parallels the frameworks of finite automata for strings and finite tree automata for trees. A possible starting point for such a framework is the formalism of directed acyclic graph (DAG) automata, defined by Kam…

  • Cache Transition Systems for Graph Parsing

    Open AccessDaniel Gildea, Giorgio Satta et al.ARTICLEComputational Linguistics2017Cited by: 1References: 1

    Motivated by the task of semantic parsing, we describe a transition system that generalizes standard transition-based dependency parsing techniques to generate a graph rather than a tree. Our system includes a cache with fixed size m, and we characterize the relationship between the parameter m and the class of graphs that can be produced through the graph-theoretic concept of tree decomposition. We find empirically that small cache sizes cover a…

  • Synchronous Context-Free Grammars and Optimal Parsing Strategies

    Open AccessDaniel Gildea, Giorgio SattaARTICLEComputational Linguistics2016References: 1

    The complexity of parsing with synchronous context-free grammars is polynomial in the sentence length for a fixed grammar, but the degree of the polynomial depends on the grammar. Specifically, the degree depends on the length of rules, the permutations represented by the rules, and the parsing strategy adopted to decompose the recognition of a rule into smaller steps. We address the problem of finding the best parsing strategy for a rule, in ter…

  • Lexicalization and Generative Power in CCG

    Open AccessMarco Kuhlmann, Alexander Koller et al.ARTICLEComputational Linguistics2015Cited by: 5References: 1

    The weak equivalence of Combinatory Categorial Grammar (CCG) and Tree-Adjoining Grammar (TAG) is a central result of the literature on mildly context-sensitive grammar formalisms. However, the categorial formalism for which this equivalence has been established differs significantly from the versions of CCG that are in use today. In particular, it allows restriction of combinatory rules on a per grammar basis, whereas modern CCG assumes a univers…

  • Splittability of Bilexical Context-Free Grammars is Undecidable

    Open AccessMark-Jan Nederhof, Giorgio SattaARTICLEComputational Linguistics2011References: 1

    Bilexical context-free grammars (2-LCFGs) have proved to be accurate models for statistical natural language parsing. Existing dynamic programming algorithms used to parse sentences under these models have running time of O(∣w∣ 4 ), where w is the input string. A 2-LCFG is splittable if the left arguments of a lexical head are always independent of the right arguments, and vice versa. When a 2-LCFGs is splittable, parsing time can be asymptotical…

  • Tree-Adjoining Grammars Are Not Closed Under Strong Lexicalization

    Open AccessMarco Kuhlmann, Giorgio SattaARTICLEComputational Linguistics2011

    A lexicalized tree-adjoining grammar is a tree-adjoining grammar where each elementary tree contains some overt lexical item. Such grammars are being used to give lexical accounts of syntactic phenomena, where an elementary tree defines the domain of locality of the syntactic and semantic dependencies of its lexical items. It has been claimed in the literature that for every tree-adjoining grammar, one can construct a strongly equivalent lexicali…

  • Complexity, Parsing, and Factorization of Tree-Local Multi-Component Tree-Adjoining Grammar

    Open AccessRebecca Nesson, Giorgio Satta et al.ARTICLEComputational Linguistics2010References: 1

    Tree-Local Multi-Component Tree-Adjoining Grammar (TL-MCTAG) is an appealing formalism for natural language representation because it arguably allows the encapsulation of the appropriate domain of locality within its elementary structures. Its multicomponent structure allows modeling of lexical items that may ultimately have elements far apart in a sentence, such as quantifiers and wh-words. When used as the base formalism for a synchronous gramm…