Deciding definability by deterministic regular expressions

DOI10.1007/978-3-642-37075-5_19MaRDI QIDQ4910426zbMATH OpenOpenAlexFDO

Authors Wojciech Czerwiński, Claire David, Katja Losemann, Wim Martens

Publication date 18 March 2013

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-37075-5_19

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Formal languages and automata (68Q45)

Recommendations

• Deciding definability by deterministic regular expressions
• Deciding determinism of regular languages
• Structure and Complexity of Some Subregular Language Families
• Definability by weakly deterministic regular expressions with counters is decidable
• Descriptional complexity of deterministic regular expressions

Cited in

(14)

• Conjunctive query containment over trees using schema information
• Complexity of universality and related problems for partially ordered NFAs
• Deciding definability by deterministic regular expressions
• Efficient testing and matching of deterministic regular expressions
• Closure properties and descriptional complexity of deterministic regular expressions
• A Compact Proof of Decidability for Regular Expression Equivalence
• Definability by weakly deterministic regular expressions with counters is decidable
• A Decision Procedure for Regular Expression Equivalence in Type Theory
• Deciding determinism of regular languages
• Decidability of regular language genus computation
• The complexity of SORE-definability problems
• Semantic flowers for good-for-games and deterministic automata
• Deciding determinism of unary languages
• Schemas for unordered XML on a DIME

This page was built for publication: Deciding definability by deterministic regular expressions

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