Filters
Strong Bisimilarity on Basic Parallel Processes is PSPACE-complete
of deciding bisimulation equivalence on BPP is in PSPACE. Combining with the PSPACE-hardness result by Srba, PSPACE-completeness is thus established....
BD - Teorie informace
- 2003 •
- D
Rok uplatnění
D - Stať ve sborníku
Strong Bisimilarity and Regularity of Basic Parallel Processes is PSPACE-Hard
We show that the problem of checking whether two processes definable in the syntax of Basic Parallel Processes (BPP) are strongly bisimilar is PSPACE-hard. We also demonstrate that there is a polynomial time reduction from the strong of BPP....
BD - Teorie informace
- 2002 •
- D
Rok uplatnění
D - Stať ve sborníku
P systems with proteins on membranes characterize PSPACE
characterize by their polynomial time-bounded computations the class PSPACE...
IN - Informatika
- 2013 •
- Jx
Rok uplatnění
Jx - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
Some Problems Related to Bisimilarity on BPP
such bisimilarity problems. Moreover is here shown that deciding regularity of a BPP is PSPACE-complete. So far this problem was only known to be PSPACE-hard....
JC - Počítačový hardware a software
- 2004 •
- D
Rok uplatnění
D - Stať ve sborníku
Bisimilarity of One-Counter Processes Is PSPACE-Complete
A one-counter automaton is a pushdown automaton over a singleton stack alphabet. We prove that the bisimilarity of processes generated by nondeterministic one-counter automata (with no e-steps) is in PSPACE. This improves the previously know...
IN - Informatika
- 2010 •
- D
Rok uplatnění
D - Stať ve sborníku
P systems with active membranes characterize PSPACE
of decisional problems PSPACE. Similar results were achieved also with other models of bio-inspired computers, such as DNA computing. Together they suggest that PSPACE naturally......
IN - Informatika
- 2006 •
- D
Rok uplatnění
D - Stať ve sborníku
Π P 2 vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
The Quantified Constraint Satisfaction Problem is the problem of evaluating a sentence with both quantifiers, over relations from some constraint language, with conjunction as the only connective. We show that for any constraint language on a finite ...
Pure mathematics
- 2024 •
- D •
- Link
Rok uplatnění
D - Stať ve sborníku
Výsledek na webu
Strong Bisimilarity and Regularity of Basic Process Algebra is PSPACE-Hard
Strong bisimilarity and regularity checking problems of Basic Process Algebra (BPA) are decidable, with the complexity upper bounds 2-EXPTIME. On the other hand, no lower bounds were known. In this paper we demonstrate PSPACE-hardness of the...
BD - Teorie informace
- 2002 •
- D
Rok uplatnění
D - Stať ve sborníku
Complexity of detectability, opacity and A-diagnosability for modular discrete event systems
for monolithic systems is PSPACE-complete, the complexity for modular systems is unknown. We the upper bound is a natural modification of the PSPACE algorithms for monolithic discuss a case where the complexity drops to PSPACE<...
Pure mathematics
- 2019 •
- Jimp •
- Link
Rok uplatnění
Jimp - Článek v periodiku v databázi Web of Science
Výsledek na webu
Deciding Universality of ptNFAs is PSpace-Complete
and partially ordered NFAs is PSpace-complete. For ptNFAs, the complexity drops to coNP a novel and nontrivial construction, that the problem is PSpace-complete......
Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
- 2018 •
- D •
- Link
Rok uplatnění
D - Stať ve sborníku
Výsledek na webu
- 1 - 10 out of 88