On the computational power of reversal-bounded machines
- 1 January 1977
- book chapter
- Published by Springer Nature in Lecture Notes in Computer Science
- p. 111-119
- https://doi.org/10.1007/3-540-08342-1_9
Abstract
No abstract availableKeywords
This publication has 11 references indexed in Scilit:
- Visits, crosses, and reversals for nondeterministic off-line machinesInformation and Control, 1978
- Remarks on the complexity of nondeterministic counter languagesTheoretical Computer Science, 1976
- Reversal-Bounded Acceptors and Intersections of Linear LanguagesSIAM Journal on Computing, 1974
- Real-Time Simulation of Multihead Tape UnitsJournal of the ACM, 1972
- Note on tape reversal complexity of languagesInformation and Control, 1970
- Quasi-realtime languagesTheory of Computing Systems, 1970
- An Infinite Hierarchy of Context-Free LanguagesJournal of the ACM, 1969
- Real-Time Definable LanguagesJournal of the ACM, 1967
- Finite-Turn Pushdown AutomataSIAM Journal on Control, 1966
- On the computational complexity of algorithmsTransactions of the American Mathematical Society, 1965