State complexity of binary coded regular languages

DOI10.1016/j.tcs.2024.114399OpenAlexW4390941915WikidataQ129754596 ScholiaQ129754596MaRDI QIDQ6120344

Viliam Geffert, Dominika Pališínová, Alexander Szabari

Publication date: 20 February 2024

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

Full work available at URL: https://doi.org/10.1016/j.tcs.2024.114399

zbMATH Keywords

finite automatastate complexityprefix codespromise problemsdon't care automata

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a structural property in the state complexity of projected regular languages
• Optimal state reductions of automata with partially specified behaviors
• Maximal codes with bounded deciphering delay
• Intersection and union of regular languages and state complexity
• Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs
• The alphabetic complexity in homomorphic definitions of word, tree and picture languages
• State complexity of binary coded regular languages
• The range of state complexities of languages resulting from the cascade product -- the unary case (extended abstract)
• Magic numbers in the state hierarchy of finite automata
• Kleene Star on Unary Regular Languages
• MAGIC NUMBERS AND TERNARY ALPHABET
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• State Reduction in Incompletely Specified Finite-State Machines

This page was built for publication: State complexity of binary coded regular languages