Detail publikace

A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata

HOLÍK, L. VOJNAR, T. ABDULLA, P. KAATI, L.

Originální název

A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata

Typ

článek v časopise - ostatní, Jost

Jazyk

angličtina

Originální abstrakt

In this paper, we address the problem of reducing the size of nondeterministic (bottom-up) tree automata. We propose a uniform framework that allows for combining various upward and downward bisimulation and simulation relations in order to obtain a language-preserving combined relation suitable for reducing tree automata without a need to determinise them. The framework generalises and extends several previous works and provides a broad spectrum of different relations yielding a possibility of a fine choice between the amount of reduction and the computational demands. We, moreover, provide a significantly improved way of computing the various combined (bi-)simulation relations. We analyse properties of the considered relations both theoretically as well as through a series of experiments.

Klíčová slova

tree automata, bisimulation, simulation, combined relations, size reduction

Autoři

HOLÍK, L.; VOJNAR, T.; ABDULLA, P.; KAATI, L.

Rok RIV

2009

Vydáno

3. 9. 2009

ISSN

1571-0661

Periodikum

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE

Ročník

2009

Číslo

251

Stát

Spojené státy americké

Strany od

27

Strany do

48

Strany počet

22

URL

http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B75H1-4X4H7HH-4-1&_cdi=13109&_user=10&_orig=browse&_coverDate=09%2F03%2F2009&_sk=997489999&view=c&wchp=dGLzVzz-zSkWb&md5=3c75609f2ce3e4e6b25134896766eee6&ie=/sdarticle.pdf

BibTex

@article{BUT49315,
  author="Lukáš {Holík} and Tomáš {Vojnar} and Parosh {Abdulla} and Lisa {Kaati}",
  title="A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata",
  journal="ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE",
  year="2009",
  volume="2009",
  number="251",
  pages="27--48",
  issn="1571-0661",
  url="http://www.sciencedirect.com/science?_ob=MImg&_imagekey=B75H1-4X4H7HH-4-1&_cdi=13109&_user=10&_orig=browse&_coverDate=09%2F03%2F2009&_sk=997489999&view=c&wchp=dGLzVzz-zSkWb&md5=3c75609f2ce3e4e6b25134896766eee6&ie=/sdarticle.pdf"
}