Deciding determinism of regular languages

DOI10.1007/s00224-014-9576-2zbMath1339.68151OpenAlexW2154985586MaRDI QIDQ493651

Haiming Chen, Ping Lu, Joachim Bremer

Publication date: 4 September 2015

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-014-9576-2

zbMATH Keywords

polynomial spacedeterministic regular languagesNL-completenessnondeterministic logspaceone-unambiguous regular languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (6)

Closure properties and descriptional complexity of deterministic regular expressions ⋮ Efficient testing and matching of deterministic regular expressions ⋮ Deciding determinism of unary languages ⋮ Conjunctive query containment over trees using schema information ⋮ Unnamed Item ⋮ Deterministic regular expressions with back-references

Cites Work

• Space-bounded reducibility among combinatorial problems
• Regular expressions into finite automata
• The Membership Problem for Regular Expressions with Unordered Concatenation and Numerical Constraints
• Descriptional Complexity of Deterministic Regular Expressions
• Checking Determinism of Regular Expressions with Counting
• THE ABSTRACT THEORY OF AUTOMATA
• Nondeterministic Space is Closed under Complementation
• Deciding Definability by Deterministic Regular Expressions
• Generalized One-Unambiguity
• Regular Expressions with Counting: Weak versus Strong Determinism
• One-unambiguous regular languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Deciding determinism of regular languages