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

The Hoare Logic of Deterministic and Nondeterministic Monadic Recursion Schemes, Computability Models: Algebraic, Topological and Geometric Algorithms, General Decidability Results for Asynchronous Shared-Memory Programs: Higher-Order and Beyond, Reasoning about knowledge and messages in asynchronous multi-agent systems, Supervisory Control of Discrete-Event Systems, A Medida de Informação de Shannon: Entropia, Unnamed Item, Regular model checking revisited, Weak inverse neighborhoods of languages, Parameterised counting in logspace, A more complete analysis of the signal double ratchet algorithm, Variable ansatz applied to spectral operator decomposition in a physical superconducting quantum device, String abstract domains and their combination, Synchronous Boolean finite dynamical systems on directed graphs over XOR functions, Parameterized Complexity of Logic-based Argumentation in Schaefer’s Framework, A characterization of functions over the integers computable in polynomial time using discrete ordinary differential equations, Universality of SN P systems with stochastic application of rules, Non-expansive matrix number systems with bases similar to certain Jordan blocks, Unnamed Item, Hardness of Random Optimization Problems for Boolean Circuits, Low-Degree Polynomials, and Langevin Dynamics, Unnamed Item, Unnamed Item, Unnamed Item, MAGIC NUMBERS FOR SYMMETRIC DIFFERENCE NFAS, Agent-Based Modeling, Mathematical Formalism for, A Unified Method to Decentralized State Detection and Fault Diagnosis/prediction of Discrete-event Systems, Interpolating greedy and reluctant algorithms, Complexity and expressive power of second‐order extended Horn logic, Boundedness of the Domain of Definition is Undecidable for Polynomial ODEs, Fan type condition and characterization of Hamiltonian graphs, Turing Machines Can Be Efficiently Simulated by the General Purpose Analog Computer, On the Computational Power of Affine Automata, An Extension of Complex Role Inclusion Axioms in the Description Logic $\mathcal{SROIQ}$, How Redundant Is Your Universal Computation Device?, On Computable Numbers, Nonuniversality, and the Genuine Power of Parallelism, Computational complexity of some problems involving congruences on algebras, State Complexity of Projected Languages, Note on Reversal of Binary Regular Languages, On the computation of natural observers in discrete-event systems, Kuratowski Algebras Generated by Prefix-, Suffix-, Factor-, and Subword-Free Languages Under Star and Complementation, Square on Deterministic, Alternating, and Boolean Finite Automata, STATE COMPLEXITY OF CONCATENATION AND COMPLEMENTATION, Non-computable Julia sets, Synchronization problems in automata without non-trivial cycles, Tracing compressed curves in triangulated surfaces, The complexity of concatenation on deterministic and alternating finite automata, The complexity of weakly recognizing morphisms, Unnamed Item, ON UNIFORMLY RECURRENT MORPHIC SEQUENCES, Codeword stabilized quantum codes: Algorithm and structure, Vanishing of l²‐cohomology as a computational problem, Square on Ideal, Closed and Free Languages, Prefix-Free Subsets of Regular Languages and Descriptional Complexity, Complement on Free and Ideal Languages, Star-Complement-Star on Prefix-Free Languages, Unnamed Item, From Parallelism to Nonuniversality: An Unconventional Trajectory, Algorithmic Aspects of Combinatorial Discrepancy, Adaptive Bin Packing with Overflow, COMPLEXITY OF THE INFINITARY LAMBEK CALCULUS WITH KLEENE STAR, An Efficient Protocol for Oblivious DFA Evaluation and Applications, Using finite state automata (FSA) for formal modelling of affordances in human-machine cooperative manufacturing systems, Grothendieck-Type Inequalities in Combinatorial Optimization, Lower Bounds for the Graph Homomorphism Problem, Stabhyli, Efficient 3-SAT algorithms in the tile assembly model, On Solving Systems of Diagonal Polynomial Equations Over Finite Fields, Unnamed Item, Computability and Dynamical Systems, On the Complexity of Input/Output Logic, COMPLEXITY IN UNION-FREE REGULAR LANGUAGES, On the complexity of bounded time and precision reachability for piecewise affine systems, Parameterized complexity classes beyond para-NP, On the complexity of determinizing monitors, Nondeterministic complexity of operations on free and convex languages, Sub-propositional Fragments of the Interval Temporal Logic of Allen’s Relations, Polynomial Functors Constrained by Regular Expressions, Fixed points in generalized parallel and sequential dynamical systems induced by a minterm or maxterm Boolean functions, On Effective Convergence of Numerical Solutions for Differential Equations, A full computation-relevant topological dynamics classification of elementary cellular automata, Average-energy games, Machines that perform measurements, Kleene closure and state complexity, Parallelizing time with polynomial circuits, Expander graphs and their applications, Computability of the Julia set. Nonrecurrent critical orbits, Remarks on the Computational Power of Some Restricted Variants of P Systems with Active Membranes, Poly-time computability of the Feigenbaum Julia set, On the State Complexity of Complements, Stars, and Reversals of Regular Languages, Least-violating control strategy synthesis with safety rules, Limited-information control of hybrid systems via reachable set propagation, Resilient synchronization in robust networked multi-agent systems, Learning nonlinear hybrid systems, Mining requirements from closed-loop control models, On the decidability of stability of hybrid systems, Lyapunov analysis of rigid body systems with impacts and friction via sums-of-squares, Hybrid control lyapunov functions for the stabilization of hybridsystems, A toolbox for simulation of hybrid systems in matlab/simulink, Zélus, State estimation for polyhedral hybrid systems and applications to the Godunov scheme, Observer design for a class of piecewise affine hybrid systems, Automated analysis of real-time scheduling using graph games, Reachability analysis of nonlinear systems using conservative polynomialization and non-convex sets, One-shot computation of reachable sets for differential games, Tracking differentiable trajectories across polyhedra boundaries, Flowpipe approximation and clustering in space-time, Bounded model-checking of discrete duration calculus, Optimal CPU allocation to a set of control tasks with soft real--time execution constraints, Safe schedulability of bounded-rate multi-mode systems, Compositional heterogeneous abstraction, Quantitative timed simulation functions and refinement metrics for real-time systems, Formula-free finite abstractions for linear temporal verification of stochastic hybrid systems, Quantitative automata-based controller synthesis for non-autonomous stochastic hybrid systems, Control design for specifications on stochastic hybrid systems, Rewarding probabilistic hybrid automata, Approximating acceptance probabilities of CTMC-paths on multi-clock deterministic timed automata, Specification-guided controller synthesis for linear systems and safe linear-time temporal logic, Temporal logic model predictive control for discrete-time systems, Iterative temporal motion planning for hybrid systems in partially unknown environments, DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET, The axiomatic power of Kolmogorov complexity, On the fairness and complexity of generalized $k$-in-a-row games, Linear automata with translucent letters and linear context-free trace languages, Modal and mixed specifications: key decision problems and their complexities, Two-Way Automata versus Logarithmic Space, A Random Testing Approach Using Pushdown Automata, A study of a generalization of a card problem, Regular path queries under approximate semantics, THE ALLOCATION OF SURPLUS BY MARKETS: A FRAMEWORK FOR ANALYSIS, Small fast universal Turing machines, Cone types and geodesic languages for lamplighter groups and Thompson's group $F$., Exponential Lower Bounds for Polytopes in Combinatorial Optimization, Regular Programming for Quantitative Properties of Data Streams, Computability, noncomputability and undecidability of maximal intervals of IVPs, MAGIC NUMBERS AND TERNARY ALPHABET, Non-regular Maximal Prefix-Free Subsets of Regular Languages, Operations on Unambiguous Finite Automata, FRACTAL STRUCTURE ON k-SAT, Randomness and Computation, On the Formalization of Some Results of Context-Free Language Theory, Size Complexity of Two-Way Finite Automata, Magic Numbers and Ternary Alphabet, Concatenation of Regular Languages and Descriptional Complexity, Computational Complexity in Non-Turing Models of Computation, HYPER-MINIMIZATION IN O(n²), Self-Verifying Finite Automata and Descriptional Complexity, The Complexity of Languages Resulting from the Concatenation Operation, Nondeterministic Complexity of Operations on Closed and Ideal Languages, Kuratowski Algebras Generated by Prefix-Free Languages, Ambiguity of Unary Symmetric Difference NFAs, Polynomial kernels for vertex cover parameterized by small degree modulators, On Khot’s unique games conjecture, Deterministic blow-ups of minimal NFA's, Note on the complexity of Las Vegas automata problems, Games for complexity of second-order call-by-name programs, The 2004 Benjamin Franklin medal in computer and cognitive science presented to Richard M. Karp, Parallel dynamical systems over graphs and related topics: a survey, The stability of the deterministic Skorokhod problem is undecidable, On the boundary of regular languages, Regular expressions for data words, Equivalence classes and conditional hardness in massively parallel computations, Minimal DFA for testing divisibility, Reverse complexity, A note on tolerance graph recognition, The complexity of finding SUBSEQ$(A)$, Some remarks on real numbers induced by first-order spectra, Interval type-2 fuzzy automata and interval type-2 fuzzy grammar, On the expressive power of behavioral profiles, Characterizing polynomial and exponential complexity classes in elementary lambda-calculus, Computing equilibria: a computational complexity perspective, On regular realizability problems for context-free languages, Checking interval properties of computations, A bypassing path based routing algorithm for the pyramid structures, A modal view on resource-bounded propositional logics, Gaussian quantum computation with oracle-decision problems, On the decidability of infix inclusion problem, A consequence of a proof of the one-way function existence for the problem of macroscopic superpositions, Frontiers of tractability for typechecking simple XML transformations, Deciding unique decodability of bigram counts via finite automata, On conditional decomposability, Physical portrayal of computational complexity, Prefix-free languages: left and right quotient and reversal, Light tail asymptotics in multidimensional reflecting processes for queueing networks, Tile invariants: New horizons., Almost periodic sequences., A structural/temporal query language for business processes, $\mathcal P = \mathcal{NP}$?, Efficiently identifying deterministic real-time automata from labeled data, On detectability of labeled Petri nets and finite automata, A study of heuristic guesses for adiabatic quantum computation, An analytic system with a computable hyperbolic sink whose basin of attraction is non-computable, Concatenation of regular languages and descriptional complexity, Reversal of binary regular languages, On a structural property in the state complexity of projected regular languages, Reasoning about actions with loops via Hoare logic, System theory for system identification., A note on algebras of languages, Permutation reconstruction from differences, Jug measuring: algorithms and complexity, Nondeterministic polynomial time factoring in the tile assembly model, Solving NP-complete problems in the tile assembly model, Book review of: S. Arora and B. Barak, Computational complexity: a modern approach., Multiple pattern matching: a Markov chain approach, Succinct representations for (non)deterministic finite automata, Verifying time complexity of Turing machines, Distinguishing two probability ensembles with one sample from each ensemble, Scott sentences for certain groups, Solving systems of diagonal polynomial equations over finite fields, Log-space conjugacy problem in the Grigorchuk group, Multiprocessor schedulability of arbitrary-deadline sporadic tasks: complexity and antichain algorithm, \textsc{Snowman} is $\mathsf{PSPACE}$-complete, On the expressiveness of interaction, First-cycle games, Quantum walks: a comprehensive review, Second-level algorithms, superrecursivity, and recovery problem in distributed systems, Statistical estimation with bounded memory, Self-similar fractals: an algorithmic point of view, A new mapping between combinatorial proofs and sequent calculus proofs read out from logical flow graphs, Producing and verifying extremely large propositional refutations, State complexity of some operations on binary regular languages, Lifting non-finite axiomatizability results to extensions of process algebras, On the algorithmic complexity of static structures, On expressive power of regular realizability problems, On binary circle plus operator $\oplus$-NFAs and succinct descriptions of regular languages, A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy, The efficiency of identifying timed automata and the power of clocks, A context-free and a 1-counter geodesic language for a Baumslag-Solitar group, Does the polynomial hierarchy collapse if onto functions are invertible?, The instability of instability of centered distributions, A fixed-parameter perspective on \#BIS, On deciding stability of multiclass queueing networks under buffer priority scheduling policies, Asymptotic granularity reduction and its application, Finite state complexity, Inverse subsemigroups of finite index in finitely generated inverse semigroups, Decision problems and projection languages for restricted variants of two-dimensional automata, Determinizing monitors for HML with recursion, General decidability results for asynchronous shared-memory programs: higher-order and beyond, On $\tau$-adic representations of integers, Tradeoff lower lounds for stack machines, A formalization of multi-tape Turing machines, Fitness landscape analysis of automated machine learning search spaces, Incompleteness and the halting problem, Boolean circuit programming: A new paradigm to design parallel algorithms, Factorizing RSA keys, an improved analogue solution, A formal model of semantic computing, Computation with finite stochastic chemical reaction networks, Computational bounds on polynomial differential equations, Interactive and probabilistic proof-checking, Detectability of labeled weighted automata over monoids, Succinct representation for (non)deterministic finite automata, Graph-theoretical characterization of invertible cellular automata, Automata equipped with auxiliary data structures and regular realizability problems, The application of hypergroups in symbolic executions and finite automata, The complexity of quantum circuit mapping with fixed parameters, Liouville numbers and the computational complexity of changing bases, On the complexity of conversion between classic real number representations, Efficient enumeration of regular expressions for faster regular expression synthesis, Control of discrete-event systems with partial observations using coalgebra and coinduction, Admissibility of cut in LC with fixed point combinator, Relational semantics for Kleene logic and action logic