State complexity of projected languages

DOI10.1007/978-3-642-22600-7_16MaRDI QIDQ5200092zbMATH OpenOpenAlexFDO

Authors Galina Jirásková, Tomáš Masopust

Publication date 29 July 2011

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-22600-7_16

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On a structural property in the state complexity of projected regular languages
• Transition complexity of incomplete DFAs
• On properties and state complexity of deterministic state-partition automata
• State complexity of regular languages
• Implementation and Application of Automata

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3959244 (Why is no real title available?)
• scientific article; zbMATH DE number 1156489 (Why is no real title available?)
• scientific article; zbMATH DE number 1834665 (Why is no real title available?)
• scientific article; zbMATH DE number 3269886 (Why is no real title available?)
• scientific article; zbMATH DE number 3305070 (Why is no real title available?)
• A family of NFAs which need 2\(^{n}-\alpha\) deterministic states
• Compositional verification in supervisory control
• DETERMINISTIC BLOW-UPS OF MINIMAL NONDETERMINISTIC FINITE AUTOMATA OVER A FIXED ALPHABET
• Descriptional complexity -- an introductory survey
• Finite automata and unary languages
• Introduction to Discrete Event Systems
• Magic Numbers and Ternary Alphabet
• Magic numbers in the state hierarchy of finite automata
• Modular Control of Discrete-Event Systems With Coalgebra
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• On the State Complexity of Complements, Stars, and Reversals of Regular Languages
• On the computation of natural observers in discrete-event systems
• Supervisory control synthesis of discrete-event systems using a coordination scheme
• The magic number problem for subregular language families
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs

Cited in

(7)

• On properties and state complexity of deterministic state-partition automata
• scientific article; zbMATH DE number 2201371 (Why is no real title available?)
• On a structural property in the state complexity of projected regular languages
• State complexity of finite partial languages
• Quantitative estimates for the size of an intersection of sparse automatic sets
• On conditional decomposability
• More on the descriptional complexity of products of finite automata

Describes a project that uses

Uses Software

• UMDES

This page was built for publication: State complexity of projected languages

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