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