Approximate NFA universality and related problems motivated by information theory

DOI10.1016/J.TCS.2023.114076zbMATH Open1520.68061MaRDI QIDQ6093572FDOQ6093572

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)

Recommendations

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

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)

Cites Work

• Title not available (Why is that?)
• Computational Complexity
• Title not available (Why is that?)
• Computational Complexity
• Formal descriptions of code properties: decidability, complexity, implementation
• Title not available (Why is that?)
• A linear algorithm for the random sampling from regular languages
• Title not available (Why is that?)
• The computational complexity of universality problems for prefixes, suffixes, factors, and subwords of regular languages
• Probability, information theory, and prime number theory
• A class of probability distributions on the integers
• COMPLEXITY, INFORMATION, ENERGY
• Problems on finite automata and the exponential time hypothesis
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• On the determinization blowup for finite automata recognizing equal-length languages
• Embedding rationally independent languages into maximal ones
• Approximate NFA universality motivated by information theory
• Randomized generation of error control codes with automata and transducers

Cited In (3)

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

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)