Theoretical computer science: computational complexity
From MaRDI portal
Publication:6602263
DOI10.1007/978-3-030-06170-8_2zbMath1547.68253MaRDI QIDQ6602263
Simon Perdrix, Jean-Yves Marion, Sophie Tison, Gilles Dowek, Olivier Bournez, Serge Grigorieff, Rémi Gilleron
Publication date: 11 September 2024
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Quantum algorithms and complexity in the theory of computing (68Q12)
Cites Work
- A note on two problems in connexion with graphs
- A Mathematical Theory of Communication
- From regular expressions to deterministic automata
- On equations for regular languages, finite automata, and sequential networks
- Tree-walking automata cannot be determinized
- The complexity of analog computation
- The equivalence of finite valued transducers (on HDT0L languages) is decidable
- Algorithms for determining relative star height and star height
- Recognizable formal power series on trees
- A new recursion-theoretic characterization of the polytime functions
- Complexity measures for regular expressions
- Light linear logic
- Regular expressions into finite automata
- \(L(A)=L(B)\)? A simplified decidability proof.
- Time bounded random access machines
- Quantum computation by measurement and quantum memory
- `Ideal learning' of natural language: positive results about learning from positive evidence
- Links between probabilistic automata and hidden Markov models: probability distributions, learning models and induction algorithms
- Transition graphs and the star-height of regular events
- Fast multiplication of large numbers
- PAC Learning under Helpful Distributions
- Regular tree languages definable in FO and in FO mod
- Quantum computational networks
- Computational Depth Complexity of Measurement-Based Quantum Computation
- Weak Second‐Order Arithmetic and Finite Automata
- THE ABSTRACT THEORY OF AUTOMATA
- Parity, circuits, and the polynomial-time hierarchy
- Recursive Markov chains, stochastic grammars, and monotone systems of nonlinear equations
- Adding nesting structure to words
- The importance of the P versus NP question
- Clustering by Compression
- The Similarity Metric
- Faster Integer Multiplication
- Visibly pushdown languages
- Quantum verification of matrix products
- Tree-Walking Automata Do Not Recognize All Regular Languages
- Average Case Complete Problems
- Relational queries computable in polynomial time
- An overview of computational complexity
- Alternation
- Rapid solution of problems by quantum computation
- Fast Multiple-Precision Evaluation of Elementary Functions
- Complexity of computations
- Fast Pattern Matching in Strings
- Quantum theory, the Church–Turing principle and the universal quantum computer
- Quantum complexity theory
- Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness
- On finite monoids having only trivial subgroups
- Quantum Walk Algorithm for Element Distinctness
- Quantum Query Complexity of Some Graph Problems
- Classically controlled quantum computation
- A Machine-Independent Theory of the Complexity of Recursive Functions
- Generalized finite automata theory with an application to a decision problem of second-order logic
- The unsolvability of the Equivalence Problem for Λ-Free nondeterministic generalized machines
- On a question of Eggan
- Testing and generating infinite sequences by a finite automaton
- Decidability of Second-Order Theories and Automata on Infinite Trees
- The complexity of theorem-proving procedures
- On n-quantifier induction
- Antichains: A New Algorithm for Checking Universality of Finite Automata
- The HOM Problem is EXPTIME-Complete
- An introduction to Kolmogorov complexity and its applications
- One-unambiguous regular languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Theoretical computer science: computational complexity
