D 2004

On Extensions of Process Rewrite Systems: Rewrite Systems with Weak Finite-State Unit

KŘETÍNSKÝ, Mojmír, Vojtěch ŘEHÁK and Jan STREJČEK

Basic information

Original name

On Extensions of Process Rewrite Systems: Rewrite Systems with Weak Finite-State Unit

Name in Czech

O rozšířených procesových přepisovacích systémech: Přepisovací systémy se slabou konečně stavovou jednotkou

Authors

KŘETÍNSKÝ, Mojmír (203 Czech Republic, guarantor), Vojtěch ŘEHÁK (203 Czech Republic) and Jan STREJČEK (203 Czech Republic)

Edition

2004. vyd. Amsterdam, The Netherlands, INFINITY'2003: 5th International Workshop on Verification of Infinite-State Systems, p. 75-88, 14 pp. 2004

Publisher

Elsevier Science

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

Netherlands

Confidentiality degree

není předmětem státního či obchodního tajemství

References:

RIV identification code

RIV/00216224:14330/04:00010392

Organization unit

Faculty of Informatics

ISSN

Keywords in English

process rewrite systems; state extension; infinite-state; decidability; reachability

Tags

Tags

International impact, Reviewed
Změněno: 23/6/2009 17:11, prof. RNDr. Jan Strejček, Ph.D.

Abstract

ORIG CZ

V originále

Various classes of infinite-state processes are often specified by rewrite systems. We extend Mayr's Process Rewrite Systems (PRS) by finite-state unit whose transition function satisfies some restrictions inspired by weak finite automata. We classify these models by their expressiveness and show how the hierarchy of new classes (w.r.t.~bisimilarity) is related to both PRS hierarchy of Mayr and two other hierarchies of PRS extensions.

In Czech

Rozšiřujeme Mayrovy přepisovací systémy o konečně stavovou jednotku, jejíž přechodová funkce podléhá restrikcím inspirovaným teorií slabých konečných automatů. Klasifikujeme třídy podle jejich výjadřovací síly vzhledem k silné bisimulaci a dokazujeme vztahy mezi nimi navzájem, vzhledem k dříve definovaným rozšířením i k třídám nerozšířených procesových přepisovacích systémů.

Links

GA201/03/1161, research and development project
Name: Verifikace nekonečně stavových systémů
Investor: Czech Science Foundation, Verification of infinite-state systems
MSM 143300001, plan (intention)
Name: Nesekvenční modely výpočtů - kvantové a souběžné distribuované modely výpočetních procesů
Investor: Ministry of Education, Youth and Sports of the CR, Non-sequential Models of Computing -- Quantum and Concurrent Distributed Models of Computing