liu.seSearch for publications in DiVA
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
The Tree-Generative Capacity of Combinatory Categorial Grammars
Linköping University, Department of Computer and Information Science, Human-Centered systems. Linköping University, Faculty of Science & Engineering.ORCID iD: 0000-0002-2492-9872
University of Leipzig.
University of Leipzig.
2019 (English)In: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) / [ed] Arkadev Chattopadhyay, Paul Gastin, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2019, Vol. 150, p. 44:1-44:14Conference paper, Published paper (Refereed)
Abstract [en]

The generative capacity of combinatory categorial grammars as acceptors of forests is investigated. It is demonstrated that the such obtained forests can also be generated by simple monadic context-free tree grammars. However, the subclass of pure combinatory categorial grammars cannot even accept all regular forests. Additionally, the forests accepted by combinatory categorial grammars with limited rule degrees are characterized: If only application rules are allowed, then they can accept only a proper subset of the regular forests, whereas they can accept exactly the regular forests once first degree composition rules are permitted.

Place, publisher, year, edition, pages
Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2019. Vol. 150, p. 44:1-44:14
Series
Leibniz International Proceedings in Informatics (LIPIcs), ISSN 1868-8969 ; 150
National Category
Language Technology (Computational Linguistics)
Identifiers
URN: urn:nbn:se:liu:diva-168623DOI: 10.4230/LIPIcs.FSTTCS.2019.44Scopus ID: 2-s2.0-85077454133ISBN: 9783959771313 (print)OAI: oai:DiVA.org:liu-168623DiVA, id: diva2:1461481
Conference
39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019, December 11-13, 2019, Bombay, India
Available from: 2020-08-26 Created: 2020-08-26 Last updated: 2025-01-15

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopusPaper

Authority records

Kuhlmann, Marco

Search in DiVA

By author/editor
Kuhlmann, Marco
By organisation
Human-Centered systemsFaculty of Science & Engineering
Language Technology (Computational Linguistics)

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 36 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • oxford
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf