The complexity of regular(-like) expressions
From MaRDI portal
Publication:2909093
Recommendations
- The complexity of regular(-like) expressions
- Descriptional complexity of deterministic regular expressions
- Mathematical Foundations of Computer Science 2004
- On regular expression proof complexity
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- Towards a theory of complexity of regular languages
- scientific article; zbMATH DE number 7315105
- scientific article; zbMATH DE number 3843141
- Complexity of suffix-free regular languages
- Complexity of suffix-free regular languages
Cites work
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 5254145 (Why is no real title available?)
- scientific article; zbMATH DE number 3291134 (Why is no real title available?)
- scientific article; zbMATH DE number 3310089 (Why is no real title available?)
- scientific article; zbMATH DE number 3366846 (Why is no real title available?)
- A Procedure for Checking Equality of Regular Expressions
- A logical calculus of the ideas immanent in nervous activity
- A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
- A note on the space complexity of some decision problems for finite automata
- Algorithms for determining relative star height and star height
- Complexity measures for regular expressions
- Computingϵ-Free NFA from Regular Expressions inO(nlog2(n)) Time
- Derivatives of Regular Expressions
- Efficient simulation of finite automata by neural nets
- Follow automata.
- From regular expressions to deterministic automata
- Language operations with regular expressions of polynomial size
- NORMALIZED EXPRESSIONS AND FINITE AUTOMATA
- Partial derivatives of regular expressions and finite automaton constructions
- Programming Techniques: Regular expression search algorithm
- Rankings of Graphs
- Regular expressions into finite automata
- THE ABSTRACT THEORY OF AUTOMATA
- The complexity of restricted regular expressions and the synthesis problem for finite automata
- The loop complexity of pure-group events
- Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
- Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions
Cited in
(17)- A hitchhiker's guide to descriptional complexity through analytic combinatorics
- scientific article; zbMATH DE number 2201362 (Why is no real title available?)
- On classes of tractable unrestricted regular expressions
- Deciding determinism of unary languages
- Expressive capacity of subregular expressions
- Regular expression length via arithmetic formula complexity
- Concatenation-free languages
- Descriptional complexity of deterministic regular expressions
- Implication of regular expressions
- The complexity of regular(-like) expressions
- Expressive capacity of concatenation freeness
- Simply typed convertibility is \textsc{Tower}-complete even for safe lambda-terms
- Manipulation of regular expressions using derivatives: an overview
- Regular expressions: new results and open problems
- On regular expression proof complexity
- Language operations with regular expressions of polynomial size
- Tight Bounds on the Descriptional Complexity of Regular Expressions
This page was built for publication: The complexity of regular(-like) expressions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2909093)
