Regular Expressions with Numerical Constraints and Automata with Counters

DOI10.1007/978-3-642-03466-4_15MaRDI QIDQ3393412zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Dag Hovland

Publication date 20 August 2009

Published in Theoretical Aspects of Computing - ICTAC 2009 (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/1956/3628

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• The membership problem for regular expressions with unordered concatenation and numerical constraints
• Regular Expressions with Counting: Weak versus Strong Determinism
• Regular expressions with counting: weak versus strong determinism
• Symbolic automata constraint solving
• Constrained expressions and their derivatives

Cited in

(13)

• Deriving generic bounds for time-series constraints based on regular expressions characteristics
• Counting with range concatenation grammars
• When bounds consistency implies domain consistency for regular counting constraints
• Deciding definability by deterministic regular expressions
• Closure properties and descriptional complexity of deterministic regular expressions
• The membership problem for regular expressions with unordered concatenation and numerical constraints
• Definability by weakly deterministic regular expressions with counters is decidable
• The tractability frontier for NFA minimization
• Constrained expressions and their derivatives
• The complexity of SORE-definability problems
• Regular Expressions with Counting: Weak versus Strong Determinism
• Fast matching of regular patterns with synchronizing counting
• Succinct determinisation of counting automata via sphere construction

This page was built for publication: Regular Expressions with Numerical Constraints and Automata with Counters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3393412)