This HTML5 document contains 46 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
n16http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
n6http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F61989100%3A27240%2F10%3A86075810%21RIV11-MSM-27240___/
dctermshttp://purl.org/dc/terms/
n13http://purl.org/net/nknouf/ns/bibtex#
n8http://localhost/temp/predkladatel/
n17http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n11http://linked.opendata.cz/resource/domain/vavai/projekt/
n19http://linked.opendata.cz/ontology/domain/vavai/
n14https://schema.org/
shttp://schema.org/
n4http://linked.opendata.cz/ontology/domain/vavai/riv/
skoshttp://www.w3.org/2004/02/skos/core#
n2http://linked.opendata.cz/resource/domain/vavai/vysledek/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n9http://linked.opendata.cz/ontology/domain/vavai/riv/klicoveSlovo/
n7http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n20http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n15http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n12http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n10http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n21http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F61989100%3A27240%2F10%3A86075810%21RIV11-MSM-27240___
rdf:type
skos:Concept n19:Vysledek
dcterms:description
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 known decidability result (Jancar 2000) and matches the known PSPACE lower bound (Srba 2009). We add the PTIME completeness result for deciding regularity (i.e. finiteness up to bisimilarity) of one-counter processes. 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 known decidability result (Jancar 2000) and matches the known PSPACE lower bound (Srba 2009). We add the PTIME completeness result for deciding regularity (i.e. finiteness up to bisimilarity) of one-counter processes.
dcterms:title
Bisimilarity of One-Counter Processes Is PSPACE-Complete Bisimilarity of One-Counter Processes Is PSPACE-Complete
skos:prefLabel
Bisimilarity of One-Counter Processes Is PSPACE-Complete Bisimilarity of One-Counter Processes Is PSPACE-Complete
skos:notation
RIV/61989100:27240/10:86075810!RIV11-MSM-27240___
n4:aktivita
n20:P
n4:aktivity
P(1M0567)
n4:dodaniDat
n21:2011
n4:domaciTvurceVysledku
n17:6026508 n17:9330771
n4:druhVysledku
n12:D
n4:duvernostUdaju
n7:S
n4:entitaPredkladatele
n6:predkladatel
n4:idSjednocenehoVysledku
249008
n4:idVysledku
RIV/61989100:27240/10:86075810
n4:jazykVysledku
n15:eng
n4:klicovaSlova
Automata; Algorithms; Equivalence; Undecidability; Finite-state Processes
n4:klicoveSlovo
n9:Finite-state%20Processes n9:Undecidability n9:Automata n9:Equivalence n9:Algorithms
n4:kontrolniKodProRIV
[F672E390D960]
n4:mistoKonaniAkce
Paris, France
n4:mistoVydani
Berlin Heidelberg
n4:nazevZdroje
CONCUR 2010 - Concurrency Theory
n4:obor
n10:IN
n4:pocetDomacichTvurcuVysledku
2
n4:pocetTvurcuVysledku
3
n4:projekt
n11:1M0567
n4:rokUplatneniVysledku
n21:2010
n4:tvurceVysledku
Böhm, Stanislav Jančar, Petr Göller, Stefan
n4:typAkce
n16:WRD
n4:wos
000285373500013
n4:zahajeniAkce
2010-08-31+02:00
s:issn
0302-9743
s:numberOfPages
15
n13:hasPublisher
Springer-Verlag. (Berlin; Heidelberg)
n14:isbn
978-3-642-15374-7
n8:organizacniJednotka
27240