Theoretical computer science: computational complexity

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

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

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
• Complexity measures for regular expressions
• THE ABSTRACT THEORY OF AUTOMATA
• Quantum theory, the Church–Turing principle and the universal quantum computer
• 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
• Quantum Walk Algorithm for Element Distinctness
• 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
• Rapid solution of problems by quantum computation
• An introduction to Kolmogorov complexity and its applications
• Parity, circuits, and the polynomial-time hierarchy
• Fast Pattern Matching in Strings
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Quantum complexity theory
• On finite monoids having only trivial subgroups
• Weak Second‐Order Arithmetic and Finite Automata
• 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
• Quantum Query Complexity of Some Graph Problems
• Computational Depth Complexity of Measurement-Based Quantum Computation
• Average Case Complete Problems
• 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
• On n-quantifier induction
• Tree-Walking Automata Do Not Recognize All Regular Languages
• Tree-walking automata cannot be determinized
• 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
• Recognizable formal power series on trees
• Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness
• Quantum algorithms for the triangle problem
• The importance of the P versus NP question
• \(L(A)=L(B)\)? A simplified decidability proof.
• On a question of Eggan
• Complexity of computations
• The HOM Problem is EXPTIME-Complete
• PAC learning under helpful distributions
• 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?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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)