Source author record

Paul C. Bell

Paul C. Bell appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Formal Languages and Automata Theory Computation and Language Computational Complexity Computational Geometry math.CO math.GR

Catalog footprint

What is connected

4works

6topics

2close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs

We show the surprising result that the cutpoint isolation problem is decidable for Probabilistic Finite Automata (PFA) where input words are taken from a letter-bounded context-free language. A context-free language $\mathcal{L}$ is letter-bounded when $\mathcal{L} \subseteq a_1^*a_2^* \cdots a_\ell^*$ for some finite $\ell > 0$ where each letter is distinct. A cutpoint is isolated when it cannot be approached arbitrarily closely. The decidability of this problem is in marked contrast to the situation for the (strict) emptiness problem for PFA which is undecidable under the even more severe restrictions of PFA with polynomial ambiguity, commutative matrices and input over a letter-bounded language as well as to the injectivity problem which is undecidable for PFA over letter-bounded languages. We provide a constructive nondeterministic algorithm to solve the cutpoint isolation problem, which holds even when the PFA is exponentially ambiguous. We also show that the problem is at least NP-hard and use our decision procedure to solve several related problems.

preprint2020arXiv

Polynomially Ambiguous Probabilistic Automata on Restricted Languages

We consider the computability and complexity of decision questions for Probabilistic Finite Automata (PFA) with sub-exponential ambiguity. We show that the emptiness problem for strict and non-strict cut-points of polynomially ambiguous commutative PFA remains undecidable, implying that the problem is undecidable when inputs are from a letter monotonic language. We show that the problem remains undecidable over a binary input alphabet when the input word is over a bounded language, in the noncommutative case. In doing so, we introduce a new technique based upon the Turakainen construction of a PFA from a Weighted Finite Automata which can be used to generate PFA of lower dimensions and of subexponential ambiguity. We also study freeness/injectivity problems for polynomially ambiguous PFA and study the border of decidability and tractability for various cases.

preprint2020arXiv

Towards Uniform Online Spherical Tessellations

The problem of uniformly placing N points onto a sphere finds applications in many areas. For example, points on the sphere correspond to unit quaternions as well as to the group of rotations SO(3) and the online version of generating uniform rotations (known as "incremental generation") plays a crucial role in a large number of engineering applications ranging from robotics and aeronautics to computer graphics. An online version of this problem was recently studied with respect to the gap ratio as a measure of uniformity. The first online algorithm of Chen et al. was upper-bounded by 5.99 and later improved to 3.69, which is achieved by considering a circumscribed dodecahedron followed by a recursive decomposition of each face. In this paper we provide a more efficient tessellation technique based on the regular icosahedron, which improves the upper-bound for the online version of this problem, decreasing it to approximately 2.84. Moreover, we show that the lower bound for the gap ratio of placing at least three points is the golden ratio, approx. 1.618, and for at least four points is no less than 1.726.

preprint2010arXiv

The Identity Correspondence Problem and its Applications

In this paper we study several closely related fundamental problems for words and matrices. First, we introduce the Identity Correspondence Problem (ICP): whether a finite set of pairs of words (over a group alphabet) can generate an identity pair by a sequence of concatenations. We prove that ICP is undecidable by a reduction of Post's Correspondence Problem via several new encoding techniques. In the second part of the paper we use ICP to answer a long standing open problem concerning matrix semigroups: "Is it decidable for a finitely generated semigroup S of square integral matrices whether or not the identity matrix belongs to S?". We show that the problem is undecidable starting from dimension four even when the number of matrices in the generator is 48. From this fact, we can immediately derive that the fundamental problem of whether a finite set of matrices generates a group is also undecidable. We also answer several question for matrices over different number fields. Apart from the application to matrix problems, we believe that the Identity Correspondence Problem will also be useful in identifying new areas of undecidable problems in abstract algebra, computational questions in logic and combinatorics on words.

Institution

Affiliation not imported yet

This author record came from a source that does not expose affiliation metadata. Once the author claims the profile or we enrich the record from another provider, this section will link to the concrete institution.

Topic footprint