Highly undecidable questions for process algebras

被引：0
|
作者：
Jancar, P [1 ]
Srba, J [1 ]
机构：
[1] Tech Univ Ostrava, Dept Comp Sci, CS-70833 Ostrava, Czech Republic
来源：
EXPLORING NEW FRONTIERS OF THEORETICAL INFORMATICS | 2004年 / 155卷
关键词：
weak bisimilarity; simulation; trace preorder; high undecidability;
D O I：
暂无
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We show Sigma(1)(1)-completeness of weak bisimilarity for PA (process algebra), and of weak simulation preorder/equivalence for PDA (pushdown automata), PA and PN (Petri nets). We also show Pi(1)(1) -hardness of weak w-trace equivalence for the (sub)classes BPA (basic process algebra) and BPP (basic parallel processes).
引用
收藏
页码：507 / 520
页数：14
相关论文
共 19 条
  • [1] An Analyzer for Extended Compositional Process Algebras
    Liu, Yang
    Sun, Jun
    Dong, Jin Song
    ICSE'08 PROCEEDINGS OF THE THIRTIETH INTERNATIONAL CONFERENCE ON SOFTWARE ENGINEERING, 2008, : 919 - 920
  • [2] In search of lost time: Axiomatising parallel composition in process algebras
    Aceto, Luca
    Anastasiadi, Elli
    Castiglioni, Valentina
    Ingolfsdottir, Anna
    Luttik, Bas
    2021 36TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2021,
  • [3] Modeling nanoparticle uptake and intracellular distribution using stochastic process algebras
    Dobay, M. P. D.
    Alberola, A. Piera
    Mendoza, E. R.
    Raedler, J. O.
    JOURNAL OF NANOPARTICLE RESEARCH, 2012, 14 (04)
  • [4] OPTIMISATION OF FORMING PROCESS FOR HIGHLY DRAPEABLE FABRICS
    Chen, Shuai
    Harper, Lee T.
    Endruweit, Andreas
    Warrior, Nicholas A.
    20TH INTERNATIONAL CONFERENCE ON COMPOSITE MATERIALS, 2015,
  • [5] Selection criteria of mesh size and time step in FEM analysis of highly nonlinear unsaturated seepage process
    Li, Xu
    Li, Xiaokang
    Wu, Yongkang
    Wu, Lizhou
    Yue, Zurun
    COMPUTERS AND GEOTECHNICS, 2022, 146
  • [6] Explicit dynamic finite element analysis of an automated grasping process using highly damped compliant fingers
    Lee, Kok-Meng
    Liu, Chih-Hsing
    COMPUTERS & MATHEMATICS WITH APPLICATIONS, 2012, 64 (05) : 965 - 977
  • [7] Novel fabrication process for sub-micron interdigitated electrode arrays for highly sensitive electrochemical detection
    Partel, S.
    Kasemann, S.
    Choleva, P.
    Dincer, C.
    Kieninger, J.
    Urban, G. A.
    SENSORS AND ACTUATORS B-CHEMICAL, 2014, 205 : 193 - 198
  • [8] Team training in obstetric and neonatal emergencies using highly realistic simulation in Mexico: impact on process indicators
    Dilys Walker
    Susanna Cohen
    Jimena Fritz
    Marisela Olvera
    Hector Lamadrid-Figueroa
    Jessica Greenberg Cowan
    Dolores Gonzalez Hernandez
    Julia C Dettinger
    Jenifer O Fahey
    BMC Pregnancy and Childbirth, 14
  • [9] Team training in obstetric and neonatal emergencies using highly realistic simulation in Mexico: impact on process indicators
    Walker, Dilys
    Cohen, Susanna
    Fritz, Jimena
    Olvera, Marisela
    Lamadrid-Figueroa, Hector
    Cowan, Jessica Greenberg
    Gonzalez Hernandez, Dolores
    Dettinger, Julia C.
    Fahey, Jenifer O.
    BMC PREGNANCY AND CHILDBIRTH, 2014, 14
  • [10] New feed system for water-insoluble organic and/or highly concentrated wastewaters in the supercritical water oxidation process
    Vadillo, V.
    Garcia-Jarana, M. B.
    Sanchez-Oneto, J.
    Portela, J. R.
    Martinez de la Ossa, E. J.
    JOURNAL OF SUPERCRITICAL FLUIDS, 2012, 72 : 263 - 269
12