On the sizes of DPDAs, PDAs, LBAs
From MaRDI portal
Publication:294936
DOI10.1016/j.tcs.2015.08.028zbMath1453.68099arXiv1503.08847MaRDI 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
context-free languages; pushdown automata; length of description of languages; linear bounded automata
68Q45: Formal languages and automata
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