Regular Expressions with Counting: Weak versus Strong Determinism

DOI10.1137/100814196zbMath1252.68146OpenAlexW2041340246MaRDI 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

zbMATH Keywords

decision problemscounter automataregular expressions with countingstrong and weak determinism

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Descriptive complexity and finite models (68Q19)

Related Items (12)

Closure properties and descriptional complexity of deterministic regular expressions ⋮ Deciding definability by deterministic regular expressions ⋮ Efficient testing and matching of deterministic regular expressions ⋮ Definability by Weakly Deterministic Regular Expressions with Counters is Decidable ⋮ Fast matching of regular patterns with synchronizing counting ⋮ Deciding determinism of unary languages ⋮ A Trichotomy for Regular Trail Queries ⋮ Deciding determinism of regular languages ⋮ Unnamed Item ⋮ Deterministic regular expressions with back-references ⋮ Annotated regular expressions and input-driven languages ⋮ Checking determinism of regular expressions with counting

This page was built for publication: Regular Expressions with Counting: Weak versus Strong Determinism