About: Simulations and Aintichains for Efficient Handling of Tree Automata

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

About: Simulations and Aintichains for Efficient Handling of 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	This work is focused on techniques for finite automata and their use in practice, with the main emphasis on nondeterministic tree automata. This concerns namely techniques for size reduction and language inclusion testing, which are two problems that are crucial for many applications of tree automata. For size reduction of tree automata, we adapt the simulation quotient technique that is well established for finite word automata. We give efficient algorithms for computing tree automata simulations and we also introduce a new type of relation that arises from a combination of tree automata downward and upward simulation and that is very well suited for quotienting. The combination principle is relevant also for word automata. We then generalise the so called antichain universality and language inclusion checking technique developed originally for finite word automata for tree automata. Subsequently, we improve the antichain technique for both word and tree automata by combining it with the This work is focused on techniques for finite automata and their use in practice, with the main emphasis on nondeterministic tree automata. This concerns namely techniques for size reduction and language inclusion testing, which are two problems that are crucial for many applications of tree automata. For size reduction of tree automata, we adapt the simulation quotient technique that is well established for finite word automata. We give efficient algorithms for computing tree automata simulations and we also introduce a new type of relation that arises from a combination of tree automata downward and upward simulation and that is very well suited for quotienting. The combination principle is relevant also for word automata. We then generalise the so called antichain universality and language inclusion checking technique developed originally for finite word automata for tree automata. Subsequently, we improve the antichain technique for both word and tree automata by combining it with the (en)
Title	Simulations and Aintichains for Efficient Handling of Tree Automata Simulations and Aintichains for Efficient Handling of Tree Automata (en)
skos:prefLabel	Simulations and Aintichains for Efficient Handling of Tree Automata Simulations and Aintichains for Efficient Handling of Tree Automata (en)
skos:notation	RIV/00216305:26230/10:PU90564!RIV12-GA0-26230___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(GAP103/10/0306), P(OC10009), Z(MSM0021630528)
http://linked.open...vai/riv/dodaniDat	2012
http://linked.open...aciTvurceVysledku	Holík, Lukáš Vojnar, Tomáš
http://linked.open.../riv/druhVysledku	B - Odborná kniha
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	287493
http://linked.open...ai/riv/idVysledku	RIV/00216305:26230/10:PU90564
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	finite automata, finite tree automata, alternating Büchi automata, nondeterminism, simulation, bisimulation, universality, language inclusion, antichain, quotienting, regular tree model checking (en)
http://linked.open.../riv/klicoveSlovo	simulation finite automata universality language inclusion nondeterminism bisimulation antichain alternating Büchi automata finite tree automata quotienting regular tree model checking
http://linked.open...ontrolniKodProRIV	[4DBE709E419E]
http://linked.open...i/riv/mistoVydani	Brno
http://linked.open...vEdiceCisloSvazku	FIT Monograph
http://linked.open...i/riv/nazevZdroje	Simulations and Aintichains for Efficient Handling of Tree Automata
http://linked.open...in/vavai/riv/obor	IN
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...v/pocetStranKnihy	150 (xsd:int)
http://linked.open...cetTvurcuVysledku	2 (xsd:int)
http://linked.open...vavai/riv/projekt	Static and Dynamic Verification of Programs with Advanced Features of Concurrency and Unboundedness Dealing with Complex Data Structures and Concurrency within the Rich Model Toolkit
http://linked.open...UplatneniVysledku	2010
http://linked.open...iv/tvurceVysledku	Holík, Lukáš Vojnar, Tomáš
http://linked.open...n/vavai/riv/zamer	Výzkum informačních technologií z hlediska bezpečnosti
number of pages	150 (xsd:int)
http://purl.org/ne...btex#hasPublisher	Vysoké učení technické v Brně. Fakulta informačních technologií
https://schema.org/isbn	978-80-214-4217-7
http://localhost/t...ganizacniJednotka	26230
is http://linked.open...avai/riv/vysledek of	Simulations and Aintichains for Efficient Handling of Tree Automata Simulations and Aintichains for Efficient Handling of 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, 47 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software