A new parallel vector model, with exact characterization of NCk

Kenneth W. Regan

doi:10.1007/3-540-57785-8_149

A new parallel vector model, with exact characterization of NC^k

Kenneth W. Regan

Department of Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

This paper develops a new and natural parallel vector model, and shows that for all k≥1, the languages recognizable in O(log^kn) time and polynomial work in the model are exactly those in NC^k. Some improvements to other simulations in parallel models and reversal complexity are given.

Original language	English
Title of host publication	STACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings
Editors	Patrice Enjalbert, Ernst W. Mayr, Klaus W. Wagner
Publisher	Springer Verlag
Pages	289-300
Number of pages	12
ISBN (Print)	9783540577850
DOIs	https://doi.org/10.1007/3-540-57785-8_149
State	Published - 1994
Event	Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94) - Caen, Fr Duration: Feb 24 1994 → Feb 26 1994

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	775 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94)
City	Caen, Fr
Period	02/24/94 → 02/26/94

Access to Document

10.1007/3-540-57785-8_149

Cite this

Regan, K. W. (1994). A new parallel vector model, with exact characterization of NC^k. In P. Enjalbert, E. W. Mayr, & K. W. Wagner (Eds.), STACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings (pp. 289-300). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 775 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-57785-8_149

Regan, Kenneth W. / A new parallel vector model, with exact characterization of NC^k. STACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. editor / Patrice Enjalbert ; Ernst W. Mayr ; Klaus W. Wagner. Springer Verlag, 1994. pp. 289-300 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f92ac39c9a4f4c90ac8da9b858a8a37f,

title = "A new parallel vector model, with exact characterization of NCk",

abstract = "This paper develops a new and natural parallel vector model, and shows that for all k≥1, the languages recognizable in O(logkn) time and polynomial work in the model are exactly those in NCk. Some improvements to other simulations in parallel models and reversal complexity are given.",

author = "Regan, \{Kenneth W.\}",

note = "Publisher Copyright: {\textcopyright} 1994, Springer Verlag. All rights reserved.; Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94) ; Conference date: 24-02-1994 Through 26-02-1994",

year = "1994",

doi = "10.1007/3-540-57785-8\_149",

language = "English",

isbn = "9783540577850",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "289--300",

editor = "Patrice Enjalbert and Mayr, \{Ernst W.\} and Wagner, \{Klaus W.\}",

booktitle = "STACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",

address = "Germany",

}

Regan, KW 1994, A new parallel vector model, with exact characterization of NC^k. in P Enjalbert, EW Mayr & KW Wagner (eds), STACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 775 LNCS, Springer Verlag, pp. 289-300, Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94), Caen, Fr, 02/24/94. https://doi.org/10.1007/3-540-57785-8_149

A new parallel vector model, with exact characterization of NC^k. / Regan, Kenneth W.
STACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. ed. / Patrice Enjalbert; Ernst W. Mayr; Klaus W. Wagner. Springer Verlag, 1994. p. 289-300 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 775 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - A new parallel vector model, with exact characterization of NCk

AU - Regan, Kenneth W.

PY - 1994

Y1 - 1994

N2 - This paper develops a new and natural parallel vector model, and shows that for all k≥1, the languages recognizable in O(logkn) time and polynomial work in the model are exactly those in NCk. Some improvements to other simulations in parallel models and reversal complexity are given.

AB - This paper develops a new and natural parallel vector model, and shows that for all k≥1, the languages recognizable in O(logkn) time and polynomial work in the model are exactly those in NCk. Some improvements to other simulations in parallel models and reversal complexity are given.

UR - https://www.scopus.com/pages/publications/0003011606

U2 - 10.1007/3-540-57785-8_149

DO - 10.1007/3-540-57785-8_149

M3 - Conference contribution

AN - SCOPUS:0003011606

SN - 9783540577850

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 289

EP - 300

BT - STACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings

A2 - Enjalbert, Patrice

A2 - Mayr, Ernst W.

A2 - Wagner, Klaus W.

PB - Springer Verlag

T2 - Proceedings of the 11th Symposium on Theoretical Aspects of Computer Science (STACS'94)

Y2 - 24 February 1994 through 26 February 1994

ER -

Regan KW. A new parallel vector model, with exact characterization of NC^k. In Enjalbert P, Mayr EW, Wagner KW, editors, STACS 1994 - 11th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings. Springer Verlag. 1994. p. 289-300. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-57785-8_149