2014/03/24 by Alexey Sorokin, Sorokin, Alexey
Biochemistry, Genetics and Molecular Biology · Computer Science · #Chemical Synthesis and Analysis #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Formal Methods in Verification #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1403.6060
Revised version for ESSLLI Student Session 2013 selected papers
arxiv created 2014/03/24 · openalex publication_date 2014/03/24 · arxiv updated 2014/03/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In 2007 Kambites presented an algebraic interpretation of Chomsky-Schutzenberger theorem for context-free languages. We give an interpretation of the corresponding theorem for the class of displacement context-free languages which are equivalent to well-nested multiple context-free languages. We also obtain a characterization of k-displacement context-free languages in terms of monoid automata and show how such automata can be simulated on two stacks. We introduce the simultaneous two-stack automata and compare different variants of its definition. All the definitions considered are shown to be equivalent basing on the geometric interpretation of memory operations of these automata.