Deciding determinism of unary languages
type: Item
instance of: scholarly article
title: Deciding determinism of unary languages
zbMATH Open document ID: 1332.68122
author: Ping Lu
author: Feifei Peng
author: Haiming Chen
author: Lixiao Zheng
published in: Information and Computation
publication date: 2015-12-07T00:00:00Z
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6516972
zbMATH Keywords: regular expressions
zbMATH Keywords: regular expressions with counting
zbMATH Keywords: deterministic languages
zbMATH Keywords: minimal DFA
zbMATH Keywords: coNP-complete
describes a project that uses: ALGOL 60
MaRDI profile type: Publication
full work available at URL: j.ic.2015.08.005
OpenAlex ID: W1862704942
cites work: Q3146939
cites work: One-unambiguous regular languages
cites work: Regular expressions into finite automata
cites work: Descriptional Complexity of Deterministic Regular Expressions
cites work: Checking determinism of regular expressions with counting
cites work: Deciding Definability by Deterministic Regular Expressions
cites work: Deciding determinism of regular languages
cites work: Definability by Weakly Deterministic Regular Expressions with Counters is Decidable
cites work: Regular expressions with counting: weak versus strong determinism
cites work: Succinctness of regular expressions with interleaving, intersection and counting
cites work: Finite automata and unary languages
cites work: Two Families of Languages Related to ALGOL
cites work: Q4320535
cites work: On a Problem of Partitions
cites work: Unary context-free grammars and pushdown automata, descriptional complexity and auxiliary space lower bounds.
cites work: Q5802215
cites work: Unsolved problems in number theory
cites work: Q4131648
cites work: Q4198056
cites work: Introduction to algorithms
cites work: Efficient Construction of Semilinear Representations of Languages Accepted by Unary NFA
cites work: Regular Expressions and NFAs Without ε-Transitions
cites work: The complexity of regular(-like) expressions
cites work: Q5613067
cites work: Prime Decompositions of Regular Languages
DOI: 10.1016/J.IC.2015.08.005
Recommended article: Deciding Determinism of Unary Languages Is coNP-Complete
Recommended article: Deciding determinism of regular languages
Recommended article: Deterministic Pushdown Automata and Unary Languages
Recommended article: DETERMINISTIC PUSHDOWN AUTOMATA AND UNARY LANGUAGES
Recommended article: Decidable unary varieties
Recommended article: Q4412108
Recommended article: Q4033497
Recommended article: Deciding FO-definability of regular languages
Recommended article: Q3685224
Recommended article: Inference of deterministic one-counter languages
description: scientific article; zbMATH DE number 6516972