Abstract
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.
K. Balodis—The first author has been supported by the European Social Fund within the project Support for Doctoral Studies at University of Latvia.
R. Freivalds—The research was supported by Co-operation Project “Uzticamas un kontrolētas mobilo ierīču pielietojuma vides izpēte un saistīto ekspertu rīku izveides iespējas” and by Project 271/2012 from the Latvian Council of Science.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ablaev, F., Freivalds, R.: Why sometimes probabilistic algorithms can be more effective. In: Wiedermann, J., Gruska, J., Rovan, B. (eds.) MFCS 1986. LNCS, vol. 233, pp. 1–14. Springer, Heidelberg (1986)
Austinat, H., Diekert, V., Hertrampf, U., Petersen, H.: Regular frequency computations. Theoret. Comput. Sci. 330(1), 15–21 (2005). Insightful Theory
Degtev, A.N.: On \((m, n)\)-computable sets. In: Moldavanskij, D.I. (ed.), Algebraic Systems, pp. 88–99. Ivanovo Gos. Universitet, (1981) (In Russian)
Freivalds, R.: Inductive inference of recursive functions: qualitative theory. In: Barzdins, J., Bjorner, D. (eds.) Baltic Computer Science. LNCS, vol. 502, pp. 77–110. Springer, Heidelberg (1991)
Hall Jr., M.: Combinatorial Theory, 2nd edn. Wiley, New York (1986)
Harizanov, V., Kummer, M., Owings, J.: Frequency computations and the cardinality theorem. J. Symb. Log. 57, 682–687 (1992)
Hinrichs, M., Wechsung, G.: Time bounded frequency computations. In: Proceedings of Twelfth Annual IEEE Conference on Computational Complexity, 1997 (Formerly: Structure in Complexity Theory Conference), pp. 185–192. IEEE (1997)
Kinber, E.B.: Frequency calculations of general recursive predicates and frequency enumerations of sets. Sov. Math. 13, 873–876 (1972)
Kinber, E.B.: Frequency computations in finite automata. Cybern. Sys. Anal. 12(2), 179–187 (1976)
König, D.: Sur les correspondances multivoques des ensembles. Fundamenta Math. 8(1), 114–134 (1926)
McNaughton, R.: The theory of automata, a survey. Adv. Comput. 2, 379–421 (1961)
Rabin, M.O.: Probabilistic automata. Inf. Control 6(3), 230–245 (1963)
Rabin, M.O., Scott, D.: Finite automata and their decision problems. IBM J. Res. Dev. 3(2), 114–125 (1959)
Rose, G.F.: An extended notion of computability. In: International Congress for Logic, Methodology and Philosophy of Science, Stanford, California (1960)
Tantau, T.: Towards a cardinality theorem for finite automata. In: Diks, K., Rytter, W. (eds.) MFCS 2002. LNCS, vol. 2420, pp. 625–636. Springer, Heidelberg (2002)
Trakhtenbrot, B.A.: On the frequency computation of functions. Algebra i Logika 2(1), 25–32 (1964). In Russian
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Balodis, K., Iraids, J., Freivalds, R. (2015). Structured Frequency Algorithms. In: Jain, R., Jain, S., Stephan, F. (eds) Theory and Applications of Models of Computation. TAMC 2015. Lecture Notes in Computer Science(), vol 9076. Springer, Cham. https://doi.org/10.1007/978-3-319-17142-5_6
Download citation
DOI: https://doi.org/10.1007/978-3-319-17142-5_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-17141-8
Online ISBN: 978-3-319-17142-5
eBook Packages: Computer ScienceComputer Science (R0)