Approximate NFA universality and related problems motivated by information theory

DOI10.1016/J.TCS.2023.114076MaRDI QIDQ6093572zbMATH OpenFDO

Authors Stavros Konstantinidis, Mitja Mastnak, Nelma Moreira, Rogério Reis

Publication date 7 September 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2023.114076

zbMATH Keywords

approximationNFA universalityPSPACE-hardnessrandomized algorithm

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45) Randomized algorithms (68W20) Approximation algorithms (68W25)

Recommendations

• Implementation and Application of Automata
• Minimizing nfa's and regular expressions
• Mathematical Foundations of Computer Science 2003
• STACS 2005
• The universal automaton

Cites work

• 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
• 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?)
• 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

(5)

• Deciding unique decodability of bigram counts via finite automata
• On Usefulness of Information: Framework and NFA Case
• On the difference set of two transductions
• Heuristic universality detection over regular expressions specified by systems
• Improved randomized approximation of hard universality and emptiness problems

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)