Search results for "Formal Language"
showing 10 items of 357 documents
Towards a Theory of Life
2015
In this paper, I set out the contributions made by some European biologists, as well as other more heterodox ones, to the recent development of theoretical thinking in biology. Theoretical biology is a relatively new discipline when compared with theoretical physics, in part because the formal languages of logic and computing which it uses have only emerged recently. Finally, I suggest that in order to build a theory of life we need to combine a cell theory based on a proper description of the laws that map the genotype in the phenotype and vice versa with the laws of evolution. Only then will we be able to properly explain the transformation and complexity of living things.
A challenging family of automata for classical minimization algorithms
2010
In this paper a particular family of deterministic automata that was built to reach the worst case complexity of Hopcroft's state minimization algorithm is considered. This family is also challenging for the two other classical minimization algorithms: it achieves the worst case for Moore's algorithm, as a consequence of a result by Berstel et al., and is of at least quadratic complexity for Brzozowski's solution, which is our main contribution. It therefore constitutes an interesting family, which can be useful to measure the efficiency of implementations of well-known or new minimization algorithms.
An Analysis of Bilevel Linear Programming Solving Parameters Based on Factoraggregation Approach
2013
We introduce the notion of factoraggregation,which is a special construction of general aggregation operators, and apply it for an analysis of optimal solution parameters for bilevel linear programming problems. The aggregation observes lower level objective functions considering the classes of equivalence generated by an objective function on the upper level. The proposed method is illustrated with numerical and graphical examples.
Conformal equivalence of visual metrics in pseudoconvex domains
2017
We refine estimates introduced by Balogh and Bonk, to show that the boundary extensions of isometries between smooth strongly pseudoconvex domains in $\C^n$ are conformal with respect to the sub-Riemannian metric induced by the Levi form. As a corollary we obtain an alternative proof of a result of Fefferman on smooth extensions of biholomorphic mappings between pseudoconvex domains. The proofs are inspired by Mostow's proof of his rigidity theorem and are based on the asymptotic hyperbolic character of the Kobayashi or Bergman metrics and on the Bonk-Schramm hyperbolic fillings.
The Reconstruction of Polyominoes from Approximately Orthogonal Projections
2001
The reconstruction of discrete two-dimensional pictures from their projection is one of the central problems in the areas of medical diagnostics, computer-aided tomography, pattern recognition, image processing, and data compression. In this note, we determine the computational complexity of the problem of reconstruction of polyominoes from their approximately orthogonal projections. We will prove that it is NP-complete if we reconstruct polyominoes, horizontal convex polyominoes and vertical convex polyominoes. Moreover we will give the polynomial algorithm for the reconstruction of hv-convex polyominoes that has time complexity O(m3n3).
AC is Equivalent to the Coherence Principle. Corrigendum to my Paper "Induction Principles for Sets"
2009
Theorem 3.7 of [1] is corrected. Two coherence principles and the ultrafilter property for partial functions contained in a relation are formulated. The equivalence of the coherent principles with AC and the equivalence of the ultrafilter property with BPI is shown.
The double-incompleteness theorem
1976
Let T be a strong enough theory, and M - its metatheory, both are consistent. Then there is a closed arithmetical formula H that is undecidable in T, but one cannot prove in M neither that H is T-unprovable, nor that H is T-unrefutable. For English translation and proof, see K. Podnieks What is mathematics: Godel's theorem and around.
Some Algebraic Properties of Machine Poset of Infinite Words
2008
The complexity of infinite words is considered from the point of view of a transformation with a Mealy machine that is the simplest model of a finite automaton transducer. We are mostly interested in algebraic properties of the underlying partially ordered set. Results considered with the existence of supremum, infimum, antichains, chains and density aspects are investigated.
Deciding properties of integral relational automata
1994
This paper investigates automated model checking possibilities for CTL* formulae over infinite transition systems represented by relational automata (RA). The general model checking problem for CTL* formulae over RA is shown undecidable, the undecidability being observed already on the class of Restricted CTL formulae. The decidability result, however, is obtained for another substantial subset of the logic, called A-CTL*+, which includes all ”linear time” formulae.
Minimal Büchi Automata for Certain Classes of LTL Formulas
2009
In this paper we calculate the minimal number of states of Buchi automata which encode some classes of linear temporal logic (LTL) formulas that are frequently used in model checking. Our results may be used for verification of the quality of algorithms which automatically translate LTL formulas into Buchi automata and for improving the quality and speed of such translators. In the last section of this paper we compare our lower-bound estimations to Buchi automata generated by two currently used translators: LTL2BA and SPOT.