Cited By
View all- Giuliano J(1970)Writing stack acceptorsProceedings of the 11th Annual Symposium on Switching and Automata Theory (swat 1970)10.1109/SWAT.1970.28(181-193)Online publication date: 28-Oct-1970
Tape- and time-bounded Turing acceptors and AFLs (Extended Abstract)
Pages 92 - 99
Abstract
Complexity classes of formal languages defined by time- and tape-bounded Turing acceptors are studied with the aim of showing sufficient conditions for these classes to be AFLs and to be principal AFLs.
References
[1]
R. Book, "Grammars with time functions", Ph.D. thesis, Harvard University, 1969, Also appears as Mathematical Linguistics and Automatic Translation, Report No. NSF-23, Aiken Computation Laboratory, Harvard University, 1969.
[2]
R. Book and S. Greibach, "Quasi-realtime languages", in Math. Systems Theory, 4 (1970). An extended abstract appears in the Proceedings of the First ACM Symposium on the Theory of Computing, Marina del Rey, California, May, 1969.
[3]
S. Ginsburg and S. Greibach, "Abstract families of languages", Studies in Abstract Families of Languages, Memoir No. 87, Amer. Math. Soc., 1-32 (1969).
[4]
S. Ginsburg and S. Greibach, "Principal AFL", SDC Technical Report, 1969.
[5]
S. Ginsburg, S. Greibach, and J. Hopcroft, "Pre-AFL", Studies in Abstract Families of Languages, Memoir No. 87, Amer. Math. Soc., 41-51(1969).
[6]
S. Ginsburg and J. Hopcroft, "Images of AFL under certain families of homomorphisms", SDC Technical Report, 1969.
[7]
S. Greibach and J. Hopcroft, "Independence of AFL operations", Studies in Abstract Families of Languages, Memoir No. 87,33-40 (1969).
[8]
J. Hartmanis and R. Stearns, "On the computational complexity of algorithms", Trans. Amer. Math. Soc., 117, 285-306 (1965).
[9]
J. Hartmanis and R. Stearns, "Automata-based computational complexity", Information Sciences, 1, 173-184 (1969).
[10]
J. Hopcroft and J. Ullman, "An approach to a unified theory of automata", Bell System Technical Journal, 46, 1763-1829 (1967).
[11]
J. Hopcroft and J. Ullman, Formal Languages and their Relation to Automata, Addison-Wesley 1969.
[12]
J. Hopcroft and J. Ullman, "Some results on tape-bounded Turing machines", J. Assoc. Computing Mach., 16, 168-177 (1969).
[13]
P. M. Lewis, II, R. Stearns, and J. Hartmanis, "Memory bounds for recognition of context-free and context-sensitive languages", 1965 IEEE Conference Record on Switching Circuit Theory and Logical Design.
[14]
A. L. Rosenberg, "Real-time definable languages" J. Assoc. Computing Mach., 14, 645-662 (1967).
[15]
W. Savitch, "Relationships between nondeterministic and deterministic tape complexities", submitted for publication. An extended abstract appears in the Proceedings of the First ACM Symposium on the Theory of Computing, Marina del Rey, California, May, 1969.
[16]
R. Stearns, J. Hartmanis, and P. M. Lewis, II, "Hierarchies of memory limited computations", 1965 IEEE Conference Record on Switching Circuit Theory and Logical Design, 179-190.
[17]
B. Wegbreit, "A generator of context-sensitive languages", J. Computer and System Sciences, 3, 456-462 (1969).
[18]
H. Yamada, "Real-time computation and recursive functions not real-time computable", IEEE Transactions on Electronic Computers, 11, 753-760 (1962).
[19]
P. R. Young, "Toward a theory of enumeration", J. Assoc. Computing Mach., 16, 328-348 (1969).
Index Terms
- Tape- and time-bounded Turing acceptors and AFLs (Extended Abstract)
Recommendations
Time- and tape-bounded turing acceptors and AFLs
Complexity classes of formal languages defined by time- and tape-bounded Turing acceptors are studied. Sufficient conditions for these classes to be AFLs are given. Further, it is shown that a time-bounded nondeterministic Turing acceptor need have only ...
Tape-bounded turing acceptors and principal AFLs
Conditions are given under which the classes of formal languages defined by non-deterministic (deterministic) tape-bounded Turing acceptors will be principal AFLs.
Tape bounds for time-bounded turing machines
Let L be a language recognized by a nondeterministic (single-tape) Turing machine of time complexity T(n)>=n^2. Then L is also recognized by a deterministic (single-tape) Turing machine of tape complexity T^1^/^2(n).
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
May 1970
234 pages
ISBN:9781450374699
DOI:10.1145/800161
Copyright © 1970 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 04 May 1970
Check for updates
Qualifiers
- Article
Acceptance Rates
STOC '70 Paper Acceptance Rate 27 of 70 submissions, 39%;
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Upcoming Conference
STOC '25
- Sponsor:
- sigact
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 349Total Downloads
- Downloads (Last 12 months)38
- Downloads (Last 6 weeks)3
Reflects downloads up to 21 Dec 2024
Other Metrics
Citations
Cited By
View all- Giuliano J(1970)Writing stack acceptorsProceedings of the 11th Annual Symposium on Switching and Automata Theory (swat 1970)10.1109/SWAT.1970.28(181-193)Online publication date: 28-Oct-1970
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in