Hostname: page-component-cd9895bd7-gvvz8 Total loading time: 0 Render date: 2024-12-23T01:23:09.037Z Has data issue: false hasContentIssue false
  • English
  • Français

Finite automata, real time processes and counting problems in bounded arithmetics

Published online by Cambridge University Press:  12 March 2014

Mirosław Kutyłowski
Mirosław Kutyłowski*
Affiliation:
Computer Science Institute, University of Wrocław, 51-151 Wrocław, Poland
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we present a negative solution of counting problems for some classes slightly different from bounded arithmetic (Δ 0sets). To get the results we study properties of chains of finite automata.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 53 , Issue 1 , March 1988 , pp. 243 - 258
Copyright
Copyright © Association for Symbolic Logic 1988

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Eilenberg, S., Automata, languages, and machines, vol. B, Academic Press, New York, 1976.Google Scholar
[2] Krohn, K. and Rhodes, J., Algebraic theory of machines, I: Prime decomposition theorem for finite semigroups and machines, Transactions of the American Mathematical Society, vol. 116 (1965), pp. 450–464.Google Scholar
[3] Paris, J., Handley, W., and Wilkie, A., Characterizing some low arithmetic classes, manuscript (received by me in 03 1985).Google Scholar
[4] Paris, J. and Wilkie, A., Counting problems in bounded arithmetic, Methods in mathematical logic ( proceedings, Caracas, 1983 ; Di Prisco, C. A., editor), Lecture Notes in Mathematics, vol. 1130, Springer-Verlag, Berlin, 1985, pp. 317–340.CrossRefGoogle Scholar