An Automata Characterisation for Multiple Context-Free Languages

DOI10.1007/978-3-662-53132-7_12MaRDI QIDQ2817383zbMATH OpenOpenAlexFDO

Authors Tobias Denkinger

Publication date 30 August 2016

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.02975

zbMATH Keywords

multiple context-free languagestree stack automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We introduce tree stack automata as a new class of automata with storage and identify a restricted form of tree stack automata that recognises exactly the multiple context-free languages.

Cites work

• A Chomsky-Schützenberger Theorem for Weighted Automata with Storage
• Nested Stack Automata
• On context-free languages and push-down automata
• On multiple context-free grammars
• Pushdown tree automata
• Some definitional suggestions for automata theory

Cited in

(15)

• Families of automata characterizing context-sensitive languages
• Closure properties in the class of multiple context-free groups
• An Automata-Theoretical Characterization of Context-Free Trace Languages
• Approximation of weighted automata with storage
• Characterization of Star-Connected Languages Using Finite Automata
• scientific article; zbMATH DE number 1101595 (Why is no real title available?)
• scientific article; zbMATH DE number 7456062 (Why is no real title available?)
• On the expressivity of linear recursion schemes
• scientific article; zbMATH DE number 5593274 (Why is no real title available?)
• Tree-walking-storage automata
• Rational weighted tree languages with storage
• Probabilistic verification beyond context-freeness
• Deterministic tree-walking-storage automata
• Deterministic real-time tree-walking-storage automata
• Deterministic real-time tree-walking-storage automata

This page was built for publication: An Automata Characterisation for Multiple Context-Free Languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817383)