Algorithms for determining the smallest number of nonterminals (states) sufficient for generating (accepting) a regular language R with R₁ R R₂ for given regular languages R₁,R₂.

DOI10.1016/S0304-3975(01)00324-3MaRDI QIDQ1853563zbMATH OpenFDO

Authors Kosaburo Hashiguchi

Publication date 21 January 2003

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

Full work available at URL https://doi.org/10.1016/S0304-3975(01)00324-3

zbMATH Keywords

AlgorithmNonterminal-minimalRegular languageRight linear grammar

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 176770
• scientific article; zbMATH DE number 3592984
• scientific article; zbMATH DE number 4116004
• Nondeterministic state complexity for suffix-free regular languages
• scientific article; zbMATH DE number 2068873
• Determination of finite automata accepting subregular languages
• Finite transducers and nondeterministic state complexity of regular languages
• scientific article; zbMATH DE number 1773088
• An optimal lower bound for nonregular languages
• Nondeterministic State Complexity of Basic Operations for Prefix-Free Regular Languages

Cites work

• scientific article; zbMATH DE number 176770 (Why is no real title available?)
• Regular languages of star height one
• The Unsolvability of the Equivalence Problem for \varepsilon -Free NGSM’s with Unary Input (Output) Alphabet and Applications

Cited in

(2)

• scientific article; zbMATH DE number 3862471 (Why is no real title available?)
• scientific article; zbMATH DE number 176770 (Why is no real title available?)

This page was built for publication: Algorithms for determining the smallest number of nonterminals (states) sufficient for generating (accepting) a regular language \(R \) with \(R_{1}\subseteq R\subseteq R_{2}\) for given regular languages \(R_{1},R_{2}\).

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853563)