scientific article; zbMATH DE number 3936518
From MaRDI portal
Publication:3707407
automatacomplexity classescomplexity measuresdeterminism versus nondeterminismformal languageslower boundsreducibilitiesrelativizationsimulationstime versus spaceupper bounds
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Analysis of algorithms and problem complexity (68Q25)
Cited in
(67)- The complexity of combinatorial problems with succinct input representation
- Reversal-bounded nondeterministic multicounter machines and complementation
- Some observations on the connection between counting and recursion
- The problem of space invariance for sequential machines
- On reversal bounded alternating Turing machines
- More complicated questions about maxima and minima, and some closures of NP
- Tradeoffs for language recognition on alternating machines
- Unambiguous computations and locally definable acceptance types
- An NP-complete language accepted in linear time by a one-tape Turing machine
- Iterated stack automata and complexity classes
- A survey of space complexity
- Bounded linear logic: A modular approach to polynomial-time computability
- Unambiguity of circuits
- Language complexity of rotations and Sturmian sequences
- The ancestor width of grammars and languages
- The polynomially exponential time restrained analytical hierarchy
- Classification of the index sets of low \([n]^ p\) and high \([n]^ p\)
- Computational complexity of functions
- The complexity of PDL with interleaving
- Recursion theoretic characterizations of complexity classes of counting functions
- The code problem for traces -- improving the boundaries
- Realtime subshifts
- On the computational complexity of problems related to distinguishability sets
- Descriptional complexity of limited automata
- The power of two-way deterministic checking stack automata
- Sorting, linear time and the satisfiability problem
- Nondeterministic multicounter machines and complementation
- Deterministic Turing machines in the range between real-time and linear-time.
- Data independence of read, write, and control structures in PRAM computations
- Computational aspects of relaxation complexity
- On the descriptional complexity of Watson-Crick automata
- On complexity of grammars related to the safety problem
- A time lower bound for satisfiability
- On the computational capacity of parallel communicating finite automata
- A note on a tree-based 2D indexing
- Limiting characterizations of low level space complexity classes
- scientific article; zbMATH DE number 3864492 (Why is no real title available?)
- Constructions for alternating finite automata∗
- Some modifications of auxiliary pushdown automata
- Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
- REPRESENTATIONS AND CHARACTERIZATIONS OF LANGUAGES IN CHOMSKY HIERARCHY BY MEANS OF INSERTION-DELETION SYSTEMS
- On the equivalence of distributed systems with queries and communication
- On the complexity of graph reconstruction
- On the expressive power of the shuffle operator matched with intersection by regular sets
- SEARCHING ALGORITHMS IMPLEMENTED ON PROBABILISTIC SYSTOLIC ARRAYS
- scientific article; zbMATH DE number 863498 (Why is no real title available?)
- Computational Sample Complexity
- The equivalence of pebbles and sensing heads for finite automata
- Weak parallel machines: a new class of physically feasible parallel machine models
- scientific article; zbMATH DE number 5217263 (Why is no real title available?)
- Non-self-embedding grammars, constant-height pushdown automata, and limited automata
- 1-limited automata: witness languages and techniques
- Limited automata and unary languages
- Linear-time limited automata
- Tree-walking-storage automata
- Complexity of multi-head finite automata: origins and directions
- Once-Marking and Always-Marking 1-Limited Automata
- A note on the relation between polynomial time functionals and Constable's class \(\mathcal K\)
- On quasilinear-time complexity theory
- Effective resolution of singularities
- Deterministic tree-walking-storage automata
- Nondeterminism makes unary 1-limited automata concise
- Forgetting 1-limited automata
- Network topologies for parallel communicating finite automata: token-ring and token-bus
- On the descriptional complexity of literal shuffle
- Boundary sets of regular and context-free languages
- Reversal complexity revisited
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 Q3707407)
