Approximate NFA universality and related problems motivated by information theory
From MaRDI portal
Publication:6093572
Formal languages and automata (68Q45) Randomized algorithms (68W20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)
Recommendations
Cites work
- scientific article; zbMATH DE number 1284433 (Why is no real title available?)
- scientific article; zbMATH DE number 1284437 (Why is no real title available?)
- scientific article; zbMATH DE number 1517989 (Why is no real title available?)
- scientific article; zbMATH DE number 941396 (Why is no real title available?)
- A class of probability distributions on the integers
- A linear algorithm for the random sampling from regular languages
- Approximate NFA universality motivated by information theory
- COMPLEXITY, INFORMATION, ENERGY
- Computational Complexity
- Computational Complexity
- Embedding rationally independent languages into maximal ones
- Formal descriptions of code properties: decidability, complexity, implementation
- On the determinization blowup for finite automata recognizing equal-length languages
- Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
- Probability, information theory, and prime number theory
- Problems on finite automata and the exponential time hypothesis
- Randomized generation of error control codes with automata and transducers
- The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages
Cited in
(3)
This page was built for publication: Approximate NFA universality and related problems motivated by information theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6093572)