Complexity of algorithms and computations

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

zbMATH Keywords

Turing machinehierarchiesanalytic classificationreal time computationMarkov algorithm

Mathematics Subject Classification ID

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