✦ LIBER ✦

New upper bounds to the limitedness of distance automata

✍ Scribed by Kosaburo Hashiguchi

Book ID: 104326384
Publisher: Elsevier Science
Year: 2000
Tongue: English
Weight: 143 KB
Volume: 233
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(97)00260-0

No coin nor oath required. For personal study only.

✦ Synopsis

A distance automaton is a ÿnite nondeterministic automaton with a distance function which assigns zero or one to each atomic transition and assigns a nonnegative integer to each accepted word by the plus-min principle. In this paper, we prove that the distances of all accepted words of a distance automaton is bounded by some constant if and only if they are bounded by 2 4m 3 +m log(m+2)+m , where m is the number of states of the automaton.

📜 SIMILAR VOLUMES

Erratum to “New upper bounds to the limi

Erratum to “New upper bounds to the limitedness of distance automata”: [Theoret. Comput. Sci. 233 (2000) 19–32]

✍ Kosaburo Hashiguchi 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 38 KB

Upper bounds on the minimum distance of

Upper bounds on the minimum distance of spherical codes

✍ Boyvalenkov, P.G.; Danev, D.P.; Bumova, S.P. 📂 Article 📅 1996 🏛 IEEE 🌐 English ⚖ 591 KB

Efficient lower and upper bounds of the

Efficient lower and upper bounds of the diagonal-flip distance between triangulations

✍ Jean-Luc Baril; Jean-Marcel Pallo 📂 Article 📅 2006 🏛 Elsevier Science 🌐 English ⚖ 143 KB

New upper bounds on the decomposability

New upper bounds on the decomposability of planar graphs

✍ Fedor V. Fomin; Dimitrios M. Thilikos 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 335 KB 👁 1 views

## Abstract It is known that a planar graph on __n__ vertices has branch‐width/tree‐width bounded by $\alpha \sqrt {n}$. In many algorithmic applications, it is useful to have a small bound on the constant α. We give a proof of the best, so far, upper bound for the constant α. In particular, for th

New Bounds on the Distance Distribution

New Bounds on the Distance Distribution of Extended Goppa Codes

✍ Simon Litsyn; Sarit Zur 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 169 KB

We derive new estimates for the error term in the binomial approximation to the distance distribution of extended Goppa codes. This is an improvement on the earlier bounds by Vladuts and Skorobogatov, and Levy and Litsyn.

Upper Bounds on the Covering Radius of a

Upper Bounds on the Covering Radius of a Code with a Given Dual Distance

✍ S. Litsyn; A. Tietäväinen 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 235 KB

We derive new upper bounds on the covering radius of a binary linear code as a function of its dual distance and dual-distance width . These bounds improve on the Delorme -Sole ´ -Stokes bounds , and in a certain interval for binary linear codes they are also better than Tieta ¨ va ¨ inen's bound .