Deciding Definability by Deterministic Regular Expressions

DOI10.1007/978-3-642-37075-5_19zbMath1260.68199OpenAlexW2603910788MaRDI QIDQ4910426

Claire David, Katja Losemann, Wojciech Czerwiński, 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

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

Related Items (10)

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 ⋮ Deciding determinism of unary languages ⋮ Schemas for unordered XML on a DIME ⋮ Conjunctive query containment over trees using schema information ⋮ Deciding determinism of regular languages ⋮ Complexity of universality and related problems for partially ordered NFAs ⋮ Unnamed Item

This page was built for publication: Deciding Definability by Deterministic Regular Expressions