Two-way multihead automata over a one-letter alphabet
RAIRO. Inform. théor., 14 1 (1980) 67-82
Published online: 2017-02-01
Articles citing this article
The Citing articles tool gives a list of articles citing the current article.
The citing articles come from EDP Sciences database, as well as other publishers participating in CrossRef Cited-by Linking Program. You can set up your personal account to receive an email alert each time this article is cited by a new article (see the menu on the right-hand side of the abstract page).
Cited article:
This article has been cited by the following article(s):
Constant-space, constant-randomness verifiers with arbitrarily small error
M. Utkan Gezer and A.C. Cem SayInformation and Computation 288 104744 (2022)
https://doi.org/10.1016/j.ic.2021.104744
Generalizations of Checking Stack Automata: Characterizations and Hierarchies
Oscar H. Ibarra and Ian McQuillanInternational Journal of Foundations of Computer Science 32 (05) 481 (2021)
https://doi.org/10.1142/S0129054121410045
5′→3′ Watson-Crick pushdown automata
Benedek NagyInformation Sciences 537 452 (2020)
https://doi.org/10.1016/j.ins.2020.06.031
Tight hierarchy of data-independent multi-head automata
Pavol Ďuriš, Rastislav Královič and Dana PardubskáJournal of Computer and System Sciences 114 126 (2020)
https://doi.org/10.1016/j.jcss.2020.06.005
12038 184 (2020)
https://doi.org/10.1007/978-3-030-40608-0_12
Developments in Language Theory
Oscar H. Ibarra and Ian McQuillanLecture Notes in Computer Science, Developments in Language Theory 11088 416 (2018)
https://doi.org/10.1007/978-3-319-98654-8_34
Independent finite automata on Cayley graphs
Ville Salo and Ilkka TörmäNatural Computing 16 (3) 411 (2017)
https://doi.org/10.1007/s11047-017-9613-6
Membrane Computing
Erzsébet Csuhaj-Varjú and György VaszilLecture Notes in Computer Science, Membrane Computing 8340 138 (2014)
https://doi.org/10.1007/978-3-642-54239-8_11
Unconventional Computation and Natural Computation
Erzsébet Csuhaj-Varjú and György VaszilLecture Notes in Computer Science, Unconventional Computation and Natural Computation 7956 55 (2013)
https://doi.org/10.1007/978-3-642-39074-6_7
Implementation and Application of Automata
Daniel Reidenbach and Markus L. SchmidLecture Notes in Computer Science, Implementation and Application of Automata 7381 361 (2012)
https://doi.org/10.1007/978-3-642-31606-7_33
Descriptional Complexity of Formal Systems
Holger PetersenLecture Notes in Computer Science, Descriptional Complexity of Formal Systems 7386 266 (2012)
https://doi.org/10.1007/978-3-642-31623-4_21
SIMULATIONS BY TIME-BOUNDED COUNTER MACHINES
HOLGER PETERSENInternational Journal of Foundations of Computer Science 22 (02) 395 (2011)
https://doi.org/10.1142/S0129054111008106
Complexity of multi-head finite automata: Origins and directions
Markus Holzer, Martin Kutrib and Andreas MalcherTheoretical Computer Science 412 (1-2) 83 (2011)
https://doi.org/10.1016/j.tcs.2010.08.024
644 (2010)
https://doi.org/10.1109/BICTA.2010.5645200
On stateless multihead automata: Hierarchies and the emptiness problem
Oscar H. Ibarra, Juhani Karhumäki and Alexander OkhotinTheoretical Computer Science 411 (3) 581 (2010)
https://doi.org/10.1016/j.tcs.2009.09.001
Developments in Language Theory
Pierluigi Frisco and Oscar H. IbarraLecture Notes in Computer Science, Developments in Language Theory 5583 240 (2009)
https://doi.org/10.1007/978-3-642-02737-6_19
Developments in Language Theory
Holger PetersenLecture Notes in Computer Science, Developments in Language Theory 5583 410 (2009)
https://doi.org/10.1007/978-3-642-02737-6_33
Algorithmic Bioprocesses
Oscar H. Ibarra and Sara WoodworthNatural Computing Series, Algorithmic Bioprocesses 229 (2009)
https://doi.org/10.1007/978-3-540-88869-7_14
LATIN 2008: Theoretical Informatics
Oscar H. Ibarra, Juhani Karhumäki and Alexander OkhotinLecture Notes in Computer Science, LATIN 2008: Theoretical Informatics 4957 94 (2008)
https://doi.org/10.1007/978-3-540-78773-0_9
DNA Computing
Oscar H. Ibarra and Sara WoodworthLecture Notes in Computer Science, DNA Computing 3892 129 (2006)
https://doi.org/10.1007/11753681_10
On membrane hierarchy in P systems
Oscar H. IbarraTheoretical Computer Science 334 (1-3) 115 (2005)
https://doi.org/10.1016/j.tcs.2004.05.007
Mathematical Foundations of Computer Science 2005
Oscar H. IbarraLecture Notes in Computer Science, Mathematical Foundations of Computer Science 2005 3618 39 (2005)
https://doi.org/10.1007/11549345_4
Membrane Computing
Oscar H. IbarraLecture Notes in Computer Science, Membrane Computing 2933 218 (2004)
https://doi.org/10.1007/978-3-540-24619-0_16
150 (2004)
https://doi.org/10.1145/977091.977113
Multi-head finite automata: data-independent versus data-dependent computations
Markus HolzerTheoretical Computer Science 286 (1) 97 (2002)
https://doi.org/10.1016/S0304-3975(01)00237-7
On the Structure of Logspace Probabilistic Complexity Classes
Ioan I. MacarieSIAM Journal on Computing 29 (3) 987 (2000)
https://doi.org/10.1137/S0097539796298339
Mathematical Foundations of Computer Science 1999
Holger PetersenLecture Notes in Computer Science, Mathematical Foundations of Computer Science 1999 1672 241 (1999)
https://doi.org/10.1007/3-540-48340-3_22
Amplification of slight probabilistic advantage at absolutely no cost in space
Ioan I. Macarie and Joel I. SeiferasInformation Processing Letters 72 (3-4) 113 (1999)
https://doi.org/10.1016/S0020-0190(99)00129-5
Automata, Languages and Programming
Pavol ďuriš, Tomasz Jurdziński, Miroslaw Kutyłowski and Krzysztof LoryŚLecture Notes in Computer Science, Automata, Languages and Programming 1443 896 (1998)
https://doi.org/10.1007/BFb0055111
Fundamentals of Computation Theory
Holger PetersenLecture Notes in Computer Science, Fundamentals of Computation Theory 1279 400 (1997)
https://doi.org/10.1007/BFb0036201
150 (1995)
https://doi.org/10.1109/ISTCS.1995.377036
Synchronized finite automata and 2DFA reductions
Oscar H. Ibarra and Nicholas Q. TrânTheoretical Computer Science 115 (2) 261 (1993)
https://doi.org/10.1016/0304-3975(93)90119-E
Automata, Languages and Programming
Oscar H. Ibarra and Nicholas Q. TrânLecture Notes in Computer Science, Automata, Languages and Programming 623 126 (1992)
https://doi.org/10.1007/3-540-55719-9_69
Tradeoffs for language recognition on alternating machines
Juraj HromkovicˇTheoretical Computer Science 63 (2) 203 (1989)
https://doi.org/10.1016/0304-3975(89)90078-9
k+ 1Heads are better than k for PDAs
Marek Chrobak and Ming LiJournal of Computer and System Sciences 37 (2) 144 (1988)
https://doi.org/10.1016/0022-0000(88)90004-9
Alternating multihead finite automata
K.N. KingTheoretical Computer Science 61 (2-3) 149 (1988)
https://doi.org/10.1016/0304-3975(88)90122-3
Cyclic automata
Max GarzonTheoretical Computer Science 53 (2-3) 307 (1987)
https://doi.org/10.1016/0304-3975(87)90071-5
Hierarchies of one-way multihead automata languages
Marek ChrobakTheoretical Computer Science 48 153 (1986)
https://doi.org/10.1016/0304-3975(86)90093-9
Mathematical Foundations of Computer Science 1986
Václav Koubek and Antonín ŘíhaLecture Notes in Computer Science, Mathematical Foundations of Computer Science 1986 233 467 (1986)
https://doi.org/10.1007/BFb0016272
361 (1986)
https://doi.org/10.1109/SFCS.1986.27
Finite automata and unary languages
Marek ChrobakTheoretical Computer Science 47 149 (1986)
https://doi.org/10.1016/0304-3975(86)90142-8
Automata, Languages and Programming
Marek ChrobakLecture Notes in Computer Science, Automata, Languages and Programming 194 101 (1985)
https://doi.org/10.1007/BFb0015735
Automata, Languages and Programming
K. N. KingLecture Notes in Computer Science, Automata, Languages and Programming 115 506 (1981)
https://doi.org/10.1007/3-540-10843-2_40