Journal Article
@Article
Artikel in Fachzeitschrift


Show entries of:

this year (2019) | last year (2018) | two years ago (2017) | Notes URL

Action:

login to update

Options:




Library Locked Library locked




Author, Editor(s)

Author(s):

Jez, Artur
Maletti, Andreas

dblp
dblp

Not MPG Author(s):

Maletti, Andreas

BibTeX cite key*:

JezMaletti2013

Title

Title*:

Hyper-minimization for deterministic tree automata

Journal

Journal Title*:

International Journal of Foundations of Computer Science

Journal's URL:

http://www.worldscientific.com/worldscinet/ijfcs

Download URL
for the article:


Language:

English

Publisher

Publisher's
Name:

World Scientific

Publisher's URL:


Publisher's
Address:

http://www.worldscientific.com

ISSN:

0129-0541

Vol, No, pp, Date

Volume*:

24

Number:

6

Publishing Date:

September 2013

Pages*:

815-830

Number of
VG Pages:


Page Start:


Page End:


Sequence Number:


DOI:

10.1142/S0129054113400200

Note, Abstract, ©

Note:


(LaTeX) Abstract:

Hyper-minimization is a recent automaton compression technique that can reduce the size of an automaton beyond the limits imposed by classical minimization. The additional compression power is enabled by allowing a finite difference in the represented language. The necessary theory for hyper-minimization is developed for (bottom-up) deterministic tree automata. The hyper-minimization problem for deterministic tree automata is reduced to the hyper-minimization problem for deterministic finite-state string automata, for which fast algorithms exist. The fastest algorithm obtained in this way runs in time $O(m \log n)$, where $m$ is the size of the transition table and $n$ is the number of states of the input tree automaton.

URL for the Abstract:


Categories,
Keywords:

Deterministic tree automaton, Minimization, Hyper-minimization, Lossy minimization.

HyperLinks / References / URLs:


Copyright Message:


Personal Comments:


Download
Access Level:

Internal

Correlation

MPG Unit:

Max-Planck-Institut für Informatik



MPG Subunit:

Algorithms and Complexity Group

Audience:

experts only

Appearance:

MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort


BibTeX Entry:

@ARTICLE{JezMaletti2013,
AUTHOR = {Jez, Artur and Maletti, Andreas},
TITLE = {Hyper-minimization for deterministic tree automata},
JOURNAL = {International Journal of Foundations of Computer Science},
PUBLISHER = {World Scientific},
YEAR = {2013},
NUMBER = {6},
VOLUME = {24},
PAGES = {815--830},
ADDRESS = {http://www.worldscientific.com},
MONTH = {September},
ISBN = {0129-0541},
DOI = {10.1142/S0129054113400200},
}


Entry last modified by Artur Jez, 11/24/2014
Show details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
[Library]
Created
01/21/2014 04:03:32 PM
Revision
1.
0.


Editor
Artur Jez
Artur Jez


Edit Date
11/24/2014 04:35:22 PM
01/21/2014 04:03:32 PM