An introduction to finite automata and their connection to logic

DOI10.1142/9789814271059_0001zbMATH Open1256.68112arXiv1011.6491OpenAlexW2964164509MaRDI QIDQ4907853FDOQ4907853

Authors: Howard Straubing, Pascal Weil 

Publication date: 26 February 2013

Published in: Modern Applications of Automata Theory (Search for Journal in Brave)

Abstract: This is a tutorial on finite automata. We present the standard material on determinization and minimization, as well as an account of the equivalence of finite automata and monadic second-order logic. We conclude with an introduction to the syntactic monoid, and as an application give a proof of the equivalence of first-order definability and aperiodicity.

Full work available at URL: https://arxiv.org/abs/1011.6491

Recommendations

• Finite automata
• scientific article; zbMATH DE number 618821
• scientific article; zbMATH DE number 459361
• scientific article; zbMATH DE number 3976377
• Automata theory and its applications

zbMATH Keywords

minimizationequivalencefinite automatafirst-order definabilitymonadic second-order logicdeterminizationfirst-order aperiodicity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25)

Cited In (9)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Minimal state automata for detecting a \(\beta\) globin gene mutation
• Title not available (Why is that?)
• The Quantifier Alternation Hierarchy of Synchronous Relations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Automata and rational expressions
• Finite automata

This page was built for publication: An introduction to finite automata and their connection to logic

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