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

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

Namespace Prefixes

PrefixIRI
n12http://linked.opendata.cz/ontology/domain/vavai/riv/typAkce/
dctermshttp://purl.org/dc/terms/
n19http://purl.org/net/nknouf/ns/bibtex#
n6http://localhost/temp/predkladatel/
n17http://linked.opendata.cz/resource/domain/vavai/riv/tvurce/
n7http://linked.opendata.cz/resource/domain/vavai/projekt/
n16http://linked.opendata.cz/ontology/domain/vavai/
n10http://linked.opendata.cz/resource/domain/vavai/zamer/
n3https://schema.org/
shttp://schema.org/
skoshttp://www.w3.org/2004/02/skos/core#
n4http://linked.opendata.cz/ontology/domain/vavai/riv/
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/
n21http://linked.opendata.cz/ontology/domain/vavai/riv/duvernostUdaju/
xsdhhttp://www.w3.org/2001/XMLSchema#
n13http://linked.opendata.cz/resource/domain/vavai/vysledek/RIV%2F00216305%3A26230%2F08%3APU76682%21RIV10-MSM-26230___/
n18http://linked.opendata.cz/ontology/domain/vavai/riv/aktivita/
n15http://linked.opendata.cz/ontology/domain/vavai/riv/jazykVysledku/
n20http://linked.opendata.cz/ontology/domain/vavai/riv/obor/
n11http://linked.opendata.cz/ontology/domain/vavai/riv/druhVysledku/
n5http://reference.data.gov.uk/id/gregorian-year/

Statements

Subject Item
n2:RIV%2F00216305%3A26230%2F08%3APU76682%21RIV10-MSM-26230___
rdf:type
skos:Concept n16:Vysledek
dcterms:description
We address the problem of computing simulation relations over tree automata. In particular, we consider downward and upward simulations on tree automata, which are, loosely speaking, analogous to forward and backward relations over word automata. We provide simple and efficient algorithms for computing these relations based on a reduction to the problem of computing simulations on labelled transition systems. Furthermore, we show that downward and upward relations can be combined to get relations compatible with the tree language equivalence, which can subsequently be used for an efficient size reduction of nondeterministic tree automata. This is of a very high interest, for instance, for symbolic verification methods such as regular model checking, which use tree automata to represent infinite sets of reachable configurations. We provide experimental results showing the efficiency of our algorithms on examples of tree automata taken from regular model checking computations. We address the problem of computing simulation relations over tree automata. In particular, we consider downward and upward simulations on tree automata, which are, loosely speaking, analogous to forward and backward relations over word automata. We provide simple and efficient algorithms for computing these relations based on a reduction to the problem of computing simulations on labelled transition systems. Furthermore, we show that downward and upward relations can be combined to get relations compatible with the tree language equivalence, which can subsequently be used for an efficient size reduction of nondeterministic tree automata. This is of a very high interest, for instance, for symbolic verification methods such as regular model checking, which use tree automata to represent infinite sets of reachable configurations. We provide experimental results showing the efficiency of our algorithms on examples of tree automata taken from regular model checking computations.
dcterms:title
Computing Simulations over Tree Automata (Efficient Techniques for Reducing Tree Automata) Computing Simulations over Tree Automata (Efficient Techniques for Reducing Tree Automata)
skos:prefLabel
Computing Simulations over Tree Automata (Efficient Techniques for Reducing Tree Automata) Computing Simulations over Tree Automata (Efficient Techniques for Reducing Tree Automata)
skos:notation
RIV/00216305:26230/08:PU76682!RIV10-MSM-26230___
n4:aktivita
n18:P n18:Z
n4:aktivity
P(GA102/07/0322), Z(MSM0021630528)
n4:dodaniDat
n5:2010
n4:domaciTvurceVysledku
n17:9761985 n17:1258486
n4:druhVysledku
n11:D
n4:duvernostUdaju
n21:S
n4:entitaPredkladatele
n13:predkladatel
n4:idSjednocenehoVysledku
360922
n4:idVysledku
RIV/00216305:26230/08:PU76682
n4:jazykVysledku
n15:eng
n4:klicovaSlova
tree automata, simulation relation, nondeterministic tree automata, reductionm, language preservation<br>
n4:klicoveSlovo
n9:nondeterministic%20tree%20automata n9:simulation%20relation n9:tree%20automata n9:reductionm n9:language%20preservation%3Cbr%3E
n4:kontrolniKodProRIV
[61AE0E473B51]
n4:mistoKonaniAkce
Budapešť
n4:mistoVydani
Berlin
n4:nazevZdroje
Tools and Algorithms for the Construction and Analysis of Systems
n4:obor
n20:JC
n4:pocetDomacichTvurcuVysledku
2
n4:pocetTvurcuVysledku
5
n4:projekt
n7:GA102%2F07%2F0322
n4:rokUplatneniVysledku
n5:2008
n4:tvurceVysledku
Abdulla, Parosh Kaati, Lisa Holík, Lukáš Vojnar, Tomáš Bouajjani, Ahmed
n4:typAkce
n12:WRD
n4:zahajeniAkce
2008-03-29+01:00
n4:zamer
n10:MSM0021630528
s:numberOfPages
16
n19:hasPublisher
Springer-Verlag
n3:isbn
978-3-540-78799-0
n6:organizacniJednotka
26230