On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F61989100%3A27240%2F08%3A00018951" target="_blank" >RIV/61989100:27240/08:00018951 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

On the Complexity of Consistency and Complete State Coding for Signal Transition Graphs

Original language description

Signal Transition Graphs (STGs) are a popular formalism for the specification of asynchronous circuits. A necessary condition for the implementability of an STG is the existence of a consistent and complete state encoding. For an important subclass of STGs, the marked graph STGs, we show that checking consistency is polynomial, but checking the existence of a complete state coding is co-NP-complete. In fact, co-NP-completeness already holds for acyclic and 1-bounded marked graph STGs and for live and 1-bounded marked graph STGs. We add some relevant results for free-choice, bounded, and general STGs.

Czech name

Konzistentnost a úplné stavové kódování pro signální přechodové grafy

Czech description

Signální přechodové grafy (STG) jsou populárním formalismem pro specifikaci asynchronních obvodů. Nutnou podmínkou pro implementovatelnost daného STG je existence konzistentního a úplného stavového kódování. Pro důležitou podtřídu ST-grafů, tzv. ohodnocených grafů STG (the marked graph STGs), ukazujeme, že ověření konzistetnosti je polynomiální, ale ověření existence úplného stavového kódování je co-NP-úplné. Ve skutečnosti co-NP-úplnost platí již pro acyklické a 1-omezené ohodnocené grafy STG a pro živé a 1-omezené ohodnocené grafy STG. Přidáváme rovněž několik relevantních výsledků pro STG s volným výběrem (free-choice), omezené STG a obecné STG.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

Project

<a href="/en/project/1M0567" target="_blank" >1M0567: Centre for Applied Cybernetics</a><br>

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2008

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Fundamenta Informaticae

ISSN

0169-2968

e-ISSN

—

Volume of the periodical

86

Issue of the periodical within the volume

1

Country of publishing house

NL - THE KINGDOM OF THE NETHERLANDS

Number of pages

27

Pages from-to

—

UT code for WoS article

—

EID of the result in the Scopus database

—