Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA direct proof of Agafonovs theorem and an extension to shift of finite type
84
0
0.0
(
0
)
Added by
Olivier Carton
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Authors
Olivier Carton
Ask ChatGPT about the research
No Arabic abstract
We provide a direct proof of Agafonovs theorem which states that finite state selection preserves normality. We also extends this result to the more general setting of shifts of finite type by defining selections which are compatible the shift. A slightly more general statement is obtained as we show that any Markov measure is preserved by finite state compatible selection.
rate research
Read More
The commutative ambiguity of a context-free grammar G assigns to each Parikh vector v the number of distinct leftmost derivations yielding a word with Parikh vector v. Based on the results on the generalization of Newtons method to omega-continuous semirings, we show how to approximate the commutative ambiguity by means of rational formal power series, and give a lower bound on the convergence speed of these approximations. From the latter result we deduce that the commutative ambiguity itself is rational modulo the generalized idempotence identity k=k+1 (for k some positive integer), and, subsequently, that it can be represented as a weighted sum of linear sets. This extends Parikhs well-known result that the commutative image of context-free languages is semilinear (k=1). Based on the well-known relationship between context-free grammars and algebraic systems over semirings, our results extend the work by Green et al. on the computation of the provenance of Datalog queries over commutative omega-continuous semirings.
We give a short proof of a theorem of J.-E. Pin (theorem 1.1 below), which can be found in his thesis.
Parikhs theorem states that the Parikh image of a context-free language is semilinear or, equivalently, that every context-free language has the same Parikh image as some regular language. We present a very simple construction that, given a context-free grammar, produces a finite automaton recognizing such a regular language.
In two papers, Little and Sellers introduced an exciting new combinatorial method for proving partition identities which is not directly bijective. Instead, they consider various sets of weighted tilings of a $1 times infty$ board with squares and dominoes, and for each type of tiling they construct a generating function in two different ways, which generates a $q$-series identity. Using this method, they recover quite a few classical $q$-series identities, but Eulers Pentagonal Number Theorem is not among them. In this paper, we introduce a key parameter when constructing the generating functions of various sets of tilings which allows us to recover Eulers Pentagonal Number Theorem along with an infinite family of generalizations.
A finite form of de Finettis representation theorem is established using elementary information-theoretic tools: The distribution of the first $k$ random variables in an exchangeable binary vector of length $ngeq k$ is close to a mixture of product distributions. Closeness is measured in terms of the relative entropy and an explicit bound is provided.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
