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 complexity; transformations; regular expressions; finite automata; descriptional complexity; formal language problems; operation problems

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q19: Descriptive complexity and finite models

Related Items

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

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