Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata.

Tomoyuki Yamakami

Published in: FCT (2023)

Keyphrases

finite automata
polynomial size
exponential size
regular expressions
grammatical inference
dnf formulas
boolean functions
hidden markov models
uniform distribution
search space
constraint satisfaction
integrity constraints
computational properties