1,721,018 research outputs found
The commutative equivalence of bounded context-free and regular languages
No full textIt is proved that every bounded context-free language L is commutatively equivalent to a regular language L', that is, there exists a bijection from L onto L' preserving the Parikh vectors of words
Combinatorial principles in elementary number theory
No full textWe prove that the theory IΔ0, extended by a weak version of the Δ0-Pigeonhole Principle, proves that every integer is the sum of four squares (Lagrange's theorem). Since the required weak version is derivable from the theory IΔ0 + ∀x (xlog(x) exists), our results give a positive answer to a question of Macintyre (1986). In the rest of the paper we consider the number-theoretical consequences of a new combinatorial principle, the ‘Δ0-Equipartition Principle’ (Δ0EQ). In particular we give a new proof, which can be formalized in IΔ0 + Δ0EQ, of the fact that every prime of the form 4n + 1 is the sum of two squares
On the commutative equivalence of bounded context-free and regular languages: Thesemi-linear case
No full textOn the cop number of a graph
No full textThe cop number c(G) of a graph G is an invariant connected with the genus and the girth. We prove that for a fixed k there is a polynomial-time algorithm which decides whether c(G) ≤ k. This settles a question of T. Andreae. Moreover, we show that every graph is topologically equivalent to a graph with c ≤ 2. Finally we consider a pursuit-evasion problem in Littlewood′s miscellany. We prove that two lions are not always sufficient to catch a man on a plane graph, provided the lions and the man have equal maximum speed. We deal both with a discrete motion (from vertex to vertex) and with a continuous motion. The discrete case is solved by showing that there are plane graphs of cop number 3 such that all the edges can be represented by straight segments of the same length
Some new results on easy lambda-terms
No full textGiven two closed lambda-terms A and B we consider the question whether the equation A = B is consistent with the lambda-beta-calculus. In general the problem is undecidable. However if A is a 0-term we can give good sufficient conditions for the consistency. This allows us to prove some counterintuitive results such as: (1) there is a closed lambda-term X which can be consistently equated to every closed lambda-term with the exception of the identity lambda x.x. (2) there is a closed lambda-term which can be consistenlty equated to every closed normal form, but not to the Curry fixed point operator Y
On the generalization of Higman and Kruskal's theorems to regular languages and rational trees
No full textIn this paper we give new extensions and generalizations of the Higman and Kruskal theorems. We start with an alphabet A equipped by a well quasi-order (wqo) less than or equal to and prove that a natural extension of this order to the family of regular languages over A is a wqo. A similar extension is given for rational trees with labels in A, proving that also in this case one obtains a wqo. We prove that the above wqo's are effectively computable, that is, for any two regular languages (rational trees) one can decide whether they are comparable in the given wqo
The omega rule is \Pi^1_1-complete in the lambda-calculus
No full textWe give a many-one reduction of the set of true \Pi^1_1 sentences to the set of consequences of the lambda-calculus with the omega-rule. This solves in the affirmative a long-standing problem of H. Barendregt (1975). © Springer-Verlag Berlin Heidelberg 2007
- …
