scientific article; zbMATH DE number 3363526
From MaRDI portal
Publication:5636862
Cited in
(only showing first 100 items - show all)- Space hierarchy theorem revised.
- On computational reducibility
- Writing pushdown acceptors
- Subrecursiveness: Machine-independent notions of computability in restricted time and storage
- On the computational complexity of membrane systems
- A note on alternating on-line Turing machines
- A space lower bound for acceptance by one-way \(\Pi_2\)-alternating machines
- Translation from classical two-way automata to pebble two-way automata
- A note on one-way and two-way automata
- The effect of end-markers on counter machines and commutativity
- Passively mobile communicating machines that use restricted space
- Space bounded computations: Review and new separation results
- A Fixed-Depth Size-Hierarchy Theorem for $\mathrm{AC}^0[\oplus]$ via the Coin Problem
- A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors
- Bridging across the \(\log(n)\) space frontier
- Relating refined space complexity classes
- Techniques for separating space complexity classes
- k\(+1\) heads are better than k for PDAs
- There are no fully space constructible functions between log log n and log n
- Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
- A hierarchy that does not collapse : alternations in low level space
- Comparing complexity classes
- Two-Way Automata versus Logarithmic Space
- Amount of Nonconstructivity in Finite Automata
- Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
- An optimal lower bound for nonregular languages
- Unary coded PSPACE-complete languages in \(\mathrm{ASPACE}(\log\log n)\)
- Writing stack acceptors
- The recursion-theoretic structure of complexity classes
- On pebble automata
- Nonexistence of program optimizers in several abstract settings
- Characterization of realizable space complexities
- Dimension and the structure of complexity classes
- For completeness, sublogarithmic space is no space.
- Reverse complexity
- Accepting networks of splicing processors: complexity results
- Weak and strong one-way space complexity classes
- An application of the translational method
- Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs
- On restricted turing computability
- The theory of languages
- Complexity barriers as independence
- Hierarchies of Turing machines with restricted tape alphabet size
- On small, reduced, and fast universal accepting networks of splicing processors
- On the language of primitive words
- Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
- The theory of languages
- Amplification of slight probabilistic advantage at absolutely no cost in space
- Deterministic versus nondeterministic space in terms of synchronized alternating machines
- On the size complexity of hybrid networks of evolutionary processors
- Translational lemmas, polynomial time, and \((\log n)^j\)-space
- Computational power of one-way Turing machines with sublogarithmic memory restrictions
- The polynomial-time hierarchy
- Multitape one-way nonwriting automata
- A survey of two-dimensional automata theory
- Halting space-bounded computations
- Improved approximations for hard optimization problems via problem instance classification
- Notes on looping deterministic two-way pushdown automata
- Time- and tape-bounded Turing acceptors and AFLs
- A remark on middle space bounded alternating Turing machines
- Minimal Size of Counters for (Real-Time) Multicounter Automata
- On store languages of language acceptors
- Two-way automata versus logarithmic space
- Alternating demon space is closed under complement and other simulations for sublogarithmic space
- Data structures for distributed counting
- Complexity of probabilistic versus deterministic automata
- Sublogarithmic $\sum _2$-space is not closed under complement and other separation results
- Space-bounded OTMs and REG ∞
- Random languages for nonuniform complexity classes
- On time hierarchies
- Space bounds for processing contentless inputs
- On the computational power of pushdown automata
- On non-determinacy in simple computing devices
- On space functions constructed by two-dimensional Turing machines
- On relationships between complexity classes of Turing machines
- Sublogarithmic-space turing machines, nonuniform space complexity, and closure properties
- The complexity of model-checking tail-recursive higher-order fixpoint logic
- Remarks on languages acceptable in log log n space
- Alternating time versus deterministic time: A separation
- A survey of space complexity
- P-RAM vs. RP-RAM
- An NP-complete language accepted in linear time by a one-tape Turing machine
- A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
- Complexity lower bounds for machine computing models
- Complexity problems in real time languages
- The enumerability and invariance of complexity classes
- Minimum-complexity pairing functions
- Space-efficient recognition of sparse self-reducible languages
- Some observations concerning alternating Turing machines using small space
- A machine description and the hierarchy of initial Grzegorczyk classes
- Principal AFL
- Push complexity: optimal bounds and unary inputs
- A characterization of the power of vector machines
- Relativization of questions about log space computability
- Some notes on strong and weak log log n space complexity
- Some remarks on the alternating hierarchy and closure under complement for sublogarithmic space
- A note on first-order spectra with binary relations
- Computing equilibria: a computational complexity perspective
- A quadratic size-hierarchy theorem for small-depth multilinear formulas
- An automaton group with \textsf{PSPACE}-complete word problem
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5636862)
