Patrick C. Fischer
- 1 ATRUBIN, A .J . An iterative one-dimensional real-time multiplier. Paper for Appl. Math., Harvard U., Cambridge, Mass., 1962. (ditto)Google Scholar
- 2 AXT, P. On a subreeursive hierarchy and primitive reeursive degrees. Trans. Amer. Math. Soc. 92 (1959), 85-105.Google ScholarCross Ref
- 3 ----. Enumeration and the Grzegorczyk hierarchy. Z. Math. Logik Grundlagen Math. 9 (1963), 53-65.Google ScholarCross Ref
- 4 BAR-HILLEL, Y. Language and Information. John Wiley, New York, 1964.Google Scholar
- 5 ----, PERLES, M., AND SHAMIR, E. Oil formal properties of simple phase structure grammars. Z. Phonetik, Sprachwiss. Kommunikationsforsch. 14 (1961), 143-172; also reprinted in {4}.Google Scholar
- 6 BECVAR, J. ReaLtime and complexity problems in automata theory. Submitted for publication.Google Scholar
- 7 BLUM. M., A inaehine-htdependent theory of reeursive functions. Doctoral thesis, Massachusetts Institute of Technology, Cambridge, Mass., 1964.Google Scholar
- 8 CHOMSKY, N. On certain formal properties of grammars. Lnform. Contr. 2 (1959), 137-167.Google ScholarCross Ref
- 9 ----. Formal properties of grammars. Hcndbook of Mathematical Psychology, Vol. 2. John Wiley, New York, 1963, 323-418.Google Scholar
- 10 ----. AND SCHUTZENBERGER, M. P . The algebraic theory of eontext-free languages. In Computer Programming and Forreal Systems, North-Holland, Amsterdam, 1963, 118-161.Google Scholar
- 11 CLEAVE, J .P . A hierarchy of primitive reeursive functions. Z. Math. Logik Grunglagen Math. 9 (1963), 331-345.Google ScholarCross Ref
- 12 COLE, S .N . Real-time computation by iterative arrays of finite-state machines. Doctoral thesis, Rep. BL-36, Harvard U., Cambridge, Mass., 1964.Google Scholar
- 13 DAVIS, M. Computability and Unsolvability. McGraw-Hill, New York, 1958.Google Scholar
- 14 EGGAN, L .C . Transition graphs and the star-height of regular events. Mich. Math. J. 10 (1963), 385-397.Google ScholarCross Ref
- 15 ELGOT, C. C., AND MEZEI, J. E. On finite relations defined by generalized automata. IBM J. Res. Develop. 9 (1965), 47-68.Google ScholarDigital Library
- 16 --- AND ROBINSON, A. Random-aceess stored-program machines, an approach to programming languages J. ACM 11 (1964), 365-399. Google ScholarDigital Library
- 17 -- AND RUTLEDGE, J. D. RS-maehines with almost blank tape. J . ACM l l (1964), 313-337. Google ScholarDigital Library
- 18 EVEY, J. The theory and applications of pushdown-store machines. Doctoral thesis, Rep. NSF-1O, Harvard U., Cambridge, Mass., 1963.Google Scholar
- 19 FABIAN, R .J . Hierarchies of general recursive functions and ordinal reeursion. Tech. Rep., Case Institute of Technology, Clevehmd, Ohio, 1964.Google Scholar
- 20 FISCHER, P. C. Theory of provable reeursive functions. Trans. Amer. Math. Soc. 117 (1965), 494-520.Google ScholarCross Ref
- 21 ---- . On computability by certain classes of restricted Turing machines. Prec. Fourth Ann. Symp. Switching Circult Theory and Logical Design, Chicago, 1963, pp. 23-32.Google ScholarDigital Library
- 22 ----. Generation of primes by a one-dimensional real-. time iterative array. J . ACM 12 (1965), 388-394. Google ScholarDigital Library
- 23 ----. On formalisms for Turing machines. J . ACM 12 (1965), 570-580. Google ScholarDigital Library
- 24 ----. AND ROSENBERG, A. L. Further results on nondeterministic n-tape automata. Abstr. 65T-48, Amer. Math. Soc. Notices 12 (1965), 139-140.Google Scholar
- 25 GINSBURG, S. An Introduction to Mathemalical Machine Theory. Addison-Wesley, Reading, Mass., 1962. Google ScholarDigital Library
- 26 ---- AND GREIBACH, S. Deterministic context-free languages. Abstr. 65T-.155, Amer. Math. Soc. Notices 12 (1965), 246.Google Scholar
- 27 ---- AND SPANIER. E .H . Mappings of languages by two-tape devices. Proe. Fifth Ann. Syrup. Switching Circuit Theory and Logical Design, Princeton, 1964, pp. 57-67.Google ScholarDigital Library
- 28 GRZEGORCZYK, A, Solile classes of recursive functions, in Rozprawy Matematcyzne. Warsaw, 1953, pp. 1-45.Google Scholar
- 29 HAINES, L. Generation and recognition of formal languages. Doctoral thesis, Massachusetts Institute of Technology, Cambridge, Mass., 1965.Google Scholar
- 30 HARTMANIS, J., LEWIS, P. M., AND STEARNS, R. E. Classifications of computations by time and memory requirements. Prec. IFIP Int. Congr. Vol. 1, 1965, pp. 31-36.Google Scholar
- 31 ----. AND STEARNS, R. E. On the computational complexity of algorithms. Trans. Amer, Math. Soc. 117 (1965), 285-306.Google ScholarCross Ref
- 32 HENNIE, F. C. Iterative Arrays of Logical Circuits. MIT Press, Cambridge, Mass., 1961.Google ScholarCross Ref
- 33 ----. One-tape off line Turing machine computations. Submitted for publication.Google Scholar
- 34 ---- AND STEARNS, R. E. Two tape simulation of multitape Turing machines. Submitted for publication.Google Scholar
- 35 KLEENE, S. C. Introduction to Metamathematics. Van Nostrand, Princeton, N. J., 1952.Google Scholar
- 36 ----. Representation of events in nerve nets and finite automata. In C. E. Shannon and J. McCarthy (Eds.), Automata Studies, pp. 3-41, Princeton U. Press, Princeton, N. J., 1956.Google ScholarCross Ref
- 37 KREIDER, D. L., aND RITCHIE, R.W. Predictably computable functionals and definition by reeursion. Z. Math. Logik Grundlagen Math. 10 (1964), 65-80.Google ScholarCross Ref
- 38 ---- AND ----. A universal two-way automaton. Submitted for publication.Google Scholar
- 39 KURODA, S.-Y. Classes of languages and linear bounded automata, lnformat. Contr. 7 (1964), 207-223.Google ScholarCross Ref
- 40 LANDWEBER, P.S. Three theorems on phase structure grammars of Type I. Informat. Contr. 6 (1963), 131-137.Google ScholarCross Ref
- 41 LEE, C. Y. Categorizing automata by W-machine programs. J. ACM 8 (1961), 384-399. Google ScholarDigital Library
- 42 McNAUGHTON, R. The theory of automata, a survey. In Advances in Computers, Vol. 2. Academic Press, New York, 1961, 379 421.Google Scholar
- 43 MEYER, A.M. Depth of nesting and the Grzegorczyk hierarchy. Abstr. 622-56, Amer. Math. Soc. Notices 13 (1965), 342.Google Scholar
- 44 MINSKY, M. L. Recursive unsolvability of Post's problem of tag and other topics in theory of Turing machines. Ann. Math. 74 (1961), 437-455.Google ScholarCross Ref
- 45 MOORE, E. F. Sequential Machines: Selected Papers. Addison-Wesley, Reading, Mass., 1964. Google ScholarDigital Library
- 46 MYHILL, J. Linear bounded automata. Wadd Tech. Note 60-165, Wright-Patterson AFB, Ohio, 1960.Google Scholar
- 47 OETTINGER, A. G. Automatic syntactic analysis and the pushdown store. Prec. Syrup. Appl. Math., Voh 12, Amer. Math. See. Providence, R. I., 1961.Google Scholar
- 48 PAPERT, S., AND McNAUGHTON, R. On topological events. Submitted for publication.Google Scholar
- 49 PERLES, M., RABIN, M. O., AND SHAMIR, E. Theory of definite antomata. IEEE Trans. EC-12 (1963), 233-243.Google Scholar
- 50 RABIN, M. O. Real-time computation. Israel J. Math. 1 (1963), 203-211.Google ScholarCross Ref
- 51 ---- AND SCOTT, D. Finite automata and their decision problems. IBM J. Reg. Develop. 3 (1959), 115-125.Google ScholarDigital Library
- 52 RITCHIE, D. M. Complexity classification ef primitive reeursive functions by their machine programs. Abstr. 622-59, Amer. Math. Soc. Notices 13 (1965), 343.Google Scholar
- 53 RITCHIE, R. W. Classes of predictably computable functions. Trans. Amer. Math. Soc. 106 (1963), 139-173.Google ScholarCross Ref
- 54 ROSENBERG, A. L. On n-tape finite-state acceptors. Proe. Fifth Mm. Syrup. Switehitlg Cireuit Theory and Logical Design, Princeton, 1964, pp. 76 -81.Google Scholar
- 55 SCHEINBERG, S. Note on the Boolean properties of contextfree languages. Inform. Contr. 3 (1960), 372-375.Google ScholarCross Ref
- 56 SCHUTZENBERGER, M. P. A remark on finite transducers. Inform,. Contr. 4 (1961), 185-196.Google ScholarCross Ref
- 57 ----. On the definition of a family of automaea. Inform. Contr. 4 (1961), 245-270.Google ScholarCross Ref
- 58 ----. Finite counting automata. Inform. Contr. 5 (1962), 91-107.Google ScholarCross Ref
- 59 ----. Certain elementary families of automata. Proc. Syrup. Mathematical Theory of Automata, Polyteeh. Inst. of Brooklyn, 1962, 139-154.Google Scholar
- 60 ----. On context-tree languages and pushdown automata. Inform, Contr. 6 (1963), 246-264.Google ScholarCross Ref
- 61 SHEPHERDSON, J. C., AND STURGIS, H. E. Computability of recursive functions. J, ACM 10 (1963), 217-255. Google ScholarDigital Library
- 62 SIEGEL, J. Some theorems about Yamada's restricted class of recursive functions. IBM Res. Pap. RC-510, T. J. Watson Iles. Ctr., Yorktown Hts., N. Y., 1961.Google Scholar
- 63 TRAHTENBROT, B, A. Turing computations with logarithmic delay. Algebra i logika 8 (1964), 33-48 (in Russian).Google Scholar
- 64 TURING, A.M. On computable numbers, with an application to the Entscheidlmgsproblem. Pron. Londmt Math. Son., Ser. 2-42, 1936, 230-265.Google Scholar
- 65 WANG, H. A variant to Turing's theory of computing machines. J. ACM 4 (1957), 63-92. Google ScholarDigital Library
- 66 YAMADA, H. Counting by a class of growing automata. Doctoral thesis, U. of Pennsylvania, Philadelphia, Pa., 1960.Google Scholar
- 67 ----. Real-time computation and recursive functions not real-time computable. IRE Trans. EC-11 (1962), 753-760.Google ScholarCross Ref
Index Terms
- Multi-tape and infinite-state automata—a survey
Recommendations
On synchronized multi-tape and multi-head automata
Motivated by applications to verification problems in string manipulating programs, we look at the problem of whether the heads in a multi-tape automaton are synchronized. Given an n-tape pushdown automaton M with a one-way read-only head per tape and a ...
Finite n-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.
Eilenberg, Elgot and Shepherdson showed in 1969, [S. Eilenberg, C.C. Elgot, J.C. Shepherdson, Sets recognized by n-tape automata, Journal of Algebra 13 (1969) 447-464], that a relation on finite words over a finite, non-unary alphabet with p letters is ...
Weak synchronization and synchronizability of multi-tape pushdown automata and turing machines
Given an n-tape automaton M with a one-way read-only head per tape which is delimited by an end marker $ and a nonnegative integer k, we say that M is weakly k-synchronized if for every n-tuple x = (x1,..., xn) that is accepted, there is an accepting ...
Comments