Complexity of algorithms and computations
From MaRDI portal
Publication:1153141
DOI10.1007/BF01084283zbMath0462.03010OpenAlexW2033546285MaRDI QIDQ1153141
V. L. Matrosov, Sergey S. Marchenkov
Publication date: 1981
Published in: Journal of Soviet Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01084283
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Cites Work
- Classes of recursive functions based on Ackermann's function
- Real time computation
- Relationships between nondeterministic and deterministic tape complexities
- Time-restricted sequence generation
- The reduction of tape reversals for off-line one-tape Turing machines
- The enumerability and invariance of complexity classes
- k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines)
- Zwei-Band Simulation von Turingmaschinen. (Two-tape simulation of Turing machines)
- Complexity problems in real time languages
- Fast multiplication of large numbers
- Tape bounds for time-bounded Turing machines
- Degrees of computational complexity
- Tape-reversal bounded Turing machine computations
- Real-time language recognition by one-dimensional cellular automata
- Über die mehrfache Rekursion
- Extension of an effectively generated class of functions by enumeration
- Theory of Formal Systems. (AM-47)
- Weak Second‐Order Arithmetic and Finite Automata
- Classifications of Recursive Functions by Means of Hierarchies
- Note on the 3‐Recursive Functions
- Classes of Predictably Computable Functions
- Enumeration and the Grzegorczyk Hierarchy
- Program size in restricted programming languages
- On the Time Required to Perform Addition
- On the Computational Complexity of Algorithms
- Classes of computable functions defined by bounds on computation
- Machine Dependence of Degrees of Difficulty
- Iteration of Primitive Recursion
- Two-Tape Simulation of Multitape Turing Machines
- Real-Time Definable Languages
- Turing machines with a schedule to keep
- Some Bounds on the Storage Requirements of Sequential Machines and Turing Machines
- 5-Symbol 8-State and 5-Symbol 6-State Universal Turing Machines
- A Machine-Independent Theory of the Complexity of Recursive Functions
- A Remarkable Class of Mannheim-Curves
- On the Length of Programs for Computing Finite Binary Sequences
- On-Line Turing Machine Computations
- Computational Complexity of One-Tape Turing Machine Computations
- The Solvability of the Halting Problem for 2-State Post Machines
- On the size of machines
- Counter machines and counter languages
- Relations Between Time and Tape Complexities
- The Halting Problem of one State Turing Machines with n‐Dimensional Tape
- On-line turing machine recognition
- Hierarchies of Primitive Recursive Functions
- Two memory bounds for the recognition of primes by automata
- A New Hierarchy of Elementary Functions
- On the Complexity of Undecidable Problems in Automata Theory
- Random Sets in Subrecursive Hierarchies
- [https://portal.mardi4nfdi.de/wiki/Publication:5581622 Eine Bemerkung zum Begriff der zuf�lligen Folge]
- Quasi-realtime languages
- Some Results on Tape-Bounded Turing Machines
- A variant of the Kolmogorov concept of complexity
- [https://portal.mardi4nfdi.de/wiki/Publication:5587565 Klassifikation der Zufallsgesetze nach Komplexit�t und Ordnung]
- Note on tape reversal complexity of languages
- On the Time Required to Perform Multiplication
- Programmkomplexität von berechenbaren Funktionen
- On the Efficiency of Algorithms
- Hierarchies of number-theoretic functions. I
- Complexity oscillations in infinite binary sequences
- Rekursionszahlen und die Grzegorczyk-Hierarchie
- A note on dense and nondense families of complexity classes
- The range of a vector measure with values in a montel space
- On Effective Procedures for Speeding Up Algorithms
- Russian Language Ignored
- THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- The state complexity of Turing machines
- The Equivalence of Different Hierarchies of Elementary Functions
- Hierarchies of number-theoretic functions II
- On restricted turing computability
- An Overview of the Theory of Computational Complexity
- A unified approach to the definition of random sequences
- A classification of the ordinal recursive functions
- Subrecursiveness: Machine-independent notions of computability in restricted time and storage
- One-tape, off-line Turing machine computations
- On the speed of addition and multiplication on one-tape, off-line turing machines
- The definition of random sequences
- A Note Concerning Nondeterministic Tape Complexities
- A Classification of the Recursive Functions
- Computational speed-up by effective operators
- The complexity of theorem-proving procedures
- On size vs. efficiency for programs admitting speed-ups
- A formal theory of inductive inference. Part I
- Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy
- Computational Complexity and the Existence of Complexity Gaps
- Recursive Properties of Abstract Complexity Classes
- Real-Time Simulation of Multihead Tape Units
- A Hierarchy of Primitive Recursive Functions
- Zusammenhang der mehrfachen und transfiniten Rekursionen
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Complexity of algorithms and computations
