article

Nondeterministic computations in sublogarithmic space and space constructibility

Author:

Viliam GeffertAuthors Info & Claims

SIAM Journal on Computing, Volume 20, Issue 3

Pages 484 - 498

https://doi.org/10.1137/0220031

Published: 01 April 1991 Publication History

Abstract

No abstract available.

Cited By

View all

Geffert V(2019)Space hierarchy theorem revisedTheoretical Computer Science10.5555/2780705.2781193295:1(171-187)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/2780705.2781193
Geffert VMereghetti CPighizzini G(2019)Converting two-way nondeterministic unary automata into simpler automataTheoretical Computer Science10.5555/2780705.2781182295:1(189-203)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/2780705.2781182
Geffert VPighizzini GMereghetti C(2019)One Pebble Versus ϵ · log n BitsFundamenta Informaticae10.5555/1922662.1922666104:1-2(55-69)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/1922662.1922666
Show More Cited By

Index Terms

Nondeterministic computations in sublogarithmic space and space constructibility
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity classes
  2. Models of computation
    1. Computability
      1. Turing machines

Recommendations

Alternation for sublogarithmic space-bounded alternating pushdown automata

This paper investigates infinite hierarchies on alternation-depth and alternation-size of alternating pushdown automata (apda's) with sublogarithmic space. We first show that there is an infinite hierarchy on alternation-depth for apda's with ...
Some properties of one-pebble turing machines with sublogarithmic space

This paper investigates some aspects of the accepting powers of deterministic, nondeterministic, and alternating one-pebble Turing machines with spaces between log log n and log n. We first investigate a relationship between the accepting powers of two-...
Sublogarithmic Space-bounded Multi-inkdot Alternating Pushdown Automata with Only Existential (Universal) States
JCAI '09: Proceedings of the 2009 International Joint Conference on Artificial Intelligence

This paper investigates some properties of two-way alternating pushdown automata with only existential (universal) states which have inkdots and sublogarithmic space. We show, for example, that for sublogarithmic space-bounded computations, multi-inkdot ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIAM Journal on Computing Volume 20, Issue 3

June 1991

198 pages

ISSN:0097-5397

Editor:
A. Yao

Issue’s Table of Contents

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 April 1991

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

9
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Geffert V(2019)Space hierarchy theorem revisedTheoretical Computer Science10.5555/2780705.2781193295:1(171-187)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/2780705.2781193
Geffert VMereghetti CPighizzini G(2019)Converting two-way nondeterministic unary automata into simpler automataTheoretical Computer Science10.5555/2780705.2781182295:1(189-203)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/2780705.2781182
Geffert VPighizzini GMereghetti C(2019)One Pebble Versus ϵ · log n BitsFundamenta Informaticae10.5555/1922662.1922666104:1-2(55-69)Online publication date: 4-Jan-2019
https://dl.acm.org/doi/10.5555/1922662.1922666
Geffert V(2019)Unary Coded PSPACE-Complete Languages in ASPACE(loglog n)Theory of Computing Systems10.1007/s00224-018-9844-763:4(688-714)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s00224-018-9844-7
Uchida YIto TOkabe HSakamoto MFurutani HKono M(2018)Four-dimensional multi-inkdot finite automataWSEAS Transactions on Computers10.5555/1481923.14819297:9(1437-1446)Online publication date: 17-Dec-2018
https://dl.acm.org/doi/10.5555/1481923.1481929
Dujnič JFrištacký NMolnár LPlander IRovan B(2018)On the History of Computer Science, Computer Engineering, and Computer Technology Development in SlovakiaIEEE Annals of the History of Computing10.1109/85.77898121:3(38-48)Online publication date: 27-Dec-2018
https://dl.acm.org/doi/10.1109/85.778981
Jirásková GOkhotin A(2008)On the State Complexity of Operations on Two-Way Finite AutomataProceedings of the 12th international conference on Developments in Language Theory10.1007/978-3-540-85780-8_35(443-454)Online publication date: 16-Sep-2008
https://dl.acm.org/doi/10.1007/978-3-540-85780-8_35
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
Xu JLiu YYoshinaga T(2006)A note on non-closure property of sublogarithmic space-bounded 1-inkdot alternating pushdown automata with only existential (universal) statesJournal of Computer Science and Technology10.1007/s11390-006-0979-721:6(979-983)Online publication date: 1-Nov-2006
https://dl.acm.org/doi/10.1007/s11390-006-0979-7

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

Alternation for sublogarithmic space-bounded alternating pushdown automata

Some properties of one-pebble turing machines with sublogarithmic space

Sublogarithmic Space-bounded Multi-inkdot Alternating Pushdown Automata with Only Existential (Universal) States

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