About: Computing Simulations over Tree Automata (Efficient Techniques for Reducing Tree Automata)

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

About: Computing Simulations over Tree Automata (Efficient Techniques for Reducing Tree Automata) 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 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. (en)
Title	Computing Simulations over Tree Automata (Efficient Techniques for Reducing Tree Automata) Computing Simulations over Tree Automata (Efficient Techniques for Reducing Tree Automata) (en)
skos:prefLabel	Computing Simulations over Tree Automata (Efficient Techniques for Reducing Tree Automata) Computing Simulations over Tree Automata (Efficient Techniques for Reducing Tree Automata) (en)
skos:notation	RIV/00216305:26230/08:PU76682!RIV10-MSM-26230___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(GA102/07/0322), Z(MSM0021630528)
http://linked.open...vai/riv/dodaniDat	2010
http://linked.open...aciTvurceVysledku	Holík, Lukáš Vojnar, Tomáš
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
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é učení technické v Brně / Fakulta informačních technologií
http://linked.open...dnocenehoVysledku	360922
http://linked.open...ai/riv/idVysledku	RIV/00216305:26230/08:PU76682
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	tree automata, simulation relation, nondeterministic tree automata, reductionm, language preservation<br> (en)
http://linked.open.../riv/klicoveSlovo	tree automata language preservation<br> nondeterministic tree automata reductionm simulation relation
http://linked.open...ontrolniKodProRIV	[61AE0E473B51]
http://linked.open...v/mistoKonaniAkce	Budapešť
http://linked.open...i/riv/mistoVydani	Berlin
http://linked.open...i/riv/nazevZdroje	Tools and Algorithms for the Construction and Analysis of Systems
http://linked.open...in/vavai/riv/obor	JC
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	5 (xsd:int)
http://linked.open...vavai/riv/projekt	Advanced Formal Approaches in the Design and Verification of Computer-Based Systems
http://linked.open...UplatneniVysledku	2008
http://linked.open...iv/tvurceVysledku	Abdulla, Parosh Holík, Lukáš Vojnar, Tomáš Bouajjani, Ahmed Kaati, Lisa
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open.../riv/zahajeniAkce	2008-03-29 (xsd:date)
http://linked.open...n/vavai/riv/zamer	Výzkum informačních technologií z hlediska bezpečnosti
number of pages	16 (xsd:int)
http://purl.org/ne...btex#hasPublisher	Springer-Verlag
https://schema.org/isbn	978-3-540-78799-0
http://localhost/t...ganizacniJednotka	26230

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, 47 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software