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
rdfs:seeAlso	http://www.fit.vutbr.cz/~vojnar/Publications/abhkv-simtree-tr-07.pdf
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 ef&#64257;cient 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 ef&#64257;cient size reduction of nondeterministic tree automata. This is of a very high interest, for instance, for symbolic veri&#64257;cation methods such as regular model checking, which use tree automata to represent in&#64257;nite sets of reachable con&#64257;gurations. We provide experimental results showing the ef&#64257;ciency of our algorithms on examples of tree automata taken from reg 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 ef&#64257;cient 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 ef&#64257;cient size reduction of nondeterministic tree automata. This is of a very high interest, for instance, for symbolic veri&#64257;cation methods such as regular model checking, which use tree automata to represent in&#64257;nite sets of reachable con&#64257;gurations. We provide experimental results showing the ef&#64257;ciency of our algorithms on examples of tree automata taken from reg (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:PU78048!RIV10-MSM-26230___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(GA102/07/0322), P(GD102/05/H050), Z(MSM0021630528)
http://linked.open...vai/riv/dodaniDat	2010
http://linked.open...aciTvurceVysledku	Holík, Lukáš Vojnar, Tomáš
http://linked.open.../riv/druhVysledku	A(V) - Audiovizuální tvorba se vzdáleným přístupem
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	360923
http://linked.open...ai/riv/idVysledku	RIV/00216305:26230/08:PU78048
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	finite tree automata, simulation, size reduction, combination of simulation relations<br> (en)
http://linked.open.../riv/klicoveSlovo	simulation size reduction combination of simulation relations<br> finite tree automata
http://linked.open...i/riv/kodPristupu	V
http://linked.open...ontrolniKodProRIV	[E26D630E8680]
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	Integrated Approach to Education of PhD Students in the Area of Parallel and Distributed Systems 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...n/vavai/riv/zamer	Výzkum informačních technologií z hlediska bezpečnosti
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, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software