intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE

Báo cáo khoa học: "On the Computational Complexity of Dominance Links in Grammatical Formalisms"

Chia sẻ: Hongdo_1 Hongdo_1 | Ngày: | Loại File: PDF | Số trang:11

57
lượt xem
2
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Dominance links were introduced in grammars to model long distance scrambling phenomena, motivating the definition of multiset-valued linear indexed grammars (MLIGs) by Rambow (1994b), and inspiring quite a few recent formalisms. It turns out that MLIGs have since been rediscovered and reused in a variety of contexts, and that the complexity of their emptiness problem has become the key to several open questions in computer science. We survey complexity results and open issues on MLIGs and related formalisms, and provide new complexity bounds for some linguistically motivated restrictions. ...

Chủ đề:
Lưu

Nội dung Text: Báo cáo khoa học: "On the Computational Complexity of Dominance Links in Grammatical Formalisms"

ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2