Computing the optimal IO sequences of a protocol in polynomial time

DOI10.1016/0020-0190(91)90170-MMaRDI QIDQ1183459zbMATH OpenOpenAlexFDO

Authors Wen-Huei Chen, Chuan Yi Tang

Publication date 28 June 1992

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(91)90170-m

zbMATH Keywords

protocolprotocol conformance testingfinite-state machineIO sequence

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Network design and communication in computer systems (68M10)

Recommendations

• On the polynomial IO-complexity
• Optimal Sequencing by Modular Decomposition: Polynomial Algorithms
• The intractability of bounded protocols for on-line sequence transmission over non-FIFO channels
• Fine-grained I/O complexity via reductions: new lower bounds, faster algorithms, and a time hierarchy
• Polynomial time algorithms for some minimum latency problems
• On the IO-complexity and approximation languages
• Link scheduling in polynomial time
• Permuting and batched geometric lower bounds in the I/O model

Cites work

• scientific article; zbMATH DE number 3328721 (Why is no real title available?)
• Faster algorithms for the shortest path problem

Cited in

(4)

• The intractability of bounded protocols for on-line sequence transmission over non-FIFO channels
• Efficient minimization of homogeneous FSMs for fault diagnosis
• A new algorithm for generating UIO sequences
• Synchronization paradigm for protocol testing under multiparty configuration

This page was built for publication: Computing the optimal IO sequences of a protocol in polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1183459)