THE COMPLEXITY OF REGULAR(-LIKE) EXPRESSIONS

DOI10.1142/S0129054111008866zbMath1252.68174MaRDI QIDQ2909093

Martin Kutrib, Markus Holzer

Publication date: 29 August 2012

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

computational complexitytransformationsregular expressionsfinite automatadescriptional complexityformal language problemsoperation problems

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Descriptive complexity and finite models (68Q19)

Related Items

Manipulation of regular expressions using derivatives: an overview, Expressive Capacity of Concatenation Freeness, Deciding determinism of unary languages, A hitchhiker's guide to descriptional complexity through analytic combinatorics, Regular expression length via arithmetic formula complexity, Expressive capacity of subregular expressions, Concatenation-free languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• From regular expressions to deterministic automata
• Partial derivatives of regular expressions and finite automaton constructions
• 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
• Algorithms for determining relative star height and star height
• A note on the space complexity of some decision problems for finite automata
• Complexity measures for regular expressions
• Regular expressions into finite automata
• Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions
• Follow automata.
• Language operations with regular expressions of polynomial size
• THE ABSTRACT THEORY OF AUTOMATA
• Efficient simulation of finite automata by neural nets
• Rankings of Graphs
• Computingϵ-Free NFA from Regular Expressions inO(nlog²(n)) Time
• NORMALIZED EXPRESSIONS AND FINITE AUTOMATA
• A Procedure for Checking Equality of Regular Expressions
• Programming Techniques: Regular expression search algorithm
• The loop complexity of pure-group events
• Derivatives of Regular Expressions
• A logical calculus of the ideas immanent in nervous activity
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata