Name
Abstract | ||
|---|---|---|
B. A. Trakhtenbrot proved that in frequency computability (introduced by G. Rose) it is crucially important whether the frequency exceeds 1/2. If it does then only recursive sets are frequency-computable. If the frequency does not exceed 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(root 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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-17142-5_6 | Lecture Notes in Computer Science |
Field | DocType | Volume |
Graph,Discrete mathematics,Combinatorics,Overlapping structures,Computer science,Computability,Finite-state machine,Projective plane,Recursion,Computation | Conference | 9076 |
ISSN | Citations | PageRank |
0302-9743 | 1 | 0.37 |
References | Authors | |
6 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kaspars Balodis | 1 | 17 | 6.03 |
| Janis Iraids | 2 | 18 | 6.14 |
| Rusins Freivalds | 3 | 781 | 90.68 |