The complexity of regular(-like) expressions
From MaRDI portal
Publication:2909093
DOI10.1142/S0129054111008866zbMATH Open1252.68174MaRDI QIDQ2909093FDOQ2909093
Publication date: 29 August 2012
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
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
computational complexitytransformationsdescriptional complexityfinite automataregular expressionsformal language problemsoperation problems
Cites Work
- Title not available (Why is that?)
- Complexity measures for regular expressions
- THE ABSTRACT THEORY OF AUTOMATA
- Title not available (Why is that?)
- Title not available (Why is that?)
- Derivatives of Regular Expressions
- Partial derivatives of regular expressions and finite automaton constructions
- Rankings of Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- A logical calculus of the ideas immanent in nervous activity
- Follow automata.
- Title not available (Why is that?)
- Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
- A note on the space complexity of some decision problems for finite automata
- Programming Techniques: Regular expression search algorithm
- Language operations with regular expressions of polynomial size
- Regular expressions into finite automata
- Computingϵ-Free NFA from Regular Expressions inO(nlog2(n)) Time
- From regular expressions to deterministic automata
- Algorithms for determining relative star height and star height
- A Procedure for Checking Equality of Regular Expressions
- NORMALIZED EXPRESSIONS AND FINITE AUTOMATA
- The loop complexity of pure-group events
- Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions
- Efficient simulation of finite automata by neural nets
- A lower bound on the size of \(\varepsilon\)-free NFA corresponding to a regular expression
- The complexity of restricted regular expressions and the synthesis problem for finite automata
Cited In (14)
- Title not available (Why is that?)
- A hitchhiker's guide to descriptional complexity through analytic combinatorics
- 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
- The complexity of regular(-like) expressions
- 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
- Language operations with regular expressions of polynomial size
- Tight Bounds on the Descriptional Complexity of Regular Expressions
- Expressive Capacity of Concatenation Freeness
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)
