For $\beta > 1$ a real algebraic integer ({\it the base}), the finite alphabets $\mathcal{A} \subset \mathbb{Z}$ which realize the identity $\mathbb{Q}(\beta) = {\rm Per}_{\mathcal{A}}(\beta)$, where ${\rm Per}_{\mathcal{A}}(\beta)$ is the set of complex numbers which are $(\beta, \mathcal{A})$-eventually periodic representations, are investigated. Comparing with the greedy algorithm, minimal and natural alphabets are defined. The natural alphabets are shown to be correlated to the asymptotics of the Pierce numbers of the base $\beta$ and Lehmer's problem. The notion of rewriting trail is introduced to construct intermediate alphabets associated with small polynomial values of the base. Consequences on the representations of neighbourhoods of the origin in $\mathbb{Q}(\beta)$, generalizing Schmidt's theorem related to Pisot numbers, are investigated. Applications to Galois conjugation are given for convergent sequences of bases $\gamma_s := \gamma_{n, m_1 , \ldots , m_s}$ such that $\gamma_{s}^{-1}$ is the unique root in $(0,1)$ of an almost Newman polynomial of the type $-1+x+x^n +x^{m_1}+\ldots+ x^{m_s}$, $n \geq 3$, $s \geq 1$, $m_1 - n \geq n-1$, $m_{q+1}-m_q \geq n-1$ for all $q \geq 1$. For $\beta > 1$ a reciprocal algebraic integer close to one, the poles of modulus $< 1$ of the dynamical zeta function of the $\beta$-shift $\zeta_{\beta}(z)$ are shown, under some assumptions, to be zeroes of the minimal polynomial of $\beta$.

0
下载
关闭预览

相关内容

Alphabet is mostly a collection of companies. This newer Google is a bit slimmed down, with the companies that are pretty far afield of our main internet products contained in Alphabet instead.
abc.xyz/

For some Maltsev conditions $\Sigma$ it is enough to check if a finite algebra $\mathbf A$ satisfies $\Sigma$ locally on subsets of bounded size, in order to decide, whether $\mathbf A$ satisfies $\Sigma$ (globally). This local-global property is the main known source of tractability results for deciding Maltsev conditions. In this paper we investigate the local-global property for the existence of a $G$-term, i.e. an $n$-ary term that is invariant under permuting its variables according to a permutation group $G \leq$ Sym($n$). Our results imply in particular that all cyclic loop conditions (in the sense of Bodirsky, Starke, and Vucaj) have the local-global property (and thus can be decided in polynomial time), while symmetric terms of arity $n>2$ fail to have it.

0
0
下载
预览

In this work we propose a formal system for fuzzy algebraic reasoning. The sequent calculus we define is based on two kinds of propositions, capturing equality and existence of terms as members of a fuzzy set. We provide a sound semantics for this calculus and show that there is a notion of free model for any theory in this system, allowing us (with some restrictions) to recover models as Eilenberg-Moore algebras for some monad. We will also prove a completeness result: a formula is derivable from a given theory if and only if it is satisfied by all models of the theory. Finally, leveraging results by Milius and Urbat, we give HSP-like characterizations of subcategories of algebras which are categories of models of particular kinds of theories.

0
0
下载
预览

We propose several heuristics for mitigating one of the main causes of combinatorial explosion in rank-based complementation of B\"{u}chi automata (BAs): unnecessarily high bounds on the ranks of states. First, we identify elevator automata, which is a large class of BAs (generalizing semi-deterministic BAs), occurring often in practice, where ranks of states are bounded according to the structure of strongly connected components. The bounds for elevator automata also carry over to general BAs that contain elevator automata as a sub-structure. Second, we introduce two techniques for refining bounds on the ranks of BA states using data-flow analysis of the automaton. We implement out techniques as an extension of the tool Ranker for BA complementation and show that they indeed greatly prune the generated state space, obtaining significantly better results and outperforming other state-of-the-art tools on a large set of benchmarks.

0
0
下载
预览

There are various metrics for researching error-correcting codes. Especially, high-density data storage system gives the existence of inconsistency for the reading and writing process. The symbol-pair metric is motivated for outputs that have overlapping pairs of symbols in a certain channel. The Rosenbloom-Tsfasman (RT) metric is introduced since there exists a problem that is related to transmission over several parallel communication channels with some channels not available for the transmission. In this paper, we determine the minimum symbol-pair weight and RT weight of repeated-root cyclic codes over $\mathfrak R=\Bbb F_{p^m}[u]/\langle u^4\rangle$ of length $n=p^k$. For the determination, we explicitly present third torsional degree for all different types of cyclic codes over $\mathfrak R$ of length $n$.

0
0
下载
预览

We consider the termination problem for triangular weakly non-linear loops (twn-loops) over some ring $\mathcal{S}$ like $\mathbb{Z}$, $\mathbb{Q}$, or $\mathbb{R}$. Essentially, the guard of such a loop is an arbitrary quantifier-free Boolean formula over (possibly non-linear) polynomial inequations, and the body is a single assignment of the form $(x_1, \ldots, x_d) \longleftarrow (c_1 \cdot x_1 + p_1, \ldots, c_d \cdot x_d + p_d)$ where each $x_i$ is a variable, $c_i \in \mathcal{S}$, and each $p_i$ is a (possibly non-linear) polynomial over $\mathcal{S}$ and the variables $x_{i+1},\ldots,x_{d}$. We show that the question of termination can be reduced to the existential fragment of the first-order theory of $\mathcal{S}$ and $\mathbb{R}$. For loops over $\mathbb{R}$, our reduction implies decidability of termination. For loops over $\mathbb{Z}$ and $\mathbb{Q}$, it proves semi-decidability of non-termination. Furthermore, we present a transformation to convert certain non-twn-loops into twn-form. Then the original loop terminates iff the transformed loop terminates over a specific subset of $\mathbb{R}$, which can also be checked via our reduction. Moreover, we formalize a technique to linearize twn-loops in our setting and analyze its complexity. Based on these results, we prove complexity bounds for the termination problem of twn-loops as well as tight bounds for two important classes of loops which can always be transformed into twn-loops. Finally, we show that there is an important class of linear loops where our decision procedure results in an efficient procedure for termination analysis, i.e., where the parameterized complexity of deciding termination is polynomial.

0
0
下载
预览

We study the problem of locating the source of a stochastic epidemic diffusion process from a sparse set of sensors. In a graph $G=(V,E)$, an unknown source node $v^* \in V$ is drawn uniformly at random, and unknown edge weights $w(e)$ for $e\in E$, representing the propagation delays along the edges, are drawn independently from a Gaussian distribution of mean $1$ and variance $\sigma^2$. An algorithm then attempts to locate $v^*$ by picking sensor (also called query) nodes $s \in V$ and being told the length of the shortest path between $s$ and $v^*$ in graph $G$ weighted by $w$. We consider two settings: \emph{static}, in which all query nodes must be decided in advance, and \emph{sequential}, in which each query can depend on the results of the previous ones. We characterize the query complexity when $G$ is an $n$-node path. In the static setting, $\Theta(n\sigma^2)$ queries are needed for $\sigma^2 \leq 1$, and $\Theta(n)$ for $\sigma^2 \geq 1$. In the sequential setting, somewhat surprisingly, only $\Theta(\log\log_{1/\sigma}n)$ are needed when $\sigma^2 \leq 1/2$, and $\Theta(\log \log n)+O_\sigma(1)$ when $\sigma^2 \geq 1/2$. This is the first mathematical study of sensor-based source location in a non-deterministic epidemic process.

0
0
下载
预览

We show that it is provable in PA that there is an arithmetically definable sequence $\{\phi_{n}:n \in \omega\}$ of $\Pi^{0}_{2}$-sentences, such that - PRA+$\{\phi_{n}:n \in \omega\}$ is $\Pi^{0}_{2}$-sound and $\Pi^{0}_{1}$-complete - the length of $\phi_{n}$ is bounded above by a polynomial function of $n$ with positive leading coefficient - PRA+$\phi_{n+1}$ always proves 1-consistency of PRA+$\phi_{n}$. One has that the growth in logical strength is in some sense "as fast as possible", manifested in the fact that the total general recursive functions whose totality is asserted by the true $\Pi^{0}_{2}$-sentences in the sequence are cofinal growth-rate-wise in the set of all total general recursive functions. We then develop an argument which makes use of a sequence of sentences constructed by an application of the diagonal lemma, which are generalisations in a broad sense of Hugh Woodin's "Tower of Hanoi" construction as outlined in his essay "Tower of Hanoi" in Chapter 18 of the anthology "Truth in Mathematics". The argument establishes the result that it is provable in PA that $P \neq NP$. We indicate how to pull the argument all the way down into EFA.

0
0
下载
预览

We first show that given a $k_1$-letter quantum finite automata $\mathcal{A}_1$ and a $k_2$-letter quantum finite automata $\mathcal{A}_2$ over the same input alphabet $\Sigma$, they are equivalent if and only if they are $(n_1^2+n_2^2-1)|\Sigma|^{k-1}+k$-equivalent where $n_1$, $i=1,2$, are the numbers of state in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$. By applying a method, due to the author, used to deal with the equivalence problem of {\it measure many one-way quantum finite automata}, we also show that a $k_1$-letter measure many quantum finite automaton $\mathcal{A}_1$ and a $k_2$-letter measure many quantum finite automaton $\mathcal{A}_2$ are equivalent if and only if they are $(n_1^2+n_2^2-1)|\Sigma|^{k-1}+k$-equivalent where $n_i$, $i=1,2$, are the numbers of state in $\mathcal{A}_i$ respectively, and $k=\max\{k_1,k_2\}$. Next, we study the language equivalence problem of those two kinds of quantum finite automata. We show that for $k$-letter quantum finite automata, the non-strict cut-point language equivalence problem is undecidable, i.e., it is undecidable whether $L_{\geq\lambda}(\mathcal{A}_1)=L_{\geq\lambda}(\mathcal{A}_2)$ where $0<\lambda\leq 1$ and $\mathcal{A}_i$ are $k_i$-letter quantum finite automata. Further, we show that both strict and non-strict cut-point language equivalence problem for $k$-letter measure many quantum finite automata are undecidable. The direct consequences of the above outcomes are summarized in the paper. Finally, we comment on existing proofs about the minimization problem of one way quantum finite automata not only because we have been showing great interest in this kind of problem, which is very important in classical automata theory, but also due to that the problem itself, personally, is a challenge. This problem actually remains open.

0
0
下载
预览

This research addresses a new tool for data analysis known as Topological Data Analysis TDA It underlies an area of Mathematics known as Combinatorial Algebra or more recently Algebraic Topology which through making strong use of Computation Statistics Probability and Topology among other concepts extracts mathematical characteristics from a set of data that allow us associate create and infer general and quality information about them

0
0
下载
预览

In this paper we initiate the study of cyclic algebraic geometry codes. We give conditions to construct cyclic algebraic geometry codes in the context of algebraic function fields over a finite field by using their group of automorphisms. We prove that cyclic algebraic geometry codes constructed in this way are closely related to cyclic extensions. We also give a detailed study of the monomial equivalence of cyclic algebraic geometry codes constructed with our method in the case of a rational function field.

0
0
下载
预览
小贴士
相关论文
Alexandr Kazda,Michael Kompatscher
0+阅读 · 10月21日
Davide Castelnovo,Marino Miculan
0+阅读 · 10月21日
Vojtěch Havlena,Ondřej Lengál,Barbora Šmahlíková
0+阅读 · 10月19日
Florian Frohn,Marcel Hark,Jürgen Giesl
0+阅读 · 10月18日
Victor Lecomte,Gergely Ódor,Patrick Thiran
0+阅读 · 10月17日
Rupert McCallum
0+阅读 · 9月22日
Daniel Trejo Medina,Karla Sarai Jimenez
0+阅读 · 6月10日
Gustavo Cabaña,María Chara,Ricardo A. Podestá,Ricardo Toledano
0+阅读 · 6月1日
相关资讯
17篇必看[知识图谱Knowledge Graphs] 论文@AAAI2020
计算机 | EMNLP 2019等国际会议信息6条
Call4Papers
13+阅读 · 2019年4月26日
Unsupervised Learning via Meta-Learning
CreateAMind
29+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
9+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
10+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
23+阅读 · 2018年9月12日
Hierarchical Disentangled Representations
CreateAMind
3+阅读 · 2018年4月15日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
强化学习 cartpole_a3c
CreateAMind
9+阅读 · 2017年7月21日
Top