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 expressions; straight-line programs; algorithms on compressed strings

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

68W32: Algorithms on strings

Related Items

Static analysis of XML security views and query rewriting, Leaf languages and string compression, Compressed Membership in Automata with Compressed Labels

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