The complexity of the membership problem for some extensions of context-free languagest†

DOI10.1080/00207167708803138zbMath0398.68037OpenAlexW2056449710MaRDI QIDQ4181980

Ivan Hal Sudborough

Publication date: 1977

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207167708803138

zbMATH Keywords

ComplexityRegular SetVector GrammarsRecognition ProblemEdol LanguagesEol LanguagesExtensions of Context-Free LanguagesHomomorphic ReplicationMembership ProblemPushdown AutomataState Grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (12)

Pattern selector grammars and several parsing algorithms in the context- free style ⋮ Unnamed Item ⋮ Tree-size bounded alternation ⋮ On uniform circuit complexity ⋮ Properties that characterize LOGCFL ⋮ A geometric hierarchy beyond context-free languages ⋮ One way finite visit automata ⋮ On languages specified by relative acceptance ⋮ The effective entropies of some extensions of context-free languages ⋮ CONTEXT-FREE GRAMMARS WITH LINKED NONTERMINALS ⋮ Time and space complexity of inside-out macro languages ⋮ Sequential grammars and automata with valences

Cites Work

• Unnamed Item
• Unnamed Item
• A geometric hierarchy of languages
• The membership question for ETOL-languages is polynomially complete
• General context-free recognition in less than cubic time
• The tape-complexity of context-independent developmental languages
• Space-bounded reducibility among combinatorial problems
• On vector languages
• Checking automata and one-way stack languages
• A hierarchy between context-free and context-sensitive languages
• AFL with the semilinear property
• On two-way multihead automata
• A Note on Tape-Bounded Complexity Classes and Linear Context-Free languages
• The Hardest Context-Free Language
• Deterministic context free languages
• Finite-Turn Pushdown Automata
• Control sets on grammars
• One-way stack automata
• Multi-tape and multi-head pushdown automata
• Programmed Grammars and Classes of Formal Languages
• Simple matrix languages
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Periodically time-variant context-free grammars
• An Overview of the Theory of Computational Complexity
• Matrix grammars with a leftmost restriction
• On matrix languages

This page was built for publication: The complexity of the membership problem for some extensions of context-free languagest†