6533b82afe1ef96bd128c072

RESEARCH PRODUCT

Structured Frequency Algorithms

Rūsiņš FreivaldsKaspars BalodisJānis Iraids

subject

CombinatoricsRecursive setComputationComputabilityStructure (category theory)Graph (abstract data type)Continuum (set theory)Rose (topology)Projective planeMathematics

description

B.A. Trakhtenbrot proved that in frequency computability (introduced by G. Rose) it is crucially important whether the frequency exceeds \(\frac{1}{2}\). If it does then only recursive sets are frequency-computable. If the frequency does not exceed \(\frac{1}{2}\) then a continuum of sets is frequency-computable. Similar results for finite automata were proved by E.B. Kinber and H. Austinat et al. We generalize the notion of frequency computability demanding a specific structure for the correct answers. We show that if this structure is described in terms of finite projective planes then even a frequency \(O(\frac{\sqrt{n}}{n})\) ensures recursivity of the computable set. We also show that with overlapping structures this frequency cannot be significantly decreased. We also introduce the notion of graph frequency computation and prove sufficient conditions for a graph \(G\) such that a continuum of sets can be \(G\)-computed.

yearjournalcountryeditionlanguage
2015-01-01
https://doi.org/10.1007/978-3-319-17142-5_6