Show/Hide Menu
Hide/Show Apps
anonymousUser
Logout
Türkçe
Türkçe
Search
Search
Login
Login
OpenMETU
OpenMETU
About
About
Açık Bilim Politikası
Açık Bilim Politikası
Frequently Asked Questions
Frequently Asked Questions
Browse
Browse
By Issue Date
By Issue Date
Authors
Authors
Titles
Titles
Subjects
Subjects
Communities & Collections
Communities & Collections
Effective optimization with weighted automata on decomposable trees
Date
2014-01-02
Author
Ravve, E. V.
Volkovich, Z.
Weber, Gerhard Wilhelm
Metadata
Show full item record
This work is licensed under a
Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License
.
Item Usage Stats
1
views
0
downloads
In this paper, we consider quantitative optimization problems on decomposable discrete systems. We restrict ourselves to labeled trees as the description of the systems and we use weighted automata on them as our computational model. We introduce a new kind of labeled decomposable trees, sum-like weighted labeled trees, and propose a method, which allows us to reduce the solution of an optimization problem, defined in a fragment of Weighted Monadic Second Order Logic, on such a tree to the solution of effectively derived problems, defined in the same logic, on its components with some additional post-processing. The approach originates from a method, proposed first by Feferman and Vaught in 1959, which we adapt and generalize. We adapt the method to the case of (fragments of) Weighted Monadic Second Order Logic and generalize it to the case of sum-like labeled trees rather than disjoint union and product. The main result of the paper may be applied in the wide range of optimization problems, such as critical path analysis or project planning, network optimization, generalized assignment problem, routing and scheduling as well as in the modern document languages like XML, image processing and compression, probabilistic systems or speech-to-text processing.
Subject Keywords
Management Science and Operations Research
,
Control and Optimization
,
Applied Mathematics
URI
https://hdl.handle.net/11511/52390
Journal
OPTIMIZATION
DOI
https://doi.org/10.1080/02331934.2013.865735
Collections
Graduate School of Applied Mathematics, Article