Complementing unary nondeterministic automata
type: Item
instance of: scholarly article
title: Complementing unary nondeterministic automata
zbMATH Open document ID: 1078.68091
author: Filippo Mera
author: Giovanni Pighizzini
published in: Theoretical Computer Science
publication date: 2005-02-22T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 2136581
zbMATH Keywords: Formal languages
zbMATH Keywords: Finite state automata
zbMATH Keywords: Unary languages
zbMATH Keywords: Descriptional complexity
zbMATH Keywords: Complementation
Wikidata QID: Q61677527
MaRDI profile type: Publication
full work available at URL: j.tcs.2004.04.015
OpenAlex ID: W2081149873
cites work: Partial orders on words, minimal elements of regular languages, and state complexity
cites work: Finite automata and unary languages
cites work: Q5422234
cites work: Q3856819
cites work: Q4412108
cites work: NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
cites work: Q4506483
cites work: THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
cites work: Succinct representation of regular languages by Boolean automata
cites work: Q4503152
cites work: Optimal simulations between unary automata
cites work: On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
cites work: Q4941905
cites work: UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION
cites work: Q5541339
cites work: On the maximal order in $S_n$ and $S*_n$
cites work: State complexity of regular languages
DOI: 10.1016/J.TCS.2004.04.015
DBLP publication ID: journals/tcs/MeraP05
Recommended article: Correct Hardware Design and Verification Methods
Recommended article: Nondeterministic multicounter machines and complementation
Recommended article: Mathematical Foundations of Computer Science 2003
Recommended article: On completeness of nondeterministic automata
Recommended article: Pairs of Complementary Unary Languages with “Balanced” Nondeterministic Automata
Recommended article: Pairs of complementary unary languages with ``balanced'' nondeterministic automata
Recommended article: Unary NFAs with Limited Nondeterminism
Recommended article: Complementation, Disambiguation, and Determinization of Büchi Automata Unified
Recommended article: Canonical Nondeterministic Automata
description: scientific article; zbMATH DE number 2136581