The Markov Chain Tree Theorem in commutative semirings and the State Reduction Algorithm in commutative semifields

Buket Benek Gursoy; Steve Kirkland; Oliver Mason; Sergey Sergeev

doi:10.1016/j.laa.2014.06.028

The Markov Chain Tree Theorem in commutative semirings and the State Reduction Algorithm in commutative semifields

Buket Benek Gursoy, Steve Kirkland, Oliver Mason, Sergey Sergeev

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

178 Downloads (Pure)

Abstract

We extend the Markov Chain Tree Theorem to general commutative semirings, and we generalize the State Reduction Algorithm to general commutative semifields. This leads to a new universal algorithm, whose prototype is the State Reduction Algorithm which computes the Markov chain tree vector of a stochastic matrix.

Original language	English
Pages (from-to)	184-196
Journal	Linear Algebra and its Applications
Volume	468
Early online date	2 Jul 2014
DOIs	https://doi.org/10.1016/j.laa.2014.06.028
Publication status	Published - 1 Mar 2015

Keywords

Markov chain
Universal algorithm
Commutative semiring
State reduction

Access to Document

10.1016/j.laa.2014.06.028Licence: Creative Commons: Attribution (CC BY)

GursoyB2021MarkovFinal published version, 368 KBLicence: Creative Commons: Attribution (CC BY)

Perron-Frobenius Theory and Max-Algebraic Combinatorics of Nonnegative Matrices
Butkovic, P.
Engineering & Physical Science Research Council
12/03/12 → 11/03/14
Project: Research Councils

Cite this

@article{95702198cb76422884e4197d72c3b40f,

title = "The Markov Chain Tree Theorem in commutative semirings and the State Reduction Algorithm in commutative semifields",

abstract = "We extend the Markov Chain Tree Theorem to general commutative semirings, and we generalize the State Reduction Algorithm to general commutative semifields. This leads to a new universal algorithm, whose prototype is the State Reduction Algorithm which computes the Markov chain tree vector of a stochastic matrix.",

keywords = "Markov chain, Universal algorithm, Commutative semiring, State reduction",

author = "{Benek Gursoy}, Buket and Steve Kirkland and Oliver Mason and Sergey Sergeev",

year = "2015",

month = mar,

day = "1",

doi = "10.1016/j.laa.2014.06.028",

language = "English",

volume = "468",

pages = "184--196",

journal = "Linear Algebra and its Applications",

issn = "0024-3795",

publisher = "Elsevier",

}

TY - JOUR

T1 - The Markov Chain Tree Theorem in commutative semirings and the State Reduction Algorithm in commutative semifields

AU - Benek Gursoy, Buket

AU - Kirkland, Steve

AU - Mason, Oliver

AU - Sergeev, Sergey

PY - 2015/3/1

Y1 - 2015/3/1

N2 - We extend the Markov Chain Tree Theorem to general commutative semirings, and we generalize the State Reduction Algorithm to general commutative semifields. This leads to a new universal algorithm, whose prototype is the State Reduction Algorithm which computes the Markov chain tree vector of a stochastic matrix.

AB - We extend the Markov Chain Tree Theorem to general commutative semirings, and we generalize the State Reduction Algorithm to general commutative semifields. This leads to a new universal algorithm, whose prototype is the State Reduction Algorithm which computes the Markov chain tree vector of a stochastic matrix.

KW - Markov chain

KW - Universal algorithm

KW - Commutative semiring

KW - State reduction

U2 - 10.1016/j.laa.2014.06.028

DO - 10.1016/j.laa.2014.06.028

M3 - Article

SN - 0024-3795

VL - 468

SP - 184

EP - 196

JO - Linear Algebra and its Applications

JF - Linear Algebra and its Applications

ER -

The Markov Chain Tree Theorem in commutative semirings and the State Reduction Algorithm in commutative semifields

Abstract

Keywords

Access to Document

Fingerprint

Projects

Perron-Frobenius Theory and Max-Algebraic Combinatorics of Nonnegative Matrices

Cite this