COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA

DOI10.1142/S012905411000757XzbMath1213.68355MaRDI QIDQ3056281

Markus Lohrey

Publication date: 11 November 2010

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

zbMATH Keywords

regular expressionsstraight-line programsalgorithms on compressed strings

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42) Algorithms on strings (68W32)

Related Items (4)

Static analysis of XML security views and query rewriting ⋮ Compressed Membership in Automata with Compressed Labels ⋮ The complexity of compressed membership problems for finite automata ⋮ Leaf languages and string compression

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Knapsack problems for NL
• Finite complete rewriting systems and the complexity of word problem
• On the complexity of iterated shuffle
• A uniform method for proving lower bounds on the computational complexity of logical theories
• Pattern matching and membership for hierarchical message sequence charts
• A note on the space complexity of some decision problems for finite automata
• A polynomial algorithm for deciding bisimilarity of normed context-free processes
• A PTIME-complete matching problem for SLP-compressed words
• Alternation
• A universal algorithm for sequential data compression
• Word Problems and Membership Problems on Compressed Words

This page was built for publication: COMPRESSED MEMBERSHIP PROBLEMS FOR REGULAR EXPRESSIONS AND HIERARCHICAL AUTOMATA