The complexity of SORE-definability problems
From MaRDI portal
Publication:5111236
Recommendations
- Complexity of decision problems for XML schemas and chain regular expressions
- Definability by weakly deterministic regular expressions with counters is decidable
- Mathematical Foundations of Computer Science 2004
- Deciding definability by deterministic regular expressions
- Deciding definability by deterministic regular expressions
Cites work
- scientific article; zbMATH DE number 1801402 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3560737 (Why is no real title available?)
- scientific article; zbMATH DE number 3251424 (Why is no real title available?)
- Checking determinism of regular expressions with counting
- Complexity of decision problems for XML schemas and chain regular expressions
- Deciding definability by deterministic regular expressions
- Deciding determinism of regular languages
- Deciding determinism of unary languages
- Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
- Definability by weakly deterministic regular expressions with counters is decidable
- Fast learning of restricted regular expressions and dtds
- One-unambiguity of regular expressions with numeric occurrence indicators
- One-unambiguous regular languages
- Regular Expressions with Numerical Constraints and Automata with Counters
- Regular expressions into finite automata
- Regular expressions with counting: weak versus strong determinism
- Relationships between nondeterministic and deterministic tape complexities
- The complexity of combinatorial problems with succinct input representation
- The membership problem for regular expressions with unordered concatenation and numerical constraints
- The parallel complexity of finite-state automata problems
- Unary pushdown automata and straight-line programs
Cited in
(2)
This page was built for publication: The complexity of SORE-definability problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111236)
