The hardest language for grammars with context operators

DOI10.1016/j.tcs.2023.113829arXiv2012.03596OpenAlexW3117953580MaRDI QIDQ6038689

Mikhail Mrykhin, Alexander Okhotin

Publication date: 2 May 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

formal grammarsformal language theoryfinite transducersinverse homomorphismsgrammars with context operatorshardest formal languages

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Parsing by matrix multiplication generalized to Boolean grammars
• Conjunctive grammars with restricted disjunction
• A tale of conjunctive grammars
• Linear-space recognition for grammars with contexts
• Hardest languages for conjunctive and Boolean grammars
• On hardest languages for one-dimensional cellular automata
• An extension of context-free grammars with one-sided context specifications
• Improved normal form for grammars with one-sided contexts
• Two-sided context specifications in formal grammars
• Generalized LR parsing algorithm for grammars with one-sided contexts
• BOOLEAN GRAMMARS AND GSM MAPPINGS
• Non-prinicipalité du cylindre des langages à compteur
• Le cylindre des langages linéaires
• The Hardest Context-Free Language
• Jump PDA’s and Hierarchies of Deterministic Context-Free Languages
• Recognizing Two-Sided Contexts in Cubic Time
• Linear grammars with one-sided contexts and their automaton representation
• On Relations Defined by Generalized Finite Automata
• Preservation of unambiguity and inherent ambiguity in context-free languages
• The Hardest LL(k) Language

This page was built for publication: The hardest language for grammars with context operators