Finite transducers and nondeterministic state complexity of regular languages

DOI10.3103/S1066369X10060034MaRDI QIDQ1956627zbMATH OpenOpenAlexFDO

Authors G. A. Povarov

Publication date 23 September 2010

Published in Russian Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.3103/s1066369x10060034

zbMATH Keywords

regular languagefinite transducerdescriptive complexitynondeterministic finite automatonnondeterministic state complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• scientific article; zbMATH DE number 1948495 (Why is no real title available?)
• scientific article; zbMATH DE number 1962776 (Why is no real title available?)
• scientific article; zbMATH DE number 2081043 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• Descriptional Complexity of Nondeterministic Finite Automata
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• Intersection and union of regular languages and state complexity

Cited in

(8)

• scientific article; zbMATH DE number 1949651 (Why is no real title available?)
• 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}\).
• Descriptional complexity of error detection
• Complexity of injection structures induced by finite state transducers
• scientific article; zbMATH DE number 176770 (Why is no real title available?)
• scientific article; zbMATH DE number 7770052 (Why is no real title available?)
• Finite state transducers with predicates and identities
• Finite State Transducers with Intuition

This page was built for publication: Finite transducers and nondeterministic state complexity of regular languages

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