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)

zbMATH Keywords

randomized algorithmapproximationPSPACE-hardnessNFA universality

Mathematics Subject Classification ID

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

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

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)

• On the difference set of two transductions
• Deciding unique decodability of bigram counts via finite automata
• On Usefulness of Information: Framework and NFA Case

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)