Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata

• URL: http://arxiv.org/abs/2311.09979v1
• Date: Thu, 16 Nov 2023 15:52:24 GMT
• Title: Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata
• Authors: Tomoyuki Yamakami
• Abstract summary: Nondeterministic finite automata have at most "one" (unambiguous), "polynomially many" (few) accepting paths, or computation/few paths leading to each fixed configuration. We prove with no unproven assumptions that some of these variants are different in computational power from each other.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Nonuniform families of polynomial-size finite automata, which are series of indexed finite automata having polynomially many inner states, are used in the past literature to solve nonuniform families of promise decision problems. Among such nonuniform families of finite automata, we focus our attention, in particular, on the variants of nondeterministic finite automata, which have at most "one" (unambiguous), "polynomially many" (few) accepting computation paths, or unambiguous/few computation paths leading to each fixed configuration. When such machines are limited to make only one-way head moves, we can prove with no unproven hardness assumptions that some of these variants are different in computational power from each other. As for two-way machines restricted to instances of polynomially-bounded length, families of two-way polynomial-size nondeterministic finite automata are equivalent in power to families of polynomial-size unambiguous finite automata.

Related papers

• MultiMax: Sparse and Multi-Modal Attention Learning [60.49318008131978]
  SoftMax is a ubiquitous ingredient of modern machine learning algorithms. We show that sparsity can be achieved by a family of SoftMax variants, but they often require an alternative loss function and do not preserve multi-modality. We propose MultiMax, which adaptively modulates the output distribution according to input entry range.
  arXiv  Detail & Related papers  (2024-06-03T10:51:43Z)
• On Maximal Families of Binary Polynomials with Pairwise Linear Common Factors [1.249418440326334]
  We characterize maximal families over the binary field $mathbbF$. Our findings prompt several more open questions, which we plan to address in an extended version of this work.
  arXiv  Detail & Related papers  (2024-05-14T16:30:28Z)
• Structure of universal formulas [13.794391803767617]
  We introduce a hierarchy of classes connecting the global approximability property to the weaker property of infinite VC dimension. We show that fixed-size neural networks with not more than one layer of neurons having activations cannot approximate functions on arbitrary finite sets. We give examples of functional families, including two-hidden-layer neural networks, that approximate functions on arbitrary finite sets, but fail to do that on the whole domain of definition.
  arXiv  Detail & Related papers  (2023-11-07T11:50:25Z)
• Higher Level Completeness for Permutation Polynomials [0.0]
  Generalising the concept of a complete permutation over a finite field, we define completness to level $kge1$ in fields of odd characteristics. We construct two families of characteristics that satisfy the condition of high level completeness for all finite fields.
  arXiv  Detail & Related papers  (2023-10-19T04:47:53Z)
• An Analysis of On-the-fly Determinization of Finite-state Automata [65.268245109828]
  We establish an abstraction of on-the-fly determinization of finite-state automata and demonstrate how it can be applied to bound the automatons. A special case of our findings is that automata with many non-deterministic transitions almost always admit a determinization of complexity.
  arXiv  Detail & Related papers  (2023-08-27T11:51:27Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Poly-NL: Linear Complexity Non-local Layers with Polynomials [76.21832434001759]
  We formulate novel fast NonLocal blocks, capable of reducing complexity from quadratic to linear with no loss in performance. The proposed method, which we dub as "Poly-NL", is competitive with state-of-the-art performance across image recognition, instance segmentation, and face detection tasks.
  arXiv  Detail & Related papers  (2021-07-06T19:51:37Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• Polymers for Extreme Conditions Designed Using Syntax-Directed Variational Autoencoders [53.34780987686359]
  Machine learning tools are now commonly employed to virtually screen material candidates with desired properties. This approach is inefficient, and severely constrained by the candidates that human imagination can conceive. We utilize syntax-directed variational autoencoders (VAE) in tandem with Gaussian process regression (GPR) models to discover polymers expected to be robust under three extreme conditions.
  arXiv  Detail & Related papers  (2020-11-04T21:36:59Z)
• GAPS: Generator for Automatic Polynomial Solvers [39.33174230839823]
  Given a system repeated with different coefficient instances, the traditional Gr"obner basis or normal form based solution is very inefficient. By precomputing such structures offline, Gr"obner basis as well as the system solutions can be solved automatically and efficiently online. The most recent tool autogen from Larsson et al. is a representative of these tools with state-of-the-art performance in solver efficiency.
  arXiv  Detail & Related papers  (2020-04-24T14:11:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.