Proceedings of the 9th Joint International Conference on Information Sciences (JCIS-06)

A study of some easily parallellizable automata

Authors
Sylvie Hamel1
1Department of Computer Science, University of Montreal
Corresponding Author
Sylvie Hamel
Available Online October 2006.
DOI
10.2991/jcis.2006.238How to use a DOI?
Keywords
automata, bit vectors, pattern matching
Abstract

A vector algorithm is an algorithm that applies a bounded number of vector operations to an input vector, regardless of the length of the input. The allowable operations are usually restricted to bit-wise operations available in processors, including shifts and binary addition with carry. This paper study automata for which it is "easy" to derive a vector algorithm to compute the sequence of states visited by the automata on a given input sequence. A special case of these automata, shellable automata, is used in pattern matching problems on biological sequences.

Copyright
© 2006, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the 9th Joint International Conference on Information Sciences (JCIS-06)
Series
Advances in Intelligent Systems Research
Publication Date
October 2006
ISBN
978-90-78677-01-7
ISSN
1951-6851
DOI
10.2991/jcis.2006.238How to use a DOI?
Copyright
© 2006, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

TY  - CONF
AU  - Sylvie Hamel
PY  - 2006/10
DA  - 2006/10
TI  - A study of some easily parallellizable automata
BT  - Proceedings of the 9th Joint International Conference on Information Sciences (JCIS-06)
PB  - Atlantis Press
SP  - 335
EP  - 339
SN  - 1951-6851
UR  - https://doi.org/10.2991/jcis.2006.238
DO  - 10.2991/jcis.2006.238
ID  - Hamel2006/10
ER  -