Conversions between six models of finite automata

DOI10.1142/S0129054124430020MaRDI QIDQ6989495zbMATH OpenFDO

Authors Michal Hospodár, Galina Jirásková

Publication date 30 April 2025

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/S0129054124430020

zbMATH Keywords

alternating finite automataBoolean finite automatacosts of conversionsdeterministic finite automatanondeterministic finite automata with a unique final statenondeterministic finite automata with multiple final statespartial deterministic finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites work

• A Survey on Fooling Sets as Effective Tools for Lower Bounds on Nondeterministic Complexity
• Alternation
• Constructions for alternating finite automata^∗
• Descriptional Complexity of Operations on Alternating and Boolean Automata
• Descriptional complexity of the forever operator
• Finite automata and unary languages
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 1418342 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• scientific article; zbMATH DE number 3305062 (Why is no real title available?)
• Intersection and union of regular languages and state complexity
• Magic numbers in the state hierarchy of finite automata
• NFA-to-DFA trade-off for regular operations
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• On equations for regular languages, finite automata, and sequential networks
• On the maximal order in S_n and S*_n
• Power, positive closure, and quotients on convex languages
• Reversal of binary regular languages
• State complexity of some operations on binary regular languages
• Succinct representation of regular languages by Boolean automata

This page was built for publication: Conversions between six models of finite automata

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