Publication:5111236
From MaRDI portal
DOI10.4230/LIPIcs.MFCS.2017.22zbMath1441.68126MaRDI QIDQ5111236
Haiming Chen, Ping Lu, Zhilin Wu
Publication date: 26 May 2020
68Q45: Formal languages and automata
Cites Work
- Fast learning of restricted regular expressions and dtds
- Deciding determinism of regular languages
- Deciding the inequivalence of context-free grammars with 1-letter terminal alphapet is \(\sum ^ p_ 2\)-complete
- Deciding determinism of unary languages
- The complexity of combinatorial problems with succinct input representation
- The parallel complexity of finite-state automata problems
- Regular expressions into finite automata
- Checking determinism of regular expressions with counting
- One-unambiguity of regular expressions with numeric occurrence indicators
- Relationships between nondeterministic and deterministic tape complexities
- The Membership Problem for Regular Expressions with Unordered Concatenation and Numerical Constraints
- Definability by Weakly Deterministic Regular Expressions with Counters is Decidable
- Regular Expressions with Numerical Constraints and Automata with Counters
- Complexity of Decision Problems for XML Schemas and Chain Regular Expressions
- Deciding Definability by Deterministic Regular Expressions
- Unary Pushdown Automata and Straight-Line Programs
- Regular Expressions with Counting: Weak versus Strong Determinism
- One-unambiguous regular languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item