scientific article

Publication date: 13 August 2009

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Nonnumerical algorithms (68W05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Deciding confluence for a simple class of relational transducer networks, The delay and window size problems in rule-based stream reasoning, Fuzzy languages with infinite range accepted by fuzzy automata: pumping lemma and determinization procedure, Polynomial recognition of cluster algebras of finite type, A new perspective on intermediate algorithms via the Riemann-Hilbert correspondence, Computing Stable Outcomes in Hedonic Games, A temporal logic for asynchronous hyperproperties, Approximately counting locally-optimal structures, Confluent complement: an algorithm for the intersection of face ideals, On the iterative convergence of harmony search algorithm and a proposed modification, Universal map for cellular automata, Existence of solutions of integral equations with asymptotic conditions, Interleaving isotactics -- an equivalence notion on behaviour abstractions, Parametric Church's thesis: synthetic computability without choice, Finite automata capturing winning sequences for all possible variants of the $PQ$ penny flip game, Enumerating solutions to grid-based puzzles with a fixed number of rows, The cut operation in subclasses of convex languages (extended abstract), Polynomial fill-in puzzles or how to make sense of the cook-Levin theorem, Fibonacci numbers, consecutive patterns, and inverse peaks, Using low-density parity-check codes to improve the McEliece cryptosystem, Modeling RNA:DNA hybrids with formal grammars, Operational complexity and pumping lemmas, Two-way deterministic automata with jumping mode, Integer multiplication in time $O(n\log n)$, On the complexity of the cogrowth sequence, Classical and Quantum Counter Automata on Promise Problems, Hugo Hadwiger's influence on geometric dissections with special properties, On the hardnesses of several quantum decoding problems, Retracted: Universal computation is `almost surely' chaotic, Geometry of translations on a Boolean cube, On the complexity of detecting convexity over a box, Model checking and synthesis for branching multi-weighted logics, ``Viral Turing machines, computation from noise and combinatorial hierarchies, On the complexity of deciding whether the distinguishing chromatic number of a graph is at most two, Levels of undecidability in rewriting, Separability by piecewise testable languages is \textsc{PTime}-complete, Achievable complexity-performance tradeoffs in lossy compression, From hidden to visible: a unified framework for transforming behavioral theories into rewrite theories, Scheduling in a dynamic heterogeneous distributed system using estimation error, Intricacies of quantum computational paths, An alternating hierarchy for finite automata, Information-theoretical complexity for the hydrogenic identity $S_N2$ exchange reaction, Solution to Motif Finding Problem in Membranes, Space complexity equivalence of P systems with active membranes and Turing machines, Graph ambiguity, Computational models for networks of tiny artifacts: a survey, Healthcare operation improvement based on simulation of cooperative resource preservation nets for none-consumable resources, The Power of Non-determinism in Higher-Order Implicit Complexity, Evaluating the Impact of Information Distortion on Normalized Compression Distance, GENE ASSEMBLY MODELS AND BOOLEAN CIRCUITS, A Characterisation of NL Using Membrane Systems without Charges and Dissolution, Turing machines and bimachines, Polynomial expressions for non-binomial structures, The Road to Quantum Computational Supremacy, The complexity of debate checking, Computing with SN P systems with I/O mode, Solving a PSPACE-complete problem with cP systems, A return to stochasticity and probability in spiking neural P systems, Least Upper Bounds on the Size of Church-Rosser Diagrams in Term Rewriting and λ-Calculus, The complexities of nonperturbative computations, Refining complexity analyses in planning by exploiting the exponential time hypothesis, Metric estimates and membership complexity for Archimedean amoebae and tropical hypersurfaces, Capacity factors in a point-to-point network, EXPTIME-completeness of thorough refinement on modal transition systems, Pregroup grammars with letter promotions: complexity and context-freeness, On the complexity of computing winning strategies for finite poset games, Metric structures and probabilistic computation, Unbounded-error quantum computation with small space bounds, A linear time algorithm for embedding hypercube into cylinder and torus, Instruction sequence processing operators, Logical and algorithmic properties of stable conditional independence, Combinatorics on partial word correlations, The compound interest in relaxing punctuality, Hyper-Minimization in O(n 2), Enhancement of automata with jumping modes, REMARKS ON TWO NONSTANDARD VERSIONS OF PERIODICITY IN WORDS, A note on accelerated Turing machines, Undecidable properties of flat term rewrite systems, On complete one-way functions, The origins of the halting problem, Embedding ordered sets into distributive lattices, Primitivity of finitely presented monomial algebras., Theory versus practice in annealing-based quantum computing, Unique Normalization for Shallow TRS, The $\Pi^0_2$ -Completeness of Most of the Properties of Rewriting Systems You Care About (and Productivity), Turing Machines with Shortcuts: Efficient Attribute-Based Encryption for Bounded Functions, Difference hierarchies and duality with an application to formal languages, Membrane automata for modeling biomolecular processes, What's decidable about weighted automata?, On the computational complexity of the languages of general symbolic dynamical systems and beta-shifts, A game-semantic model of computation, Varieties, On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls, An automaton-theoretic approach to the representation theory of quantum algebras, Generalized fuzzy automata with semantic computing, Formalization of the computational theory of a Turing complete functional language model, Closure properties of subregular languages under operations, On the (dis)similarities between stationary imprecise and non-stationary precise uncertainty models in algorithmic randomness, Computation with multiple CTCs of fixed length and width, What is the natural abstraction level of an algorithm?, Operations on Permutation Automata, Computational Hardness of Multidimensional Subtraction Games, On the Generalized Membership Problem in Relatively Hyperbolic Groups, The stochastic thermodynamics of computation, A survey of graph burning, If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser, Computing the exact number of periodic orbits for planar flows, Unnamed Item, A survey on observability of Boolean control networks, Polynomial‐time universality and limitations of deep learning, Subclasses of \textsc{Ptime} interpreted by programming languages, Alternating automatic register machines, A sound strategy to compile general recursion into finite depth pattern matching, Computing Stable Outcomes in Symmetric Additively Separable Hedonic Games, Unnamed Item, Energy complexity of computation, The effect of jumping modes on various automata models, Better automata through process algebra, Verification-Led Smart Contracts, Existential and universal width of alternating finite automata, Operational complexity: NFA-to-DFA trade-off, Well-founded coalgebras, revisited, The computational complexity of classical knot recognition, Operational complexity in subregular classes, Structural insights about avoiding transfers in the patient-to-room assignment problem, About the Domino Problem for Subshifts on Groups, Positive Neural Networks in Discrete Time Implement Monotone-Regular Behaviors, An Exponential Separation between Randomized and Deterministic Complexity in the LOCAL Model, Descriptional Complexity of the Forever Operator, Unnamed Item, Encodings of Turing machines in linear logic, Qualitative Numeric Planning: Reductions and Complexity, The monoids of the patience sorting algorithm, On computational complexity of Cremer Julia sets, Physical Computational Complexity and First-order Logic, Recursed Is Not Recursive: A Jarring Result, A PSPACE-complete first-order fragment of computability logic, Unnamed Item, Unnamed Item, Complement for two-way alternating automata, The Complexity of Zero Knowledge, Unnamed Item, On Functions Computed on Trees, Computable analysis with applications to dynamic systems, Deciding the Confusability of Words under Tandem Repeats in Linear Time, Unnamed Item, Unnamed Item, Consistently-detecting monitors, Palindromic Characteristic of Committed Graphs and Some Model Theoretic Properties