Improved randomized approximation of hard universality and emptiness problems

MaRDI QIDQ6894352zbMATH OpenFDO

Authors Pantelis Andreou, Stavros Konstantinidis, Taylor J. Smith

Publication date 25 November 2025

Published in Journal of Automata, Languages and Combinatorics (Search for Journal in Brave)

Full work available at URL https://jalc.de/issues/2025/issue_30_1-3/jalc-2025-005-026.php

zbMATH Keywords

approximationDiophantine equationsemptiness problemsnondeterministic finite automatarandomizationtautology testingtwo-dimensional automatauniversality problems

Mathematics Subject Classification ID

Computer solution of Diophantine equations (11Y50) Formal languages and automata (68Q45) Randomized algorithms (68W20) Approximation algorithms (68W25)

Cites work

• A class of probability distributions on the integers
• A statistical anytime algorithm for the halting problem
• A survey of two-dimensional automata theory
• Antichains: A New Algorithm for Checking Universality of Finite Automata
• Approximate NFA universality and related problems motivated by information theory
• Complexity of two-dimensional patterns
• Computational Complexity
• Computational Complexity
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• Mordell's equation: a classical approach
• On the difference set of two transductions
• On the theory of average case complexity
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Probability, information theory, and prime number theory
• Randomized generation of error control codes with automata and transducers
• Rational approximations to the zeta function

This page was built for publication: Improved randomized approximation of hard universality and emptiness problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6894352)