Theoretical computer science: computational complexity

DOI10.1007/978-3-030-06170-8_2zbMATH Open1547.68253MaRDI QIDQ6602263FDOQ6602263

Authors: Olivier Bournez, Gilles Dowek, Rémi Gilleron, Serge Grigorieff, Jean-Yves Marion, Simon Perdrix, Sophie Tison 

Publication date: 11 September 2024

Recommendations

• scientific article; zbMATH DE number 5217263
• Computability and complexity. Foundations and tools for pursuing scientific applications
• Computational Complexity
• Computational Complexity
• Complexity theory

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Quantum algorithms and complexity in the theory of computing (68Q12) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Machine-Independent Theory of the Complexity of Recursive Functions
• A Mathematical Theory of Communication
• A new recursion-theoretic characterization of the polytime functions
• A note on two problems in connexion with graphs
• Adding nesting structure to words
• Algorithms for determining relative star height and star height
• Alternation
• An introduction to Kolmogorov complexity and its applications
• An overview of computational complexity
• Antichains: A New Algorithm for Checking Universality of Finite Automata
• Average Case Complete Problems
• Classically controlled quantum computation
• Clustering by Compression
• Complexity measures for regular expressions
• Complexity of computations
• Computability and randomness
• Computational Depth Complexity of Measurement-Based Quantum Computation
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Fast Multiple-Precision Evaluation of Elementary Functions
• Fast Pattern Matching in Strings
• Fast multiplication of large numbers
• Faster integer multiplication
• From regular expressions to deterministic automata
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Grammatical inference. Learning automata and grammars.
• Handbook of knowledge representation.
• Kolmogorov complexity in perspective. I: Information theory and randomness
• Light linear logic
• Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms
• On n-quantifier induction
• On a question of Eggan
• On equations for regular languages, finite automata, and sequential networks
• On finite monoids having only trivial subgroups
• One-unambiguous regular languages
• PAC learning under helpful distributions
• Parity, circuits, and the polynomial-time hierarchy
• Quantum Query Complexity of Some Graph Problems
• Quantum Walk Algorithm for Element Distinctness
• Quantum algorithms for the triangle problem
• Quantum complexity theory
• Quantum computation by measurement and quantum memory
• Quantum computational networks
• Quantum theory, the Church–Turing principle and the universal quantum computer
• Quantum verification of matrix products
• Rapid solution of problems by quantum computation
• Recognizable formal power series on trees
• Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
• Regular expressions into finite automata
• Regular tree languages definable in FO and in FO\(_{\mathrm{mod}}\)
• Relational queries computable in polynomial time
• THE ABSTRACT THEORY OF AUTOMATA
• Testing and generating infinite sequences by a finite automaton
• The HOM problem is EXPTIME-complete
• The Similarity Metric
• The complexity of analog computation
• The complexity of theorem-proving procedures
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• The importance of the P versus NP question
• The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
• Time bounded random access machines
• Transition graphs and the star-height of regular events
• Tree-Walking Automata Do Not Recognize All Regular Languages
• Tree-walking automata cannot be determinized
• Visibly pushdown languages
• Weak Second‐Order Arithmetic and Finite Automata
• \(L(A)=L(B)\)? A simplified decidability proof.
• `Ideal learning' of natural language: positive results about learning from positive evidence

This page was built for publication: Theoretical computer science: computational complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6602263)