An Analysis of On-the-fly Determinization of Finite-state Automata

• URL: http://arxiv.org/abs/2308.14077v1
• Date: Sun, 27 Aug 2023 11:51:27 GMT
• Title: An Analysis of On-the-fly Determinization of Finite-state Automata
• Authors: Ivan Baburin and Ryan Cotterell
• Abstract summary: 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.
• Score: 65.268245109828
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper we establish an abstraction of on-the-fly determinization of finite-state automata using transition monoids and demonstrate how it can be applied to bound the asymptotics. We present algebraic and combinatorial properties that are sufficient for a polynomial state complexity of the deterministic automaton constructed on-the-fly. A special case of our findings is that automata with many non-deterministic transitions almost always admit a determinization of polynomial complexity. Furthermore, we extend our ideas to weighted finite-state automata.

Related papers

• Complexity-constrained quantum thermodynamics [0.2796197251957244]
  We show that the minimum thermodynamic work required to reset an arbitrary state, via a complexity-constrained process, is quantified by the state's complexity entropy. The complexity entropy quantifies a trade-off between the work cost and complexity cost of resetting a state. We identify information-theoretic applications of the complexity entropy.
  arXiv  Detail & Related papers  (2024-03-07T19:00:01Z)
• Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata [0.0]
  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.
  arXiv  Detail & Related papers  (2023-11-16T15:52:24Z)
• Edge of entanglement in non-ergodic states: a complexity parameter formulation [0.0]
  We analyze the subsystem size scaling of the entanglement entropy of a non-ergodic pure state. A rescaling of the complexity parameter helps us to identify the critical regime for the entanglement entropy of a broad range of pure non-ergodic states.
  arXiv  Detail & Related papers  (2023-10-19T14:52:43Z)
• Universality of critical dynamics with finite entanglement [68.8204255655161]
  We study how low-energy dynamics of quantum systems near criticality are modified by finite entanglement. Our result establishes the precise role played by entanglement in time-dependent critical phenomena.
  arXiv  Detail & Related papers  (2023-01-23T19:23:54Z)
• 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)
• Circuit Complexity through phase transitions: consequences in quantum state preparation [0.0]
  We analyze the circuit complexity for preparing ground states of quantum many-body systems. In particular, how this complexity grows as the ground state approaches a quantum phase transition.
  arXiv  Detail & Related papers  (2023-01-11T19:00:10Z)
• Detailed Account of Complexity for Implementation of Some Gate-Based Quantum Algorithms [55.41644538483948]
  In particular, some steps of the implementation, as state preparation and readout processes, can surpass the complexity aspects of the algorithm itself. We present the complexity involved in the full implementation of quantum algorithms for solving linear systems of equations and linear system of differential equations.
  arXiv  Detail & Related papers  (2021-06-23T16:33:33Z)
• Fixed Depth Hamiltonian Simulation via Cartan Decomposition [59.20417091220753]
  We present a constructive algorithm for generating quantum circuits with time-independent depth. We highlight our algorithm for special classes of models, including Anderson localization in one dimensional transverse field XY model. In addition to providing exact circuits for a broad set of spin and fermionic models, our algorithm provides broad analytic and numerical insight into optimal Hamiltonian simulations.
  arXiv  Detail & Related papers  (2021-04-01T19:06:00Z)
• The Variational Method of Moments [65.91730154730905]
  conditional moment problem is a powerful formulation for describing structural causal parameters in terms of observables. Motivated by a variational minimax reformulation of OWGMM, we define a very general class of estimators for the conditional moment problem. We provide algorithms for valid statistical inference based on the same kind of variational reformulations.
  arXiv  Detail & Related papers  (2020-12-17T07:21:06Z)
• On the Complexity of Symbolic Finite-State Automata [7.386725677365395]
  We revisit the complexity of procedures on SFAs (such as intersection, emptiness, etc.) and analyze them according to the measures we find suitable for symbolic automata. We pay attention to the special forms of SFAs: normalized SFAs and neat SFAs, as well as to SFAs over a monotonic effective Boolean algebra.
  arXiv  Detail & Related papers  (2020-11-10T20:55:55Z)

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.