Regular Expressions with Counting: Weak versus Strong Determinism
From MaRDI portal
Publication:5891559
DOI10.1137/100814196zbMath1252.68146MaRDI QIDQ5891559
Wouter Gelade, Wim Martens, Marc Gyssens
Publication date: 30 May 2012
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/bf5a4911d3999ab6e8b2460a04577d60326ea513
68Q45: Formal languages and automata
20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
68Q19: Descriptive complexity and finite models
Related Items
Unnamed Item, Closure properties and descriptional complexity of deterministic regular expressions, Deciding determinism of regular languages, Annotated regular expressions and input-driven languages, Deciding determinism of unary languages, Deterministic regular expressions with back-references, Checking determinism of regular expressions with counting, Deciding definability by deterministic regular expressions, Efficient testing and matching of deterministic regular expressions, Definability by Weakly Deterministic Regular Expressions with Counters is Decidable