Deciding determinism of regular languages
type: Item
instance of: scholarly article
title: Deciding determinism of regular languages
zbMATH Open document ID: 1339.68151
author: Ping Lu
author: Joachim Bremer
author: Haiming Chen
published in: Theory of Computing Systems
publication date: 2015-09-04T00:00:00Z
review text: The paper deals with the problem of deciding whether a given regular language \(L\) can be described by a deterministic (also called one-unambiguous) regular expression, that is, a regular expression such that each occurrence of a letter in any word from \(L\) can be uniquely matched to a symbol in this expression, without looking ahead in the word. The algorithm for this problem due to \textit{A. Brüggemann-Klein} and \textit{D. Wood} [Inf. Comput. 142, No. 2, 182--206 (1998; Zbl 0912.68112)] is modified so that recursive calls are avoided. In this way it is shown that the problem is NL-complete if input languages are given by deterministic finite automata and the size of the alphabet is either constant or logarithmic. Using the same approach, it is also proved that the problem can be solved in quadratic space if input languages are given by nondeterministic finite automata or regular expressions, thereby improving the result of \textit{W. Czerwiński} et al. [Lect. Notes Comput. Sci. 7794, 289--304 (2013; Zbl 1260.68199)].
reviewed by: Michal Kunc
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6478532
zbMATH Keywords: deterministic regular languages
zbMATH Keywords: one-unambiguous regular languages
zbMATH Keywords: NL-completeness
zbMATH Keywords: polynomial space
zbMATH Keywords: nondeterministic logspace
MaRDI profile type: Publication
full work available at URL: s00224-014-9576-2
OpenAlex ID: W2154985586
cites work: Q4376789
cites work: Space-bounded reducibility among combinatorial problems
cites work: Regular expressions into finite automata
cites work: One-unambiguous regular languages
cites work: Generalized One-Unambiguity
cites work: Checking Determinism of Regular Expressions with Counting
cites work: Deciding Definability by Deterministic Regular Expressions
cites work: Q4198056
cites work: Regular expressions with counting: weak versus strong determinism
cites work: THE ABSTRACT THEORY OF AUTOMATA
cites work: Q4045961
cites work: Q3862379
cites work: The Membership Problem for Regular Expressions with Unordered Concatenation and Numerical Constraints
cites work: Nondeterministic Space is Closed under Complementation
cites work: Descriptional Complexity of Deterministic Regular Expressions
cites work: Q4298260
cites work: Q4714446
DOI: 10.1007/S00224-014-9576-2
description: scientific article; zbMATH DE number 6478532