On the Complexity of Symbolic Finite-State Automata

• URL: http://arxiv.org/abs/2011.05389v3
• Date: Fri, 2 Jul 2021 12:57:45 GMT
• Title: On the Complexity of Symbolic Finite-State Automata
• Authors: Dana Fisman and Hadar Frenkel and Sandra Zilles
• Abstract summary: 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.
• Score: 7.386725677365395
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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: the number of states, the maximal number of transitions exiting a state, and the size of the most complex transition predicate. 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.

Related papers

• Inducing Systematicity in Transformers by Attending to Structurally Quantized Embeddings [60.698130703909804]
  Transformers generalize to novel compositions of structures and entities after being trained on a complex dataset. We propose SQ-Transformer that explicitly encourages systematicity in the embeddings and attention layers. We show that SQ-Transformer achieves stronger compositional generalization than the vanilla Transformer on multiple low-complexity semantic parsing and machine translation datasets.
  arXiv  Detail & Related papers  (2024-02-09T15:53:15Z)
• 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)
• 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)
• 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)
• Automata Cascades: Expressivity and Sample Complexity [90.53326983143644]
  We show that cascades allow for describing the sample complexity of automata in terms of their components. Our results show that one can in principle learn automata with infinite input alphabets and a number of states that is exponential in the amount of data available.
  arXiv  Detail & Related papers  (2022-11-25T11:02:33Z)
• State complexity of one-way quantum finite automata together with classical states [2.3097706741644686]
  One-way quantum finite automata together with classical states (1QFAC) proposed in [Journal of Computer and System Sciences 81(2) 359-375] As a quantum-classical hybrid model, 1QFAC recognize all regular languages. It was shown that the state complexity of 1QFAC for some languages is essentially superior to that of DFA and other 1QFA.
  arXiv  Detail & Related papers  (2021-12-07T15:00:18Z)
• 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)
• 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)
• Glushkov's construction for functional subsequential transducers [91.3755431537592]
  Glushkov's construction has many interesting properties and they become even more evident when applied to transducers. Special flavour of regular expressions is introduced, which can be efficiently converted to $epsilon$-free functional subsequential weighted finite state transducers.
  arXiv  Detail & Related papers  (2020-08-05T17:09:58Z)

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.