Publication Details

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

HOLÍK, L.; VOJNAR, T.; ABDULLA, P.; KAATI, L. A Uniform (Bi-)Simulation-Based Framework for Reducing Tree Automata. ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, 2009, vol. 2009, no. 251, p. 27-48. ISSN: 1571-0661.
Czech title
Uniformní systém (bi)simulačních relací pro redukci stromových automatů
Type
journal article
Language
English
Authors
Holík Lukáš, doc. Mgr., Ph.D. (DITS)
Vojnar Tomáš, prof. Ing., Ph.D. (DITS)
Abdulla Parosh
Kaati Lisa
URL
Keywords

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

Abstract

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.

Published
2009
Pages
27–48
Journal
ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE, vol. 2009, no. 251, ISSN 1571-0661
Book
Proceedings of the International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2008)
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"
}
Back to top