The complexity of SORE-definability problems
From MaRDI portal
Publication:5111236
DOI10.4230/LIPICS.MFCS.2017.22zbMATH Open1441.68126MaRDI QIDQ5111236FDOQ5111236
Haiming Chen, Ping Lu, Zhilin Wu
Publication date: 26 May 2020
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Checking determinism of regular expressions with counting
- One-unambiguity of regular expressions with numeric occurrence indicators
- Relationships between nondeterministic and deterministic tape complexities
- Definability by Weakly Deterministic Regular Expressions with Counters is Decidable
- Regular Expressions with Numerical Constraints and Automata with Counters
- Deciding Definability by Deterministic Regular Expressions
- Deciding determinism of regular languages
- Regular expressions with counting: weak versus strong determinism
- Deciding determinism of unary languages
- Fast learning of restricted regular expressions and dtds
- Complexity of Decision Problems for XML Schemas and Chain Regular Expressions
- Title not available (Why is that?)
- The complexity of combinatorial problems with succinct input representation
- One-unambiguous regular languages
- Regular expressions into finite automata
- The Membership Problem for Regular Expressions with Unordered Concatenation and Numerical Constraints
- The parallel complexity of finite-state automata problems
- Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
- Title not available (Why is that?)
- Unary Pushdown Automata and Straight-Line Programs
Cited In (1)
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)
