Lena Katharina Schiffer
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Lena Katharina Schiffer has a total of 3 co-authors. Here are the top co-authors by number of shared publications:
- Andreas Maletti
Universität Leipzig
3 shared publications - Marco Kuhlmann
Linköping University
2 shared publications - Giorgio Satta
Dept. of Information Engineering University of Padua
1 shared publication
Latest Publications
- 25 July 2023
- Published by Elsevier in Information and Computation
- Vol. 294
Combinatory categorial grammars as generators of weighted forests
- 25 July 2023
- Published by Elsevier in Information and Computation
- Vol. 294
Combinatory categorial grammars as generators of weighted forests
- Open Access
- 19 May 2022
- Published by MIT Press in Computational Linguistics
- Vol. 48 (3) , 1-41
Tractable Parsing for CCGs of Bounded Degree
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 degree of composition has been suggested as a universal constraint on natural language grammar. Moreover, ours is the first complexity result for a version of CCG that includes substitution rules, which are used in practical grammars but have been ignored in theoretical work.
- 19 May 2022
- Published by MIT Press in Computational Linguistics
- Vol. 48 (3) , 1-41
Open AccessTractable Parsing for CCGs of Bounded Degree
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 degree of composition has been suggested as a universal constraint on natural language grammar. Moreover, ours is the first complexity result for a version of CCG that includes substitution rules, which are used in practical grammars but have been ignored in theoretical work.
- Open Access
- 1 March 2022
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 124, 214-233
The tree-generative capacity of combinatory categorial grammars
- 1 March 2022
- Published by Elsevier in Journal of Computer and System Sciences
- Vol. 124, 214-233
Open AccessThe tree-generative capacity of combinatory categorial grammars
- Open Access
- 2 August 2021
- Published by MIT Press in Transactions of the Association for Computational Linguistics
- Vol. 9, 707-720
Strong Equivalence of TAG and CCG
Tree-adjoining grammar (TAG) and combinatory categorial grammar (CCG) are two well-established mildly context-sensitive grammar formalisms that are known to have the same expressive power on strings (i.e., generate the same class of string languages). It is demonstrated that their expressive power on trees also essentially coincides. In fact, CCG without lexicon entries for the empty string and only first-order rules of degree at most 2 are sufficient for its full expressive power.
- 2 August 2021
- Published by MIT Press in Transactions of the Association for Computational Linguistics
- Vol. 9, 707-720
Open AccessStrong Equivalence of TAG and CCG
Tree-adjoining grammar (TAG) and combinatory categorial grammar (CCG) are two well-established mildly context-sensitive grammar formalisms that are known to have the same expressive power on strings (i.e., generate the same class of string languages). It is demonstrated that their expressive power on trees also essentially coincides. In fact, CCG without lexicon entries for the empty string and only first-order rules of degree at most 2 are sufficient for its full expressive power.