Tag #turing machine
39 papers:
STOC-2015-KoppulaLW #bound #memory management #obfuscation- Indistinguishability Obfuscation for Turing Machines with Unbounded Memory (VK, ABL, BW), pp. 419–428.
LICS-CSL-2014-KlinLOT #complexity #constraints #problem- Turing machines with atoms, constraint satisfaction problems, and descriptive complexity (BK, SL, JO, ST), p. 10.
DLT-2013-Freivalds #automaton #finite- Ultrametric Finite Automata and Turing Machines (RF), pp. 1–11.
LATA-2013-ZakS #distance- A Turing Machine Distance Hierarchy (SZ, JS), pp. 570–578.
- LICS-2013-BojanczykKLT
- Turing Machines with Atoms (MB, BK, SL, ST), pp. 183–192.
- LATA-2012-IbarraT #automaton #multi
- Weak Synchronization and Synchronizability of Multitape Pushdown Automata and Turing Machines (OHI, NQT), pp. 337–350.
HILT-2012-Liskov #programming- Keynote presentation: Programming the turing machine (BL), pp. 23–24.
ITiCSE-2011-Goldweber #learning #process- Two kinesthetic learning activities: turing machines and basic computer organization (MG), p. 335.
- LATA-2011-AxelsenG #performance
- A Simple and Efficient Universal Reversible Turing Machine (HBA, RG), pp. 117–128.
- ITiCSE-2008-Garcia-OsorioMJG #automaton #education
- Teaching push-down automata and turing machines (CGO, IMS, JJV, NGP), p. 316.
CIAA-2008-HempelK #persistent- Persistent Computations of Turing Machines (HH, MK), pp. 171–180.
- LATA-2008-Petersen #sorting
- Sorting and Element Distinctness on One-Way Turing Machines (HP), pp. 433–439.
FoSSaCS-2006-OuaknineW #logic #metric #on the- On Metric Temporal Logic and Faulty Turing Machines (JO, JW), pp. 217–230.
ICALP-2005-AsarinC - Noisy Turing Machines (EA, PC), pp. 1031–1042.
- ICALP-2004-DurandMUV
- Ecological Turing Machines (BD, AAM, MU, NKV), pp. 457–468.
- DLT-2002-SasakiIIW #2d #bound #probability
- A Space Lower Bound of Two-Dimensional Probabilistic Turing Machines (YS, KI, AI, YW), pp. 185–196.
- DLT-2001-KudlekR
- A Universal Turing Machine with 3 States and 9 Symbols (MK, YR), pp. 311–318.
- LICS-2001-AsarinB #hybrid
- Perturbed Turing Machines and Hybrid Systems (EA, AB), pp. 269–278.
- DLT-1995-Banik
- Colonies as Systems of Turing Machines Without States (IB), pp. 189–198.
- STOC-1995-CuckerKKLW #on the
- On real Turing machines that toss coins (FC, MK, PK, TL, KW), pp. 335–342.
- ICALP-1993-Yamamoto #bound #nondeterminism #trade-off
- Reversal-Space Trade-offs For Simultaneous Resource-Bounded Nondeterministic Turing Machines (HY), pp. 203–214.
CSL-1992-Aanderaa - A Universal Turing Machine (SA), pp. 1–4.
RTA-1989-Dauchet #linear #simulation- Simulation of Turing Machines by a Left-Linear Rewrite Rule (MD), pp. 109–120.
- ICALP-1988-DietzfelbingerM #complexity #matrix
- The Complexity of Matrix Transposition on One-Tape Off-Line Turing Machines with Output Tape (MD, WM), pp. 188–200.
- STOC-1987-MaassSS
- Two Tapes Are Better than One for Off-Line Turing Machines (WM, GS, ES), pp. 94–100.
- STOC-1986-GalilKS #graph #nondeterminism #on the #simulation
- On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines (ZG, RK, ES), pp. 39–49.
- STOC-1984-Maass #bound #nondeterminism #polynomial
- Quadratic Lower Bounds for Deterministic and Nondeterministic One-Tape Turing Machines (WM), pp. 401–408.
- STOC-1982-InoueTT #2d
- Two-Dimensional Alternating Turing Machines (KI, IT, HT), pp. 37–46.
- STOC-1982-Vitanyi #multi #realtime #simulation
- Real-Time Simulation of Multicounters by Oblivious One-Tape Turing Machines (PMBV), pp. 27–36.
- STOC-1981-Simon #bound #complexity #probability
- Space-Bounded Probabilistic Turing Machine Complexity Classes Are Closed under Complement (JS), pp. 158–167.
- ICALP-1979-MonienS #nondeterminism #on the
- On Eliminating Nondeterminism From Turing Machines Which Use Less Than Logarithmic Worktape Space (BM, IHS), pp. 431–445.
- ICALP-1978-Biskup #metric
- Path Measures of Turing Machine Computations (JB), pp. 90–104.
- ICALP-1977-SavitchV #linear #multi #simulation
- Linear Time Simulation of Multihead Turing Machines with Head-to-Head Jumps (WJS, PMBV), pp. 453–464.
- ICALP-1976-GillS #metric
- Ink, Dirty-Tape Turing Machines, and Quasicomplexity Measures (JG, IS), pp. 285–306.
- ICALP-1974-Weicker #memory management
- Turing Machines with Associative Memory Access (RW), pp. 458–472.
- STOC-1974-Gill #complexity #probability
- Computational Complexity of Probabilistic Turing Machines (JTGI), pp. 91–95.
- ICALP-1972-Monien #automaton #bound
- Relationship between Pushdown Automata and Tape-Bounded Turing Machines (BM), pp. 575–583.
- STOC-1972-JonesS #first-order #similarity
- Turing Machines and the Spectra of First-Order Formulas with Equality (NDJ, ALS), pp. 157–167.
- STOC-1969-Savitch #nondeterminism #simulation
- Deterministic Simulation of Non-Deterministic Turing Machines (WJS), pp. 247–248.
