Journal article

ABDULLA, P., A., BOUAJJANI, A., HOLÍK, L., KAATI, L. and VOJNAR, T.. Composed Bisimulation for Tree Automata. International Journal of Foundations of Computer Science. 2009, vol. 20, no. 4, pp. 685-700. ISSN 0129-0541.
Publication language:english
Original title:Composed Bisimulation for Tree Automata
Title (cs):Složená bisimulace stromových automatů
Pages:685-700
Place:SG
Year:2009
Journal:International Journal of Foundations of Computer Science, Vol. 20, No. 4, SG
ISSN:0129-0541
URL:http://www.worldscinet.com/ijfcs/20/preserved-docs/2004/S0129054109006814.pdf [PDF]
Keywords
finite tree automata, bisimulation, size reduction.
Annotation
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 finer way to resolve the trade-off between the available degree of reduction and its cost.
BibTeX:
@ARTICLE{
   author = {A. Parosh Abdulla and Ahmed Bouajjani and Lukáš Holík and
	Lisa Kaati and Tomáš Vojnar},
   title = {Composed Bisimulation for Tree Automata},
   pages = {685--700},
   journal = {International Journal of Foundations of Computer Science},
   volume = {20},
   number = {4},
   year = {2009},
   ISSN = {0129-0541},
   language = {english},
   url = {http://www.fit.vutbr.cz/research/view_pub.php.en?id=9031}
}

Your IPv4 address: 23.20.20.195
Switch to IPv6 connection

DNSSEC [dnssec]