Article

Free access

Solving the state assignment problem for signal transition graphs

Authors:

L. Lavagno,

C. W. Moon,

R. K. Brayton,

A. L. Sangiovanni-VincentelliAuthors Info & Claims

DAC '92: Proceedings of the 29th ACM/IEEE Design Automation Conference

Pages 568 - 572

Published: 01 July 1992 Publication History

PDF eReader

References

[1]

T.A. Chu. Synthesis of Self-timed VLSI Circuits from Graph-theoretic Speciftcations. PhD thesis, M1T, June 1987.

Google Scholar

[2]

M.A. Kishinevsky, A. Y. Kondratyev, and A. R. Taubin. Formal method for selftimed design, in Proceedings of the European Design Automation Conference, 1991.

Digital Library

Google Scholar

[3]

L. Lavagno, K. Keutzer, and A. Sangiovanni-Vincentelli. Algorithms for synthesis of hazard-free asynchronous circuits, in Proceedings of the DestgnAutomation Conference, June 1991.

Digital Library

Google Scholar

[4]

L. Lavagno, C. W. Moon, R. K. Brayton, and A. Sangiovanni-Vincentelli. A novel framework for solving the state assignment problem for event-based specificataons. Technical Report UCB/ERL M92/19, U.C. Berkeley, 1992.

Google Scholar

[5]

A. Martin. Formal program transformations for VLSI synthesis. In E. W. Dij'kstra, editor, Formal Development of Programs and Proofs, The UT Year of Programming Series. Addison-Wesley, 1990.

Digital Library

Google Scholar

[6]

C. W. Moon, P. R. Stephan, and R. K. Brayton. Synthesis of hazard-free asynchronous circuits from graphical specifications. In Proceedings of the interna. tional Conference on Computer-Aided Design, November 199 i.

Google Scholar

[7]

A. Saldanha, T. V'flla, R. K. Brayton, and A. L. Sangiovanni-V'mcenteIli. A framework for satisfying input and output encoding constraints. In Proceedings of the 28th Design Automation Conference, pages 170-175, June 1991.

Digital Library

Google Scholar

[8]

J. H. Traeey. Internal state assignments for asynchronous sequential machines. IEEE Transactions on Electronic Computers, EC-I 5(4):551-560, August 1966.

Crossref

Google Scholar

[9]

S. H. Unger. Asynchronous Saquantial Switching Circuits. Wiley Interscience, 1969.

Digital Library

Google Scholar

[10]

P. Vanbekbergen. Optimized synthesis of asynchronous control circuits from graph-theoretic specifications. In Proceedings of the International Conference on Computer-Aided Design, pages 184-187, November 1990.

Crossref

Google Scholar

[11]

P. Vanbekbergen, G. Goossens, and H. De Man. A local opumization technique for asynchronous control circuits. In Proceedings of the International Workshop on Logic Synthesis, May 1991.

Google Scholar

[12]

T. Villa. A heuristic incompletely specified finite state machine minimizer. Personal communication, 1985.

Google Scholar

[13]

A. V. Yakovlev and A. Petrov. Petri nets and parallel bus controller design. In International Conference on Application and Theory of Petri Nets, Paris, France, June 1990.

Google Scholar

Cited By

View all

Brunvand ENowick SYun K(1999)Practical advances in asynchronous design and in asynchronous/synchronous interfacesProceedings of the 36th annual ACM/IEEE Design Automation Conference10.1145/309847.309889(104-109)Online publication date: 1-Jun-1999
https://dl.acm.org/doi/10.1145/309847.309889
Nagalla RHellestrand G(1997)A Visual Approach for Asynchronous Circuit SynthesisProceedings of the Tenth International Conference on VLSI Design: VLSI in Multimedia Applications10.5555/523974.834900Online publication date: 4-Jan-1997
https://dl.acm.org/doi/10.5555/523974.834900
Lin KKuo CLin C(1997)Synthesis of Hazard-Free Asynchronous Circuits Based on Characteristic GraphIEEE Transactions on Computers10.1109/12.64429946:11(1246-1263)Online publication date: 1-Nov-1997
https://dl.acm.org/doi/10.1109/12.644299
Show More Cited By

Index Terms

Solving the state assignment problem for signal transition graphs

Recommendations

Channel assignment problem and relaxed 2-distant coloring of graphs
Abstract
Let G be a simple graph. Suppose f is a mapping from V ( G ) to nonnegative integers. If, for any two adjacent vertices u and v of G, | f ( u ) − f ( v ) | ≥ 2, then f is called a 2-distant coloring of G. In this paper, we introduce a ...
A generalized state assignment theory for transformations on signal transition graphs
Special issue: asynchronous circuit design for VLSI signal processing

In this article, we propose a global assignment theory forencoding state graph transformations. A constraint satisfaction framework is proposed that can guaranteenecessary and sufficient conditions for a state graph assignment to result in a transformed ...
Efficient state assignment framework for asynchronous state graphs
ICCD '95: Proceedings of the 1995 International Conference on Computer Design: VLSI in Computers and Processors

This paper presents a new efficient state assignment framework for synthesizing asynchronous state graphs. This framework operates purely at the state graph level and is applicable to a broad class of behaviors. In this paper we focus the framework for ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '92: Proceedings of the 29th ACM/IEEE Design Automation Conference

July 1992

752 pages

ISBN:089791516X

Chairman:
Daniel G. Schweikert
Cadence Design Systems, Inc., San Jose, CA

Publisher

IEEE Computer Society Press

Washington, DC, United States

Publication History

Published: 01 July 1992

Check for updates

Qualifiers

Article

Conference

DAC92

Sponsor:

EDAC
SIGDA
IEEE-CAS
IEEE-CS

DAC92: The 29th ACM/IEEE-CS Design Automation Conference

June 8 - 12, 1992

California, Anaheim, USA

Acceptance Rates

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
339
Total Downloads

Downloads (Last 12 months)56
Downloads (Last 6 weeks)14

Reflects downloads up to 18 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Brunvand ENowick SYun K(1999)Practical advances in asynchronous design and in asynchronous/synchronous interfacesProceedings of the 36th annual ACM/IEEE Design Automation Conference10.1145/309847.309889(104-109)Online publication date: 1-Jun-1999
https://dl.acm.org/doi/10.1145/309847.309889
Nagalla RHellestrand G(1997)A Visual Approach for Asynchronous Circuit SynthesisProceedings of the Tenth International Conference on VLSI Design: VLSI in Multimedia Applications10.5555/523974.834900Online publication date: 4-Jan-1997
https://dl.acm.org/doi/10.5555/523974.834900
Lin KKuo CLin C(1997)Synthesis of Hazard-Free Asynchronous Circuits Based on Characteristic GraphIEEE Transactions on Computers10.1109/12.64429946:11(1246-1263)Online publication date: 1-Nov-1997
https://dl.acm.org/doi/10.1109/12.644299
Tabrizi NLiebelt MEshraghian K(1997)A Tabular Method for Guard Strengthening, Symmetrization, and Operator Reduction for Martin's Asynchronous Design MethodologyIEEE Transactions on Computers10.1109/12.62048746:9(1050-1054)Online publication date: 1-Sep-1997
https://dl.acm.org/doi/10.1109/12.620487
Kolks TVercauteren SLin B(1996)Control Resynthesis for Control-Dominated Asynchronous DesignsProceedings of the 2nd International Symposium on Advanced Research in Asynchronous Circuits and Systems10.5555/785164.785215Online publication date: 18-Mar-1996
https://dl.acm.org/doi/10.5555/785164.785215
Lin Bde Jong GKolks TPreas B(1995)Hierarchical optimization of asynchronous circuitsProceedings of the 32nd annual ACM/IEEE Design Automation Conference10.1145/217474.217616(712-717)Online publication date: 1-Jan-1995
https://dl.acm.org/doi/10.1145/217474.217616
Puri RGu JPaulin P(1994)A divide-and-conquer approach for asynchronous interface synthesisProceedings of the 7th international symposium on High-level synthesis10.5555/254208.254252(118-125)Online publication date: 20-May-1994
https://dl.acm.org/doi/10.5555/254208.254252
Kam TVilla TBrayton RSangiovanni-Vincentelli ALorenzetti M(1994)A fully implicit algorithm for exact state minimizationProceedings of the 31st annual Design Automation Conference10.1145/196244.196615(684-690)Online publication date: 6-Jun-1994
https://dl.acm.org/doi/10.1145/196244.196615
Puri RGu JLorenzetti M(1994)A modular partitioning approach for asynchronous circuit synthesisProceedings of the 31st annual Design Automation Conference10.1145/196244.196278(63-69)Online publication date: 6-Jun-1994
https://dl.acm.org/doi/10.1145/196244.196278
de Jong GLin BLorenzetti M(1994)A communicating Petri net model for the design of concurrent asynchronous modulesProceedings of the 31st annual Design Automation Conference10.1145/196244.196272(49-55)Online publication date: 6-Jun-1994
https://dl.acm.org/doi/10.1145/196244.196272
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.

Cited By

Index Terms

Recommendations

Channel assignment problem and relaxed 2-distant coloring of graphs

A generalized state assignment theory for transformations on signal transition graphs

Efficient state assignment framework for asynchronous state graphs