Related papers: Real-time Regular Expression Matching

Real-time Regular Expression Matching

URL: http://arxiv.org/abs/2308.10208v1
Date: Sun, 20 Aug 2023 09:25:40 GMT
Title: Real-time Regular Expression Matching
Authors: Alexandra Bernadotte
Abstract summary: This paper is devoted to finite state automata, regular expression matching, pattern recognition, and the exponential blow-up problem. This paper presents a theoretical and hardware solution to the exponential blow-up problem for some complicated classes of regular languages.
Score: 65.268245109828
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: This paper is devoted to finite state automata, regular expression matching, pattern recognition, and the exponential blow-up problem, which is the growing complexity of automata exponentially depending on regular expression length. This paper presents a theoretical and hardware solution to the exponential blow-up problem for some complicated classes of regular languages, which caused severe limitations in Network Intrusion Detection Systems work. The article supports the solution with theorems on correctness and complexity.

Related papers

Explicit Solution Equation for Every Combinatorial Problem via Tensor Networks: MeLoCoToN [55.2480439325792]
We show that every computation problem has an exact explicit equation that returns its solution. We present a method to obtain an equation that solves exactly any problem, both inversion, constraint satisfaction and optimization.
arXiv Detail & Related papers (2025-02-09T18:16:53Z)
From Exponential to Polynomial Complexity: Efficient Permutation Counting with Subword Constraints [0.0]
Counting distinct permutations with replacement, especially when involving multiple subwords, is a longstanding challenge in analysis. This paper introduces a novel framework that presents closed-form formulas for calculating distinct permutations with replacement. We then extend our foundational formula to handle multiple subwords through the development of an additional formula.
arXiv Detail & Related papers (2024-11-23T19:52:11Z)
MathGAP: Out-of-Distribution Evaluation on Problems with Arbitrarily Complex Proofs [80.96119560172224]
Large language models (LLMs) can solve arithmetic word problems with high accuracy, but little is known about how well they generalize to problems that are more complex than the ones on which they have been trained. We present a framework for evaluating LLMs on problems with arbitrarily complex arithmetic proofs, called MathGAP.
arXiv Detail & Related papers (2024-10-17T12:48:14Z)
Learning K-U-Net with constant complexity: An Application to time series forecasting [1.8816077341295625]
Training deep models for time series forecasting is a critical task with an inherent challenge of time complexity. We introduce a new exponentially weighted gradient descent algorithm designed to achieve constant time complexity in deep learning models.
arXiv Detail & Related papers (2024-10-03T12:35:17Z)
Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems [0.20971479389679337]
Combination of Quantum Minimum Finding and dynamic programming has proved particularly efficient in improving the complexity of NP-hard problems. In this paper, we provide a bounded-error hybrid algorithm that achieves such an improvement for a broad class of NP-hard single-machine scheduling problems. Our algorithm reduces the exponential-part complexity compared to the best-known classical algorithm, sometimes at the cost of an additional pseudo-polynomial factor.
arXiv Detail & Related papers (2024-08-11T10:28:49Z)
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)
A Hybrid System for Systematic Generalization in Simple Arithmetic Problems [70.91780996370326]
We propose a hybrid system capable of solving arithmetic problems that require compositional and systematic reasoning over sequences of symbols. We show that the proposed system can accurately solve nested arithmetical expressions even when trained only on a subset including the simplest cases.
arXiv Detail & Related papers (2023-06-29T18:35:41Z)
A Fast Algorithm for Consistency Checking Partially Ordered Time [9.594432031144716]
We consider the problem of deciding if a (likely incomplete) description of a system of events is consistent. While the classical complexity of this problem has been fully settled, comparably little is known of the fine-grained complexity of POT. We construct a much faster algorithm with a run-time bounded by $O*((0.26n)n)$.
arXiv Detail & Related papers (2023-05-25T10:36:49Z)
Consistency of mechanistic causal discovery in continuous-time using Neural ODEs [85.7910042199734]
We consider causal discovery in continuous-time for the study of dynamical systems. We propose a causal discovery algorithm based on penalized Neural ODEs.
arXiv Detail & Related papers (2021-05-06T08:48:02Z)
Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
We study the issue of receiving infinite-length sequences from a recurrent language model. We propose two remedies which address inconsistency: consistent variants of top-k and nucleus sampling, and a self-terminating recurrent language model.
arXiv Detail & Related papers (2020-02-06T19:56:15Z)

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