article

A lower bound for the nondeterministic space complexity of context-free recognition

Authors:

Helmut Alt,

Viliam Geffert,

Kurt MehlhornAuthors Info & Claims

Information Processing Letters, Volume 42, Issue 1

Pages 25 - 27

https://doi.org/10.1016/0020-0190(92)90127-H

Published: 27 April 1992 Publication History

Abstract

No abstract available.

Cited By

View all

Yakaryılmaz ASay A(2013)Proving the Power of PostselectionFundamenta Informaticae10.5555/2594865.2594873123:1(107-134)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.5555/2594865.2594873
Yakaryılmaz AFreivalds RSay AAgadzanyan R(2012)Quantum computation with write-only memoryNatural Computing: an international journal10.1007/s11047-011-9270-011:1(81-94)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1007/s11047-011-9270-0
Yakaryilmaz ASay A(2010)Languages recognized by nondeterministic quantum finite automataQuantum Information & Computation10.5555/2011464.201146710:9(747-770)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.5555/2011464.2011467
Show More Cited By

Index Terms

A lower bound for the nondeterministic space complexity of context-free recognition
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
2. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Formal languages and automata theory

Recommendations

Büchi context-free languages

We define context-free grammars with Buchi acceptance condition generating languages of countable words. We establish several closure properties and decidability results for the class of Buchi context-free languages generated by these grammars. We also ...
Descriptional complexity of union and star on context-free languages

We investigate context-free languages with respect to the measures Prod and Symb of descriptional complexity, which give the minimal number of productions and the minimal total number of symbols in productions, respectively, necessary to generate the ...
Nonterminal Complexity of Some Operations on Context-Free Languages

We investigate context-free languages with respect to the measure Var of descriptional complexity, which gives the minimal number of nonterminals necessary to generate a language. More specifically, we consider the behaviour of this measure with respect ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Information Processing Letters Volume 42, Issue 1

April 27, 1992

54 pages

ISSN:0020-0190

Editor:
W. M. Turski
Warsaw Univ., Warsaw, Poland

Issue’s Table of Contents

Publisher

Elsevier North-Holland, Inc.

United States

Publication History

Published: 27 April 1992

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Yakaryılmaz ASay A(2013)Proving the Power of PostselectionFundamenta Informaticae10.5555/2594865.2594873123:1(107-134)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.5555/2594865.2594873
Yakaryılmaz AFreivalds RSay AAgadzanyan R(2012)Quantum computation with write-only memoryNatural Computing: an international journal10.1007/s11047-011-9270-011:1(81-94)Online publication date: 1-Mar-2012
https://dl.acm.org/doi/10.1007/s11047-011-9270-0
Yakaryilmaz ASay A(2010)Languages recognized by nondeterministic quantum finite automataQuantum Information & Computation10.5555/2011464.201146710:9(747-770)Online publication date: 1-Sep-2010
https://dl.acm.org/doi/10.5555/2011464.2011467
Demetrescu CFinocchi IRibichini A(2009)Trading off space for passes in graph streaming problemsACM Transactions on Algorithms10.1145/1644015.16440216:1(1-17)Online publication date: 28-Dec-2009
https://dl.acm.org/doi/10.1145/1644015.1644021
Geffert V(2007)Magic numbers in the state hierarchy of finite automataInformation and Computation10.1016/j.ic.2007.07.001205:11(1652-1670)Online publication date: 1-Nov-2007
https://dl.acm.org/doi/10.1016/j.ic.2007.07.001
Demetrescu CFinocchi IRibichini A(2006)Trading off space for passes in graph streaming problemsProceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm10.5555/1109557.1109635(714-723)Online publication date: 22-Jan-2006
https://dl.acm.org/doi/10.5555/1109557.1109635

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

Büchi context-free languages

Descriptional complexity of union and star on context-free languages

Nonterminal Complexity of Some Operations on Context-Free Languages

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations