article

Free access

On the power of one-way communication

Authors:

Jik H. Chang,

Oscar H. Ibarra,

Anastasios VergisAuthors Info & Claims

Journal of the ACM (JACM), Volume 35, Issue 3

Pages 697 - 726

https://doi.org/10.1145/44483.44493

Published: 01 June 1988 Publication History

PDF eReader

Abstract

In this paper, a very simple model of parallel computation is considered, and the question of how restricting the flow of data to be one way compares with two-way flow is studied. It is shown that the one-way version is surprisingly very powerful in that it can solve problems that seemingly require two-way communication. Whether or not one-way communication is strictly weaker than two-way is an open problem, although the conjecture in this paper is in the positive. It is shown, however, that proving this conjecture is at least as hard as some well-known open problems in complexity theory.

References

[1]

AGGARWAL, A. A comparative study of X-tree, pyramid and related machines. In Proceedings of the 25th Annual IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1984, pp. 89-99.

Google Scholar

[2]

ATALLAH, M., AND KOSARAJU, S. A generalized dictionary machine for VLSI. IEEE Trans. Comput. C-34, 2 (1985), 151-155.

Google Scholar

[3]

CHANDRA, A. K., KOZEN, D. C., AND STOCKMEYER, L.J. Alternation. J. ACM 28, 1 (Jan. 1981), 114-133.

Crossref

Google Scholar

[4]

CHANG, J., CHUNG, M., IBARRA, O., AND RAO, K. Systolic tree implementation of data structures. Tech. Rep. TR 85-32, Dept. of Computer Science, Univ. of Minnesota, Minneapolis, MN, 1985; IEEE Trans. Comput., to appear.

Crossref

Google Scholar

[5]

CHANG, J., IBARRA, O., AND PALIS, M. Efficient simulations of simple models of parallel computation by space-bounded TMs and time-bounded alternating TMs. Revision of Tech. Rep. TR 85- 47, Dept. of Computer Science, Univ. of Minnesota, Minneapolis, MN, 1985.

Google Scholar

[6]

CHOFFRUT, C., AND CULIK, K. II. On real-time cellular automata and trellis automata. Acta Inf. 21 (I984), 393-407.

Crossref

Google Scholar

[7]

COLE, S. Real-time computation by n-dimensional iterative arrays of finite-state machines. IEEE Trans. Comput. C-18, 4 (1969), 349-365.

Google Scholar

[8]

CooK, S. A. Characterizations of pushdown machines in terms of time-bounded computers. J. ACM 18, 1 (Jan. 1971), 4-18.

Crossref

Google Scholar

[9]

CULIK, K., II, AND Yu, S. Iterative tree automata. Theoret. Comput. Sci. 32 (1984), 227-247.

Google Scholar

[10]

CULIK, K., II, IBARRA, O., AND YU, S. Iterative tree arrays with logarithmic depth. Int. J. Comput. Math. 20 (1986), 187-204.

Google Scholar

[11]

DYER, C. One-way bounded cellular automata. Inf. Control 44 (1980), 261-28 I.

Google Scholar

[12]

FREEDMAN, A. R., AND LADNER, R.E. Space bounds for processing contentless inputs. J. Comput. Syst. Sci. 11, 1 (1975), 118-128.

Google Scholar

[13]

HARTMANIS, J., LEWIS, P., AND STEARNS, R. Hierarchies of memory limited computations. In Proceedings of the 6th IEEE Annual Symposium on Switching Circuit Theory and Logical Design. IEEE, New York, 1965, pp. 179-190.

Google Scholar

[14]

HOPCROFT, J., PAUL, W., AND VALIANT, L. On time versus space. J. ACM 24, 2 (Apr. 1977), 332-337.

Crossref

Google Scholar

[15]

HOPCROFT, J., AND ULLMAN, J. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Mass., 1979.

Crossref

Google Scholar

[16]

ISARRA, O.H. A note concerning nondeterministic tape complexities. J. ACM 19, 4 (Oct. 1972), 608-612.

Crossref

Google Scholar

[17]

IBARRA, O., AND JIANG, T. On one-way cellular arrays. SIAM J. Comput. 16 (1987), 1135-1154.

Crossref

Google Scholar

[18]

IBARRA, O., KIM, S., AND PALLS, M. Designing systolic algorithms using sequential machines. IEEE Trans. Comput. C-35, 6 (1986), 531-542.

Crossref

Google Scholar

[19]

IBARRA, O., PALIS, M., AND KIM, S. Some results concerning linear iterative (systolic) arrays. J. Parallel Distrib. Comput. 2 (1985), 182-218.

Google Scholar

[20]

LEISERSON, C. Systolic priority queues. Tech. Rep. CMU-CS-79-115. Dept. of Computer Science, Carnegie Mellon Univ., Pittsburgh, Pa., 1979.

Google Scholar

[21]

OTrMAN, T., ROSENBERG, A., AND STOCKMEYER, L. A dictionary machine (for VLSI). IEEE Trans. Comput. C-31, 9 (1982), 892-897.

Google Scholar

[22]

RuaY, S., AND FISCHER, P. Translational methods and computational complexity. In Proceedings of the 6th IEEE Annual Symposium on Switching Circuit Theory and Logical Design. IEEE, New York, 1965, pp. 173-178.

Google Scholar

[23]

Ruzzo, W. Tree-size bounded alternation. J. Comput. Syst. Sci. 21 (1980), 218-235.

Google Scholar

[24]

Ruzzo, W. On uniform circuit complexity. J. Comput. Syst. Sci. 22 (1981), 365-383.

Google Scholar

[25]

SAVITCH, W. Relationship between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4 (1970), 177-192.

Google Scholar

[26]

SOMANI, A., AND AGGARWAL, V. An efficient unsorted VLSI dictionary machine. IEEE Trans. Comput. C-34, 9 (1985), 841-852.

Crossref

Google Scholar

[27]

UMEO, H., MORITA, K., AND SUGATA, K. Deterministic one-way simulation of two-way real-time cellular automata and its related problems. Inf. Process. Lett. 14 (1982), 158-161.

Google Scholar

Cited By

View all

Kutrib M(2018)Cellular Automata and Language TheoryCellular Automata10.1007/978-1-4939-8700-9_54(513-542)Online publication date: 28-Nov-2018
https://doi.org/10.1007/978-1-4939-8700-9_54
Kutrib M(2015)Complexity of One-Way Cellular AutomataCellular Automata and Discrete Complex Systems10.1007/978-3-319-18812-6_1(3-18)Online publication date: 15-May-2015
https://doi.org/10.1007/978-3-319-18812-6_1
Kutrib M(2012)Non-deterministic cellular automata and languagesInternational Journal of General Systems10.1080/03081079.2012.69589641:6(555-568)Online publication date: Aug-2012
https://doi.org/10.1080/03081079.2012.695896
Show More Cited By

Index Terms

On the power of one-way communication
1. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Operational analysis
2. Theory of computation

Recommendations

Energy efficiency optimization of one-way and two-way DF relaying considering circuit power

In this paper, the energy efficiency (EE) of a decode and forward (DF) relay system is studied, where two sources communicate through a half-duplex relay node in one-way and two-way relaying strategies. Both the circuitry power and the transmission ...
From Two-Way to One-Way Finite State Transducers
LICS '13: Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science

Any two-way finite state automaton is equivalent to some one-way finite state automaton. This well-known result, shown by Rabin and Scott and independently by Shepherd son, states that two-way finite state automata (even non-deterministic) characterize ...
On One-way One-bit O (One)-message Cellular Automata

Cellular automata are one-dimensional arrays of interconnected interacting finite automata, also called cells. Here, we investigate one of the weakest class of cellular automata, namely the class of real-time one-way cellular automata. Additionally, we ...

Reviews

Reviewer: Eric Warren Allender

One of the simplest models for parallel computation is the linear iterative array, which consists of n identical finite state devices connected in a linear array, with two-way communication between adjacent elements. It is easy to see that the class 2LIA of sets accepted by two-way linear iterative arrays is equal to DSPACE( n). The authors of this paper consider restricting this model, allowing only one-way communication (from left to right) between adjacent elements. Surprisingly, the resulting class 1LIA is very powerful. One of the main results of the paper is ATIME( n) ? 9T1LIA ? 9TDSPACE( n), :9F:Y where ATIME( n) denotes the class of sets accepted in linear time on alternating Turing machines. Since NSPACE(:.PC9 :3WzL n) is contained in ATIME( n), it follows that one cannot show that one-way communication is less powerful than two-way communication in this model without first solving the long-standing open question of whether NSPACE(:.PC9 :3WzL n) = DSPACE( n). The paper is a thorough investigation of the 1LIA model. A variety of extensions of the model are also considered. The paper is well written and the results are interesting and surprising. An earlier version of this work was presented in 1986 at the 27th Annual Symposium on Foundations of Computer Science.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 35, Issue 3

July 1988

280 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/44483

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1988

Published in JACM Volume 35, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
971
Total Downloads

Downloads (Last 12 months)131
Downloads (Last 6 weeks)17

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kutrib M(2018)Cellular Automata and Language TheoryCellular Automata10.1007/978-1-4939-8700-9_54(513-542)Online publication date: 28-Nov-2018
https://doi.org/10.1007/978-1-4939-8700-9_54
Kutrib M(2015)Complexity of One-Way Cellular AutomataCellular Automata and Discrete Complex Systems10.1007/978-3-319-18812-6_1(3-18)Online publication date: 15-May-2015
https://doi.org/10.1007/978-3-319-18812-6_1
Kutrib M(2012)Non-deterministic cellular automata and languagesInternational Journal of General Systems10.1080/03081079.2012.69589641:6(555-568)Online publication date: Aug-2012
https://doi.org/10.1080/03081079.2012.695896
Terrier V(2012)Language Recognition by Cellular AutomataHandbook of Natural Computing10.1007/978-3-540-92910-9_4(123-158)Online publication date: 2012
https://doi.org/10.1007/978-3-540-92910-9_4
Kutrib M(2012)Cellular Automata and Language TheoryComputational Complexity10.1007/978-1-4614-1800-9_25(359-381)Online publication date: 2012
https://doi.org/10.1007/978-1-4614-1800-9_25
Mahajan MKrithivasan K(2011)Language classes defined by time-bounded relativised cellular automataRAIRO - Theoretical Informatics and Applications10.1051/ita/199327050403127:5(403-432)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1993270504031
Kutrib M(2009)Cellular Automata and Language TheoryEncyclopedia of Complexity and Systems Science10.1007/978-0-387-30440-3_54(800-823)Online publication date: 2009
https://doi.org/10.1007/978-0-387-30440-3_54
Nishio HMargenstern Mvon Haeseler F(2007)On Algebraic Structure of Neighborhoods of Cellular AutomataFundamenta Informaticae10.5555/2366491.236649778:3(397-416)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.5555/2366491.2366497
Nishio HMargenstern Mvon Haeseler F(2007)On Algebraic Structure of Neighborhoods of Cellular AutomataFundamenta Informaticae10.5555/1366029.136603578:3(397-416)Online publication date: 1-Aug-2007
https://dl.acm.org/doi/10.5555/1366029.1366035
Terrier V(2006)Low complexity classes of multidimensional cellular automataTheoretical Computer Science10.1016/j.tcs.2006.07.061369:1(142-156)Online publication date: 15-Dec-2006
https://dl.acm.org/doi/10.1016/j.tcs.2006.07.061
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Energy efficiency optimization of one-way and two-way DF relaying considering circuit power

From Two-Way to One-Way Finite State Transducers

On One-way One-bit O (One)-message Cellular Automata

Reviews

Access critical reviews of Computing literature here

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations