Báo cáo khoa học: "Linear Context-Free Rewriting Systems and Deterministic Tree-Walking Transducers*"

We show that the class of string languages generated by linear context-free rewriting systems is equal to the class of output languages of deterministic treewalking transducers. From equivalences that have previously been established we know that this class of languages is also equal to the string languages generated by context-free hypergraph grammars, multicomponent tree-adjoining grammars, and multiple contextfree grammars and to the class of yields of images of the regular tree languages under finite-copying topdown tree transducers. .

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.