About: Composed Bisimulation for Tree Automata

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

About: Composed Bisimulation for 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 reducing the size of (nondeterministic, bottom-up) tree automata (TA) using suitable, language-preserving equivalences on the states of the automata. In particular, we propose the so-called composed bisimulation equivalence as a new language preserving equivalence. A composed bisimulation equivalence is defined in terms of two different relations, namely the upward and downward bisimulation equivalence. We provide simple and efficient algorithms for computing these relations. The notion of composed bisimulation equivalence is motivated by an attempt to obtain an equivalence that can provide better reductions than what currently known bisimulation-based approaches can offer, but which is not significantly more difficult to compute (and hence stays below the computational requirements of simulation-based reductions). The experimental results we present in the paper show that our composed bisimulation equivalence meets such requirements, and hence provides users of TA with a fi We address the problem of reducing the size of (nondeterministic, bottom-up) tree automata (TA) using suitable, language-preserving equivalences on the states of the automata. In particular, we propose the so-called composed bisimulation equivalence as a new language preserving equivalence. A composed bisimulation equivalence is defined in terms of two different relations, namely the upward and downward bisimulation equivalence. We provide simple and efficient algorithms for computing these relations. The notion of composed bisimulation equivalence is motivated by an attempt to obtain an equivalence that can provide better reductions than what currently known bisimulation-based approaches can offer, but which is not significantly more difficult to compute (and hence stays below the computational requirements of simulation-based reductions). The experimental results we present in the paper show that our composed bisimulation equivalence meets such requirements, and hence provides users of TA with a fi (en)
Title	Composed Bisimulation for Tree Automata Composed Bisimulation for Tree Automata (en)
skos:prefLabel	Composed Bisimulation for Tree Automata Composed Bisimulation for Tree Automata (en)
skos:notation	RIV/00216305:26230/09:PU82678!RIV10-MSM-26230___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(GA102/07/0322), P(GD102/09/H042), Z(MSM0021630528)
http://linked.open...iv/cisloPeriodika	4
http://linked.open...vai/riv/dodaniDat	2010
http://linked.open...aciTvurceVysledku	Holík, Lukáš Vojnar, Tomáš
http://linked.open.../riv/druhVysledku	J - Článek v odborném periodiku
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	307895
http://linked.open...ai/riv/idVysledku	RIV/00216305:26230/09:PU82678
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	finite tree automata, bisimulation, size reduction. (en)
http://linked.open.../riv/klicoveSlovo	bisimulation finite tree automata size reduction.
http://linked.open...odStatuVydavatele	SG - Singapurská republika
http://linked.open...ontrolniKodProRIV	[D80BFBCB2AD9]
http://linked.open...i/riv/nazevZdroje	International Journal of Foundations of Computer Science
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	Mathematical and Engineering Approaches to Developing Reliable and Secure Concurrent and Distributed Computer Systems Advanced Formal Approaches in the Design and Verification of Computer-Based Systems
http://linked.open...UplatneniVysledku	2009
http://linked.open...v/svazekPeriodika	20
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
issn	0129-0541
number of pages	16 (xsd:int)
http://localhost/t...ganizacniJednotka	26230
is http://linked.open...avai/riv/vysledek of	Composed Bisimulation for Tree Automata Composed Bisimulation for Tree Automata Composed Bisimulation for Tree Automata Composed Bisimulation for Tree Automata

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