Počítačová lingvistika ve vztahu k informatice
Počítačová simulace
Počítačová simulace [Dokončení]
Point-fixe sur un ensemble restreint
Points and Triangles in the Plane and Halving Planes in Space.
Polar coordinate drawing of planar graphs with good angular resolution.
Polar cylinders of surfaces of revolution: Contour line determination.
Polyabelian loops and Boolean completeness
We consider the question of which loops are capable of expressing arbitrary Boolean functions through expressions of constants and variables. We call this property Boolean completeness. It is a generalization of functional completeness, and is intimately connected to the computational complexity of various questions about expressions, circuits, and equations defined over the loop. We say that a loop is polyabelian if it is an iterated affine quasidirect product of Abelian groups; polyabelianness...
Polygon placement under translation and rotation
Polygon Triangulation in O(n log log n) Time with Simple Data Structures.
Polygonizations of Point Sets in the Plane.
Polyhedral Line Transversals in Space.
Polynomial complexity of the Gilman-Maskit discreteness algorithm.
Polynomial languages with finite antidictionaries
We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.
Polynomial languages with finite antidictionaries
We tackle the problem of studying which kind of functions can occur as complexity functions of formal languages of a certain type. We prove that an important narrow subclass of rational languages contains languages of polynomial complexity of any integer degree over any non-trivial alphabet.
Polynomial size test sets for commutative languages
Polynomial time algorithms for two classes of subgraph problem
We design a O(n3) polynomial time algorithm for finding a (k-1)- regular subgraph in a k-regular graph without any induced star K1,3(claw-free). A polynomial time algorithm for finding a cubic subgraph in a 4-regular locally connected graph is also given. A family of k-regular graphs with an induced star K1,3 (k even, k ≥ 6), not containing any (k-1)-regular subgraph is also constructed.
Polynomial time bounded truth-table reducibilities to padded sets
We study bounded truth-table reducibilities to sets of small information content called padded (a set is in the class of all -padded sets, if it is a subset of ). This is a continuation of the research of reducibilities to sparse and tally sets that were studied in many previous papers (for a good survey see [HOW1]). We show necessary and sufficient conditions to collapse and separate classes of bounded truth-table reducibilities to padded sets. We prove that depending on two properties of a...
Polynomially Bounded Sequences and Polynomial Sequences
In this article, we formalize polynomially bounded sequences that plays an important role in computational complexity theory. Class P is a fundamental computational complexity class that contains all polynomial-time decision problems [11], [12]. It takes polynomially bounded amount of computation time to solve polynomial-time decision problems by the deterministic Turing machine. Moreover we formalize polynomial sequences [5].
Polynomials over the reals in proofs of termination : from theory to practice
This paper provides a framework to address termination problems in term rewriting by using orderings induced by algebras over the reals. The generation of such orderings is parameterized by concrete monotonicity requirements which are connected with different classes of termination problems: termination of rewriting, termination of rewriting by using dependency pairs, termination of innermost rewriting, top-termination of infinitary rewriting, termination of context-sensitive rewriting, etc. We...