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

• Conditional Distribution Quantization in Machine Learning [83.54039134248231]
  Conditional expectation mathbbE(Y mid X) often fails to capture the complexity of multimodal conditional distributions mathcalL(Y mid X) We propose using n-point conditional quantizations--functional mappings of X that are learnable via gradient descent--to approximate mathcalL(Y mid X)
  arXiv  Detail & Related papers  (2025-02-11T00:28:24Z)
• Fermionic cellular automata in one dimension [72.49909271232748]
  We consider quantum cellular automata for one-dimensional chains of Fermionic modes. A complete characterization of nearest-neighbours automata is given.
  arXiv  Detail & Related papers  (2025-01-09T16:22:15Z)
• 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)
• 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)
• 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.