Regular Expressions with Counting: Weak versus Strong Determinism

DOI10.1137/100814196zbMath1252.68146MaRDI QIDQ5891559

Wim Martens, Marc Gyssens, Wouter Gelade

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

zbMATH Keywords

decision problems; counter automata; regular expressions with counting; strong and weak determinism

Mathematics Subject Classification ID

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