A polynomial-time algorithm for checking consistency of free-choice signal transition graphs

Javier Esparza

doi:10.1109/CSD.2003.1207700

A polynomial-time algorithm for checking consistency of free-choice signal transition graphs

Javier Esparza

Universität Stuttgart

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

1 Scopus citations

Abstract

Signal transition graphs (STGs) are one of the most popular models for the specification of asynchronous circuits. A STG can be implemented if it admits a so-called consistent and complete binary encoding. Checking this is EXPSPACE-hard for arbitrary STGs, and so a lot of attention has been devoted to the subclass of free-choice STGs, which offers a good compromise between expressive power and analyzability. In the last years, polynomial time synthesis techniques have been developed for free-choice STGs, but they assume that the STG has a consistent binary encoding. The first polynomial algorithm for checking consistency is presented here.

Original language	English
Title of host publication	Proceedings - 3rd International Conference on Application of Concurrency to System Design, ACSD 2003
Editors	Felice Balarin, Ricardo J. Machado, Johan Lilius
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	61-70
Number of pages	10
ISBN (Electronic)	0769518877
DOIs	https://doi.org/10.1109/CSD.2003.1207700
State	Published - 2003
Externally published	Yes
Event	3rd International Conference on Application of Concurrency to System Design, ACSD 2003 - Guimaraes, Portugal Duration: 18 Jun 2003 → 20 Jun 2003

Publication series

Name	Proceedings - International Conference on Application of Concurrency to System Design, ACSD
Volume	2003-January
ISSN (Print)	1550-4808

Conference

Conference	3rd International Conference on Application of Concurrency to System Design, ACSD 2003
Country/Territory	Portugal
City	Guimaraes
Period	18/06/03 → 20/06/03

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

SDG 7 Affordable and Clean Energy

Keywords

Algorithm design and analysis
Asynchronous circuits
Circuit synthesis
Clocks
Computer science
Encoding
Energy consumption
Petri nets
Polynomials
Signal synthesis

Access to Document

10.1109/CSD.2003.1207700

Cite this

Esparza, J. (2003). A polynomial-time algorithm for checking consistency of free-choice signal transition graphs. In F. Balarin, R. J. Machado, & J. Lilius (Eds.), Proceedings - 3rd International Conference on Application of Concurrency to System Design, ACSD 2003 (pp. 61-70). Article 1207700 (Proceedings - International Conference on Application of Concurrency to System Design, ACSD; Vol. 2003-January). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/CSD.2003.1207700

Esparza, Javier. / A polynomial-time algorithm for checking consistency of free-choice signal transition graphs. Proceedings - 3rd International Conference on Application of Concurrency to System Design, ACSD 2003. editor / Felice Balarin ; Ricardo J. Machado ; Johan Lilius. Institute of Electrical and Electronics Engineers Inc., 2003. pp. 61-70 (Proceedings - International Conference on Application of Concurrency to System Design, ACSD).

@inproceedings{d7e417c781474faa872d45c60202da33,

title = "A polynomial-time algorithm for checking consistency of free-choice signal transition graphs",

abstract = "Signal transition graphs (STGs) are one of the most popular models for the specification of asynchronous circuits. A STG can be implemented if it admits a so-called consistent and complete binary encoding. Checking this is EXPSPACE-hard for arbitrary STGs, and so a lot of attention has been devoted to the subclass of free-choice STGs, which offers a good compromise between expressive power and analyzability. In the last years, polynomial time synthesis techniques have been developed for free-choice STGs, but they assume that the STG has a consistent binary encoding. The first polynomial algorithm for checking consistency is presented here.",

keywords = "Algorithm design and analysis, Asynchronous circuits, Circuit synthesis, Clocks, Computer science, Encoding, Energy consumption, Petri nets, Polynomials, Signal synthesis",

author = "Javier Esparza",

note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 3rd International Conference on Application of Concurrency to System Design, ACSD 2003 ; Conference date: 18-06-2003 Through 20-06-2003",

year = "2003",

doi = "10.1109/CSD.2003.1207700",

language = "English",

series = "Proceedings - International Conference on Application of Concurrency to System Design, ACSD",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "61--70",

editor = "Felice Balarin and Machado, \{Ricardo J.\} and Johan Lilius",

booktitle = "Proceedings - 3rd International Conference on Application of Concurrency to System Design, ACSD 2003",

}

Esparza, J 2003, A polynomial-time algorithm for checking consistency of free-choice signal transition graphs. in F Balarin, RJ Machado & J Lilius (eds), Proceedings - 3rd International Conference on Application of Concurrency to System Design, ACSD 2003., 1207700, Proceedings - International Conference on Application of Concurrency to System Design, ACSD, vol. 2003-January, Institute of Electrical and Electronics Engineers Inc., pp. 61-70, 3rd International Conference on Application of Concurrency to System Design, ACSD 2003, Guimaraes, Portugal, 18/06/03. https://doi.org/10.1109/CSD.2003.1207700

A polynomial-time algorithm for checking consistency of free-choice signal transition graphs. / Esparza, Javier.
Proceedings - 3rd International Conference on Application of Concurrency to System Design, ACSD 2003. ed. / Felice Balarin; Ricardo J. Machado; Johan Lilius. Institute of Electrical and Electronics Engineers Inc., 2003. p. 61-70 1207700 (Proceedings - International Conference on Application of Concurrency to System Design, ACSD; Vol. 2003-January).

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

TY - GEN

T1 - A polynomial-time algorithm for checking consistency of free-choice signal transition graphs

AU - Esparza, Javier

PY - 2003

Y1 - 2003

N2 - Signal transition graphs (STGs) are one of the most popular models for the specification of asynchronous circuits. A STG can be implemented if it admits a so-called consistent and complete binary encoding. Checking this is EXPSPACE-hard for arbitrary STGs, and so a lot of attention has been devoted to the subclass of free-choice STGs, which offers a good compromise between expressive power and analyzability. In the last years, polynomial time synthesis techniques have been developed for free-choice STGs, but they assume that the STG has a consistent binary encoding. The first polynomial algorithm for checking consistency is presented here.

AB - Signal transition graphs (STGs) are one of the most popular models for the specification of asynchronous circuits. A STG can be implemented if it admits a so-called consistent and complete binary encoding. Checking this is EXPSPACE-hard for arbitrary STGs, and so a lot of attention has been devoted to the subclass of free-choice STGs, which offers a good compromise between expressive power and analyzability. In the last years, polynomial time synthesis techniques have been developed for free-choice STGs, but they assume that the STG has a consistent binary encoding. The first polynomial algorithm for checking consistency is presented here.

KW - Algorithm design and analysis

KW - Asynchronous circuits

KW - Circuit synthesis

KW - Clocks

KW - Computer science

KW - Encoding

KW - Energy consumption

KW - Petri nets

KW - Polynomials

KW - Signal synthesis

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

U2 - 10.1109/CSD.2003.1207700

DO - 10.1109/CSD.2003.1207700

M3 - Conference contribution

AN - SCOPUS:35048839193

T3 - Proceedings - International Conference on Application of Concurrency to System Design, ACSD

SP - 61

EP - 70

BT - Proceedings - 3rd International Conference on Application of Concurrency to System Design, ACSD 2003

A2 - Balarin, Felice

A2 - Machado, Ricardo J.

A2 - Lilius, Johan

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 3rd International Conference on Application of Concurrency to System Design, ACSD 2003

Y2 - 18 June 2003 through 20 June 2003

ER -

Esparza J. A polynomial-time algorithm for checking consistency of free-choice signal transition graphs. In Balarin F, Machado RJ, Lilius J, editors, Proceedings - 3rd International Conference on Application of Concurrency to System Design, ACSD 2003. Institute of Electrical and Electronics Engineers Inc. 2003. p. 61-70. 1207700. (Proceedings - International Conference on Application of Concurrency to System Design, ACSD). doi: 10.1109/CSD.2003.1207700

A polynomial-time algorithm for checking consistency of free-choice signal transition graphs

Abstract

Publication series

Conference

UN SDGs

Keywords

Access to Document

Other files and links

Fingerprint

Cite this