Second-order finite automata: expressive power and simple proofs using automatic structures

DOI10.1007/978-3-030-81508-0_20MaRDI QIDQ832943zbMATH OpenOpenAlexFDO

Authors Dietrich Kuske

Publication date 25 March 2022

Full work available at URL https://doi.org/10.1007/978-3-030-81508-0_20

zbMATH Keywords

automatic classesclasses of languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Second-order finite automata
• Second-Order Finite Automata
• Finite automata over structures (extended abstract)
• Finite automata. II
• Realization of finite-automaton algorithms by structured programs. II
• Automata for the verification of monadic second-order graph properties
• Deciding monadic second order logic over \(\omega \)-words by specialized finite automata
• Weighted automata and monadic second order logic
• Two-way finite automata: old and recent results

Cites work

• Automata Presenting Structures: A Survey of the Finite String Case
• Automatic presentations of structures
• Cardinality and counting quantifiers on omega-automatic structures
• Foundations of Software Science and Computation Structures
• Is Ramsey's theorem omega-automatic?
• Learnability of automatic classes
• MSO on the Infinite Binary Tree: Choice and Order
• On direct products of automaton decidable theories
• On the valuedness of finite transducers
• Second-Order Finite Automata
• Synchronized rational relations of finite and infinite words
• The isomorphism problem on classes of automatic structures with transitive relations
• Where automatic structures benefit from weighted automata

Cited in

(2)

• Second-order finite automata
• Properties of graphs specified by a regular language

This page was built for publication: Second-order finite automata: expressive power and simple proofs using automatic structures

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