Definability by Weakly Deterministic Regular Expressions with Counters is Decidable

DOI10.1007/978-3-662-48057-1_29zbMath1465.68159OpenAlexW2396856781MaRDI QIDQ2946353

Markus Latte, Matthias Niewerth

Publication date: 16 September 2015

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

Full work available at URL: https://doi.org/10.1007/978-3-662-48057-1_29

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (5)

Closure properties and descriptional complexity of deterministic regular expressions ⋮ Efficient testing and matching of deterministic regular expressions ⋮ Deciding determinism of unary languages ⋮ Unnamed Item ⋮ Deterministic regular expressions with back-references

Cites Work

• Closure properties and descriptional complexity of deterministic regular expressions
• Regular expressions into finite automata
• One-unambiguity of regular expressions with numeric occurrence indicators
• The Membership Problem for Regular Expressions with Unordered Concatenation and Numerical Constraints
• Descriptional Complexity of Deterministic Regular Expressions
• Checking Determinism of Regular Expressions with Counting
• Regular Expressions with Numerical Constraints and Automata with Counters
• Deciding Definability by Deterministic Regular Expressions
• Regular Expressions with Counting: Weak versus Strong Determinism
• One-unambiguous regular languages

This page was built for publication: Definability by Weakly Deterministic Regular Expressions with Counters is Decidable