On the sizes of DPDAs, PDAs, LBAs

DOI10.1016/j.tcs.2015.08.028zbMath1453.68099arXiv1503.08847OpenAlexW1882952697MaRDI QIDQ294936

Richard Beigel, William I. Gasarch

Publication date: 16 June 2016

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

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

zbMATH Keywords

context-free languagespushdown automatalength of description of languageslinear bounded automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• The method of forced enumeration for nondeterministic automata
• General context-free recognition in less than cubic time
• Lower bounds for context-free grammars
• On degrees of unsolvability
• Fast context-free grammar parsing requires fast boolean matrix multiplication
• Powers of tensors and fast matrix multiplication
• Nondeterministic Space is Closed under Complementation
• On the Succinctness of Different Representations of Languages
• Regularity and Related Problems for Deterministic Pushdown Automata
• Program size in restricted programming languages
• A note on the succinctness of descriptions of deterministic languages
• On the power of bounded concurrency II
• On the recursion-theoretic complexity of relative succinctness of representations of languages
• A regularity test for pushdown machines

This page was built for publication: On the sizes of DPDAs, PDAs, LBAs