Minimal cover-automata for finite languages

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

Nicolae Sântean, Sheng Yu, Cezar Campeanu

Publication date: 3 March 2002

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(00)00292-9

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, State complexity of finite partial languages, A model learning based testing approach for kernel P systems, Minimal consistent DFA revisited, Learning finite cover automata from queries, Asymptotic approximation by regular languages, 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, Inductive synthesis of cover-grammars with the help of ant colony optimization, On the compressibility of finite languages and formal proofs, Succinct representations of languages by DFA with different levels of reliability, An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton, State complexity of finite partial languages, Minimal consistent DFA from sample strings, A sufficient condition to polynomially compute a minimum separating DFA, Testing based on identifiable P systems using cover automata and X-machines, On the cover complexity of finite languages, More on deterministic and nondeterministic finite cover automata, Building efficient and compact data structures for simplicial complexes, Kernel P systems: from modelling to verification and testing, On the existence of regular approximations, Finite state based testing of P systems, A model learning based testing approach for spiking neural P systems, More on Deterministic and Nondeterministic Finite Cover Automata, Kernel P Systems Modelling, Testing and Verification - Sorting Case Study, Hyper-minimisation Made Efficient, Reducing Acyclic Cover Transducers, An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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