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

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

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

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)