Search Results

Documents authored by Xu, Zhi

Found 2 Possible Name Variants:

Xu, Zhi

Document
DOI: 10.4230/LIPIcs.STACS.2008.1362
The Frobenius Problem in a Free Monoid

Authors: Jui-Yi Kao, Jeffrey Shallit, and Zhi Xu

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
The classical Frobenius problem over ${mathbb N}$ is to compute the largest integer $g$ not representable as a non-negative integer linear combination of non-negative integers $x_1, x_2, ldots, x_k$, where $gcd(x_1, x_2, ldots, x_k) = 1$. In this paper we consider novel generalizations of the Frobenius problem to the noncommutative setting of a free monoid. Unlike the commutative case, where the bound on $g$ is quadratic, we are able to show exponential or subexponential behavior for several analogues of $g$, with the precise bound depending on the particular measure chosen.
Cite as

Jui-Yi Kao, Jeffrey Shallit, and Zhi Xu. The Frobenius Problem in a Free Monoid. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 421-432, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{kao_et_al:LIPIcs.STACS.2008.1362,
  author =	{Kao, Jui-Yi and Shallit, Jeffrey and Xu, Zhi},
  title =	{{The Frobenius Problem in a Free Monoid}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{421--432},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1362},
  URN =		{urn:nbn:de:0030-drops-13620},
  doi =		{10.4230/LIPIcs.STACS.2008.1362},
  annote =	{Keywords: Combinatorics on words, Frobenius problem, free monoid}
}

Xu, Zhisheng

Document
DOI: 10.4230/LIPIcs.MFCS.2018.69
Double Threshold Digraphs

Authors: Peter Hamburger, Ross M. McConnell, Attila Pór, Jeremy P. Spinrad, and Zhisheng Xu

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
A semiorder is a model of preference relations where each element x is associated with a utility value alpha(x), and there is a threshold t such that y is preferred to x iff alpha(y) - alpha(x) > t. These are motivated by the notion that there is some uncertainty in the utility values we assign an object or that a subject may be unable to distinguish a preference between objects whose values are close. However, they fail to model the well-known phenomenon that preferences are not always transitive. Also, if we are uncertain of the utility values, it is not logical that preference is determined absolutely by a comparison of them with an exact threshold. We propose a new model in which there are two thresholds, t_1 and t_2; if the difference alpha(y) - alpha(x) is less than t_1, then y is not preferred to x; if the difference is greater than t_2 then y is preferred to x; if it is between t_1 and t_2, then y may or may not be preferred to x. We call such a relation a (t_1,t_2) double-threshold semiorder, and the corresponding directed graph G = (V,E) a (t_1,t_2) double-threshold digraph. Every directed acyclic graph is a double-threshold digraph; increasing bounds on t_2/t_1 give a nested hierarchy of subclasses of the directed acyclic graphs. In this paper we characterize the subclasses in terms of forbidden subgraphs, and give algorithms for finding an assignment of utility values that explains the relation in terms of a given (t_1,t_2) or else produces a forbidden subgraph, and finding the minimum value lambda of t_2/t_1 that is satisfiable for a given directed acyclic graph. We show that lambda gives a useful measure of the complexity of a directed acyclic graph with respect to several optimization problems that are NP-hard on arbitrary directed acyclic graphs.
Cite as

Peter Hamburger, Ross M. McConnell, Attila Pór, Jeremy P. Spinrad, and Zhisheng Xu. Double Threshold Digraphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 69:1-69:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{hamburger_et_al:LIPIcs.MFCS.2018.69,
  author =	{Hamburger, Peter and McConnell, Ross M. and P\'{o}r, Attila and Spinrad, Jeremy P. and Xu, Zhisheng},
  title =	{{Double Threshold Digraphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{69:1--69:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.69},
  URN =		{urn:nbn:de:0030-drops-96519},
  doi =		{10.4230/LIPIcs.MFCS.2018.69},
  annote =	{Keywords: posets, preference relations, approximation algorithms}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact