Publication result detail

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

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

Original Title

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

English Title

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

Type

Peer-reviewed article not indexed in WoS or Scopus

Original Abstract

In this paper, we address the problem of reducing the size ofnondeterministic (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.

English abstract

In this paper, we address the problem of reducing the size ofnondeterministic (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.

Keywords

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

Key words in English

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

Authors

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

RIV year

2010

Released

03.09.2009

Book

Proceedings of the International Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2008)

ISBN

1571-0661

Periodical

ELECTRONIC NOTES IN THEORETICAL COMPUTER SCIENCE

Volume

2009

Number

251

State

United States of America

Pages from

27

Pages to

48

Pages count

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"
}