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
• 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

• A quantum model for synchronizing finite state transition systems [0.0]
  We propose a quantum model for finding a resetting input sequence (RS) which can take a finite state transition system (FA) independent of its current state.<n>We represent the FA states, inputs, and transition function in quantum space.<n>As a proof of concept we provide results of several simulated FAs on a quantum simulator.
  arXiv  Detail & Related papers  (2026-07-08T03:27:19Z)
• On the Statistical Query Complexity of Learning Semiautomata: a Random Walk Approach [59.589793281734636]
  We show that Statistical Query hardness can be established when both the alphabet size and input length are in the number of states.<n>Our result is derived solely from the internal state-transition structure of semiautomata.
  arXiv  Detail & Related papers  (2025-10-05T09:35:35Z)
• Programmable Anyon Mobility through Higher Order Cellular Automata [16.86899900829509]
  Controlling anyon mobility is critical for robust quantum memory and understanding symmetry-enriched topological phases with subsystem symmetries.<n>We introduce higher-order cellular automata (HOCA) -- a powerful computer science tool -- to SET physics.<n>First, we design finite-depth HOCA-controlled unitary quantum circuits, yielding exactly solvable SET models with Abelian anyons and all possible locally generated subsystem symmetries.
  arXiv  Detail & Related papers  (2025-08-19T15:53:45Z)
• Critical Thinking: Which Kinds of Complexity Govern Optimal Reasoning Length? [72.70486097967124]
  We formalize a framework using deterministic finite automata (DFAs) We show that there exists an optimal amount of reasoning tokens such that the probability of producing a correct solution is maximized. We then demonstrate an implication of these findings: being able to predict the optimal number of reasoning tokens for new problems and filtering out non-optimal length answers results in consistent accuracy improvements.
  arXiv  Detail & Related papers  (2025-04-02T17:45:58Z)
• What is the relation between Slow Feature Analysis and the Successor Representation? [0.0]
  Slow feature analysis (SFA) is an unsupervised method for extracting representations from time series data. The successor representation (SR) is a method for representing states in a Markov decision process (MDP) based on transition statistics. This work studies their connection along these two axes.
  arXiv  Detail & Related papers  (2024-09-25T14:57:07Z)
• 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.