Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
A polynomial algorithm for deciding bisimilarity of normed context-free processes
RISE - Research Institutes of Sweden, ICT, SICS.
1994 (English)Report (Other academic)
Abstract [en]

The previous best upper bound on the complexity of deciding bisimilarity between normed context-free processes, due to Huynh and Tian, is that the problem lies in the second level of the polynomial hierarchy: their algorithm guesses a proof of equivalence and validates this proof in polynomial time using oracles freely answering questions which are in NP. In this paper we improve on this result by presenting a polynomial-time algorithm which solves this problem. As a corollary, we have a polynomial algorithm for the equivalence problem for simple context-free grammars.

Place, publisher, year, edition, pages
Swedish Institute of Computer Science , 1994, 1. , p. 20
Series
SICS Research Report, ISSN 0283-3638 ; R94:08
Keywords [en]
Process algebra, Formal languages, Analysis of algorithms
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:ri:diva-21381OAI: oai:DiVA.org:ri-21381DiVA, id: diva2:1041417
Available from: 2016-10-31 Created: 2016-10-31 Last updated: 2018-02-02Bibliographically approved

Open Access in DiVA

fulltext(2356 kB)0 downloads
File information
File name FULLTEXT01.pdfFile size 2356 kBChecksum SHA-512
fe99e266afb09e6edc718618632a595611d0fd3ee7e945f88b27e6336bf5f0cd04e42ff2ef1d770a59ba28e3ae4585e6f2e930405f9696c9fbdda4740b1a4f6f
Type fulltextMimetype application/pdf

By organisation
SICS
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

urn-nbn

Altmetric score

urn-nbn
Total: 37 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
v. 2.34.0