On Approximating Non-regular Languages by Regular Languages

• Autorzy: Eisman G. , Ravikumar B.
• Języki publikacji: EN

Abstrakty

EN

Approximate computation is a central concept in algorithms and computation theory. Our notion of approximation is that the algorithm performs correctly on most of the inputs. We propose some finite automata models to study the question of how well a finite automaton can approximately recognize a non-regular language. On the one hand, we show that there are natural problems for which a DFA can correctly solve almost all the instances, but not all instances. An example of such a problem is a decision question about the number of digits in the square of a given integer. On the other hand, we show that some languages (such as L_majority = {x ∈(0 + 1)* | x has more 1’s than 0’s }) can’t be approximated by any regular language in a strong sense. We also show that there are problems that are intermediate (between the extremes stated above) in terms of how we well a regular language can approximate it. An example of such a problem is a decision question about the number of digits in the product of two integers. We also present results comparing different models of approximation.

Słowa kluczowe

EN

finite automata; approximation; majority language; squaring

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 125--142
• Opis fizyczny: Bibliogr. 22 poz., wykr.

Twórcy

autor

Eisman G.

autor

Ravikumar B.

• Department of Computer Science, Sonoma State University, Rohnert Park, CA 94128, USA,

Bibliografia

• [1] A.Aho, J.Hopcroft and J.Ullman, Design and Analysis of Computer Algorithms, Addison-Wesley, 1973.
• [2] L.Babai, A random oracle separates PSPACE from the polynomial hierarchy. Information Processing Letters, 26:51-53, 1987.
• [3] A. Baker, Transcendental Number Theory, Cambridge University Press, 1975.
• [4] M. Blum, Universal statistical tests, Proceedings of LATIN '92 Lecture Notes in Computer Science, Volume 583, 71-75, 1992.
• [5] Jin-yi Cai,With Probability One, A Random Oracle Separates PSPACE fromthe Polynomial-Time Hierarchy ACM Symposium on Theory of Computing, 21-29, 1986.
• [6] K.L.Chung, Finite Markov Chains, Springer-Verlag, Inc. 1967.
• [7] B. Cordy and K. Salomaa, On the existence of regular approximations, Theoretical Computer Science 387, 125-135, 2007.
• [8] M.Crochemore and Rytter, Jewels of Stringology,World-Scientific, Inc. 2002.
• [9] P. Flajolet, Ambiguity and transcendence, in Proceedings of the 12th International Colloquium on Automata, Languages and Programming, Springer-Verlag, 179-188, 1985.
• [10] M. Furer, Faster Integer Multiplication Algorithm, SIAM Journal on Computing, 39:3, 979-1005 (2009).
• [11] O. Goldreich, Combinatorial Property Testing (a survey), in RandomizedMethods in Algorithm Design American Mathematical Society, 45-60, 1998.
• [12] D. Hong, J.C. Birget, "Probabilistic approximation of some NP optimization problems by finite-state machines", in Randomization and Approximation Techniques in Computer Science (RANDOM'97), J. Rolim (ed.), Lecture Notes in Computer Science, Vol. 1269, Springer-Verlag, pp. 151-164, 1997.
• [13] J.Hopcroft and J.Ullman, Introduction to Automata, Formal Languages and Theory of Computation, Addison-Wesley, Inc. Reading, MA, 1979.
• [14] M. Kappes and C.M.R. Kintala, Tradeoffs between reliability and conciseness of deterministic finite automata, Journal of Automata, Languages and Combinatorics, 9:281-292, 2004.
• [15] M. Kappes and F. Niener, Succinct representations of languages by DFA with different levels of reliability, Theoretical Computer Science 330, 299-310, 2005.
• [16] A. Kooshesh and B. Ravikumar, Efficient implementation of algorithms for approximate exponentiation, Information Processing Letters, 105: 131-137, 2008.
• [17] R.Motwani and P.Raghavan, Randomized Algorithms, Cambridge University Press, 1996.
• [18] A.R.Meyer andMcCreight, Computationally complex and pesudo-randomzero-one valued functions. Theory of Machines and Computations, Editors: Z.Kohavi and A.Paz, 19-41, Academic Press, 1971.
• [19] S. Muthukrishnan, Data Streams: Algorithms and Applications (unpublished notes), 2003.
• [20] A.Paz, Probabilistic automata, Academic Press, 1971.
• [21] B. Ravikumar, What are the leading 10 digits of 666!666!? A problem in Mathematics of Oz by Clifford Pickover (unpublished manuscript).
• [22] R. E. Wilber, Randomness and the Density of Hard Problems IEEE Conf. on Foundations of Computer Science, 335-342, 1983.