IEICE TRANSACTIONS on Information
On the Descriptional Complexity of Iterative Arrays
Summary :
The descriptional complexity of iterative arrays (IAs) is studied. Iterative arrays are a parallel computational model with a sequential processing of the input. It is shown that IAs when compared to deterministic finite automata or pushdown automata may provide savings in size which are not bounded by any recursive function, so-called non-recursive trade-offs. Additional non-recursive trade-offs are proven to exist between IAs working in linear time and IAs working in real time. Furthermore, the descriptional complexity of IAs is compared with cellular automata (CAs) and non-recursive trade-offs are proven between two restricted classes. Finally, it is shown that many decidability questions for IAs are undecidable and not semidecidable.
- Publication
- IEICE TRANSACTIONS on Information Vol.E87-D No.3 pp.721-725
- Publication Date
- 2004/03/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Cellular Automata)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Andreas MALCHER, "On the Descriptional Complexity of Iterative Arrays" in IEICE TRANSACTIONS on Information,
vol. E87-D, no. 3, pp. 721-725, March 2004, doi: .
Abstract: The descriptional complexity of iterative arrays (IAs) is studied. Iterative arrays are a parallel computational model with a sequential processing of the input. It is shown that IAs when compared to deterministic finite automata or pushdown automata may provide savings in size which are not bounded by any recursive function, so-called non-recursive trade-offs. Additional non-recursive trade-offs are proven to exist between IAs working in linear time and IAs working in real time. Furthermore, the descriptional complexity of IAs is compared with cellular automata (CAs) and non-recursive trade-offs are proven between two restricted classes. Finally, it is shown that many decidability questions for IAs are undecidable and not semidecidable.
URL: https://global.ieice.org/en_transactions/information/10.1587/e87-d_3_721/_p
Copy
@ARTICLE{e87-d_3_721,
author={Andreas MALCHER, },
journal={IEICE TRANSACTIONS on Information},
title={On the Descriptional Complexity of Iterative Arrays},
year={2004},
volume={E87-D},
number={3},
pages={721-725},
abstract={The descriptional complexity of iterative arrays (IAs) is studied. Iterative arrays are a parallel computational model with a sequential processing of the input. It is shown that IAs when compared to deterministic finite automata or pushdown automata may provide savings in size which are not bounded by any recursive function, so-called non-recursive trade-offs. Additional non-recursive trade-offs are proven to exist between IAs working in linear time and IAs working in real time. Furthermore, the descriptional complexity of IAs is compared with cellular automata (CAs) and non-recursive trade-offs are proven between two restricted classes. Finally, it is shown that many decidability questions for IAs are undecidable and not semidecidable.},
keywords={},
doi={},
ISSN={},
month={March},}
Copy
TY - JOUR
TI - On the Descriptional Complexity of Iterative Arrays
T2 - IEICE TRANSACTIONS on Information
SP - 721
EP - 725
AU - Andreas MALCHER
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E87-D
IS - 3
JA - IEICE TRANSACTIONS on Information
Y1 - March 2004
AB - The descriptional complexity of iterative arrays (IAs) is studied. Iterative arrays are a parallel computational model with a sequential processing of the input. It is shown that IAs when compared to deterministic finite automata or pushdown automata may provide savings in size which are not bounded by any recursive function, so-called non-recursive trade-offs. Additional non-recursive trade-offs are proven to exist between IAs working in linear time and IAs working in real time. Furthermore, the descriptional complexity of IAs is compared with cellular automata (CAs) and non-recursive trade-offs are proven between two restricted classes. Finally, it is shown that many decidability questions for IAs are undecidable and not semidecidable.
ER -
English
