About: Complexity of deciding bisimilarity between normed BPA and normed BPP

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Complexity of deciding bisimilarity between normed BPA and normed BPP Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	We present a polynomial-time algorithm deciding bisimilarity between a normed BPA process and a normed BPP process, with running time O(n^7). This improves the previously known exponential upper bound. We first suggest an O(n^3) transformation of the BPP process into %22prime form%22. Our algorithm then relies on a polynomial bound for a %22finite-state core%22 of the transition system generated by the (transformed) BPP process. We present a polynomial-time algorithm deciding bisimilarity between a normed BPA process and a normed BPP process, with running time O(n^7). This improves the previously known exponential upper bound. We first suggest an O(n^3) transformation of the BPP process into %22prime form%22. Our algorithm then relies on a polynomial bound for a %22finite-state core%22 of the transition system generated by the (transformed) BPP process. (en)
Title	Complexity of deciding bisimilarity between normed BPA and normed BPP Complexity of deciding bisimilarity between normed BPA and normed BPP (en)
skos:prefLabel	Complexity of deciding bisimilarity between normed BPA and normed BPP Complexity of deciding bisimilarity between normed BPA and normed BPP (en)
skos:notation	RIV/61989100:27240/10:86075745!RIV11-MSM-27240___
http://linked.open...avai/riv/aktivita	P
http://linked.open...avai/riv/aktivity	P(1M0567)
http://linked.open...iv/cisloPeriodika	10
http://linked.open...vai/riv/dodaniDat	2011
http://linked.open...aciTvurceVysledku	Sawa, Zdeněk Kot, Martin Jančar, Petr
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Vysoká škola báňská - Technická univerzita Ostrava / Fakulta elektrotechniky a informatiky
http://linked.open...dnocenehoVysledku	251647
http://linked.open...ai/riv/idVysledku	RIV/61989100:27240/10:86075745
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Complexity; Basic parallel processes; Basic process algebra; Bisimulation equivalence (en)
http://linked.open.../riv/klicoveSlovo	Complexity Basic parallel processes Basic process algebra Bisimulation equivalence
http://linked.open...odStatuVydavatele	US - Spojené státy americké
http://linked.open...ontrolniKodProRIV	[D3E1BF92376C]
http://linked.open...i/riv/nazevZdroje	Information and Computation
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	3 (xsd:int)
http://linked.open...cetTvurcuVysledku	3 (xsd:int)
http://linked.open...vavai/riv/projekt	Centre for Applied Cybernetics
http://linked.open...UplatneniVysledku	2010
http://linked.open...v/svazekPeriodika	208
http://linked.open...iv/tvurceVysledku	Kot, Martin Jančar, Petr Sawa, Zdeněk
http://linked.open...ain/vavai/riv/wos	000281830300006
issn	0890-5401
number of pages	13 (xsd:int)
http://localhost/t...ganizacniJednotka	27240

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 48 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software