Minimal cover-automata for finite languages

DOI10.1016/S0304-3975(00)00292-9zbMath0984.68099WikidataQ59595166 ScholiaQ59595166MaRDI QIDQ5958721

Sheng Yu, Cezar Campeanu, Nicolae Sântean

Publication date: 3 March 2002

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

deterministic finite automata; cover language; deterministic cover automata; finite languages

Mathematics Subject Classification ID

68Q45: Formal languages and automata

Related Items

Similarity relations and cover automata, UNWEIGHTED AND WEIGHTED HYPER-MINIMIZATION, On Testing P Systems, Computing All ℓ-Cover Automata Fast, GOODBY TO THE KINDHEARTED DRAGON PROF. SHENG YU, 1950–2012, Compressibility of Finite Languages by Grammars, NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES, COVER TRANSDUCERS FOR FUNCTIONS WITH FINITE DOMAIN, Minimal consistent DFA revisited, Learning finite cover automata from queries, Incremental construction of minimal deterministic finite cover automata, Bounded sequence testing from deterministic finite state machines, On the Hopcroft's minimization technique for DFA and DFCA, Succinct representations of languages by DFA with different levels of reliability, An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton, On the existence of regular approximations, Finite state based testing of P systems, More on Deterministic and Nondeterministic Finite Cover Automata, Hyper-minimisation Made Efficient, Reducing Acyclic Cover Transducers, An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton

Cites Work

• A class of measures on formal languages
• The state complexities of some basic operations on regular languages
• Automaticity. I: Properties of a measure of descriptional complexity
• A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item