article

Free access

On Communicating Finite-State Machines

Authors:

Daniel Brand,

Pitro ZafiropuloAuthors Info & Claims

Journal of the ACM (JACM), Volume 30, Issue 2

Pages 323 - 342

https://doi.org/10.1145/322374.322380

Published: 01 April 1983 Publication History

PDF eReader

References

[1]

BARTLETT, K A., SCANTLEBURY, R A, AND WILKINSON, P T A note on reliable full-duplex tran$- mission over half-duplex links Commun, ACM 12, 5 (May 1969), 260-261.

Crossref

Google Scholar

[2]

BOCHMANN, G V Communlcatton protocols and error recovery procedures, ACM Oper. Syst Rev. 9. 3 (July 1975), pp 45-50

Crossref

Google Scholar

[3]

BOCHMANN G V Flmte state description of communicattons protocols. Proc. Computer Network Protocols Symp., L~ege, Belgium, Feb. 1978, pp F3-I-F3-11

Google Scholar

[4]

BOCHMANN, G,V, ANO GESCEI, J. A unified method for specificatton and vertlication of protocols. Proc IFIP 77, AFIPS Press, Arlington, Va, 1977, pp 229-234

Google Scholar

[5]

BOCHMANN, G.V, AND MERLIN, P,On the construction of communication protocols. Pro~. Int. Conf on Computer Commumcat~ons, Oct 1980, pp 371-378

Google Scholar

[6]

BOCHMANN, G.V., AND SUNSHINE, C. Use of formal methods in communication protocol design. IEEE Trans. Commun COM-28, 4 (Apr. 1980), 624-631

Google Scholar

[7]

BRAND, D., AND JOYNER, W.H, JR. Verification of protocols using symbolic execution. Comput. Networks 2, 4/5 (Sept./Oct. 1978), 351-360.

Google Scholar

[8]

BRAND, D., AND ZAFIROPULO, P.Synthesis of protocols for an unlimited number of processes. In Proc. of Trends and Applicanons 1980: Computer Network Protocols, National Bureau of Standards, Gaithersburg, Md., May 1980, pp. 29--40.

Google Scholar

[9]

BRAND, D., AND ZAFIROPULO, P.On communicating fimte-state machines. Tech Pep. RZ 1053, IBM Zurich Research Lab., Rfischlikon, Switzerland, Jan. 1981.

Google Scholar

[10]

CCITT.Recommendauon X 21 (revised), AP VI, No. 55-E, Geneve, Switzerland, 1976.

Google Scholar

[11]

DANTHINE, A, ED Proc Computer Network Protocols Symp, Liege, Belgium, 1978; see also specaal lSSile off computer network protocols, Comput Networks 2, 4/5 (Sept/Oct. 1978)

Google Scholar

[12]

DEvY, M., AND DIAZ, M Multdevel speclficatmn and validation of the control in communication systems. Conf. on Distributed Comput. Syst, Oct 1979, pp. 43-50

Google Scholar

[13]

GOUDA, M.G, AND MANNING, E.G On the modehng, analysis and design of protocols---A special class of software structures Proe. 2nd lnt Conf on Software Engineenng, San Francisco, Calif, Oct. 1976, pp. 256-262

Crossref

Google Scholar

[14]

HAILPERN, B., AND OWICKI, S.Verifying network protocols using temporal logic. In Proc Trends and Applicaoons 198ff Computer Network Protocols, National Bureau of Standards, Gaithersburg, Md., May 1980, pp 18-28.

Google Scholar

[15]

HAJEK, J Automaucally verified data transfer protocols Proc Int Conf on Computer Commumcations, Kyoto, Japan, Sept 1978, pp. 749-756

Google Scholar

[16]

KARP, R M, Arid MILLER, R E Parallel program schemata: A mathemaucal model for parallel computaUon Conf Rec 8th Ann. IEEE S),mp on S~~,achtng and Automata Theory (Oct 1967), IEEE, New York, pp 55-61.

Google Scholar

[17]

MERLIN, P.M.A methodology for the design and Jmplementauon of commumcatmn protocols IEEE Trans Commun. COM.24, 6 (June 1976), 614--621.

Google Scholar

[18]

MERLIN, P.M.Specificatmn and vahdatton of protocols. IEEE Trans Commun. COM-27, 11 (Nov 1979), 1671-1680

Google Scholar

[19]

PETERSON, J LPetn nets Comput. Sum, 9, 3 (Sept. 1977), 223-251

Crossref

Google Scholar

[20]

RUDIN, H, WEST, C H., AND ZAFIROPULO, P Automated protocol validauon. One cram of development Proc Computer Network Protocols Conf., Liege, Belgium, Feb 1978, pp F4-1-F4-6

Google Scholar

[21]

SCHULTZ, G D., RosE, D B., WEST, C H, AND GRAY, J.P. Executable descnpuon and validation of SNA. IEEE Trans. Commun COM-28, 4 (Apr. 1980), 661--667.

Google Scholar

[22]

STENNING,INING, N V.A data transfer protocol Comput Networks 1, 2 (Sept 1976), 99-110

Google Scholar

[23]

SUNSHINE, C.A Commumcaoon Protocol Modebng. Artech House, Dedham, Mass, 1981

Google Scholar

[24]

SYMONS, F I.W Representation, analys~s and verification of commumcatton protocols. Rep. No 7380, Telecom Australia Research Labs, November 1980,

Google Scholar

[25]

WEST, C H.General teclmtque for commumcations protocol vahdauon IBM J. Res. Devel. 22, 4 (July 1978), 393--404.

Google Scholar

[26]

WESt, C H, AND ZArmOI'ULO, P Automated vahdation of a communicauons protocol. The CCITT X21 recommendation IBM J Res Devel 22, 10an. 1978), 60-71

Google Scholar

[27]

YOELI, M., AND BARZILAI, Z.Behavioral descnptmn of commumcatmn switching systems using extended Petn nets. Dtgttal Processes 3 (1977), 307-320.

Google Scholar

[28]

ZAFIROPULO, P. Protocol vahdation by duologue-matrix analys~s IEEE Trans Commun COM-26, 8 (Aug 1978), 1187-1194

Google Scholar

[29]

ZAFIROPULO, P, WEST, C H, RUDIN, H, COWAN, D.D., AND BRAND, D.Towards analyzing and synthesizing protocols IEEE Trans Commun COM-28, 4 (Apr 1980), 651-661

Google Scholar

Cited By

View all

Barbanera FHennicker R(2024)Safe Composition of Systems of Communicating Finite State MachinesElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.414.3414(39-57)Online publication date: 11-Dec-2024
https://doi.org/10.4204/EPTCS.414.3
Di Giusto CLaversa LPeters K(2024)Synchronisability in Mailbox CommunicationElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.412.3412(19-34)Online publication date: 22-Nov-2024
https://doi.org/10.4204/EPTCS.412.3
Spengler S(2024)Reachability and Safety Games under TSO SemanticsElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.409.14409(154-171)Online publication date: 30-Oct-2024
https://doi.org/10.4204/EPTCS.409.14
Show More Cited By

Index Terms

On Communicating Finite-State Machines
1. Networks
  1. Network protocols
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Descriptional complexity of (un)ambiguous finite state machines and pushdown automata
RP'10: Proceedings of the 4th international conference on Reachability problems

Unambiguity and its generalization to quantified ambiguity are important concepts in, e.g., automata and complexity theory. Basically, an unambiguous machine has at most one accepting computation path for each accepted word. While unambiguous pushdown ...
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 ...
State-Identification problems for finite-state transducers
FATES'06/RV'06: Proceedings of the First combined international conference on Formal Approaches to Software Testing and Runtime Verification

A well-established theory exists for testing finite-state machines, in particular Moore and Mealy machines. A fundamental class of problems handled by this theory is state identification: we are given a machine with known state space and transition ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 30, Issue 2

April 1983

157 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322374

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1983

Published in JACM Volume 30, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

876
Total Citations
View Citations
4,992
Total Downloads

Downloads (Last 12 months)598
Downloads (Last 6 weeks)94

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Barbanera FHennicker R(2024)Safe Composition of Systems of Communicating Finite State MachinesElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.414.3414(39-57)Online publication date: 11-Dec-2024
https://doi.org/10.4204/EPTCS.414.3
Di Giusto CLaversa LPeters K(2024)Synchronisability in Mailbox CommunicationElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.412.3412(19-34)Online publication date: 22-Nov-2024
https://doi.org/10.4204/EPTCS.412.3
Spengler S(2024)Reachability and Safety Games under TSO SemanticsElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.409.14409(154-171)Online publication date: 30-Oct-2024
https://doi.org/10.4204/EPTCS.409.14
Wu YYan HWang JNa XWang XZheng J(2024)An Online Monitoring System for In Situ and Real-Time Analyzing of Inclusions within the Molten MetalSensors10.3390/s2409276724:9(2767)Online publication date: 26-Apr-2024
https://doi.org/10.3390/s24092767
Barbanera FDezani-Ciancaglini Mde'Liguoro U(2024)Un-projectable Global Types for Multiparty SessionsProceedings of the 26th International Symposium on Principles and Practice of Declarative Programming10.1145/3678232.3678245(1-13)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1145/3678232.3678245
Peters KYoshida NSobocinski PLago UEsparza J(2024)Separation and Encodability in Mixed Choice Multiparty SessionsProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662085(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662085
Leugering J(2024)TickTockTokens: a minimal building block for event-driven systems2024 Neuro Inspired Computational Elements Conference (NICE)10.1109/NICE61972.2024.10549408(1-8)Online publication date: 23-Apr-2024
https://doi.org/10.1109/NICE61972.2024.10549408
Jordan JStiber M(2024)Graph-based Modeling and Simulation of Emergency Services Communication Systems2024 32nd International Conference on Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS)10.1109/MASCOTS64422.2024.10786343(1-4)Online publication date: 21-Oct-2024
https://doi.org/10.1109/MASCOTS64422.2024.10786343
Criollo Cajamarca LEgas Acosta CTipantuña CCarvajal-Rodriguez JParra C(2024)Finite State Machine of the MQTT-SN Protocol for Its Operation Over IEEE 802.15.4 in Linear TopologiesIEEE Access10.1109/ACCESS.2024.342196212(91678-91714)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3421962
Hong WChen ZZhang YYu HDu YWang J(2024)Verification of message-passing uninterpreted programsScience of Computer Programming10.1016/j.scico.2023.103075234:COnline publication date: 1-May-2024
https://dl.acm.org/doi/10.1016/j.scico.2023.103075
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.

References

Cited By

Index Terms

Recommendations

Descriptional complexity of (un)ambiguous finite state machines and pushdown automata

From Two-Way to One-Way Finite State Transducers

State-Identification problems for finite-state transducers

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