Second-order finite automata

DOI10.1007/S00224-022-10085-WMaRDI QIDQ2158302zbMATH OpenOpenAlexFDO

Authors Alexsander Andrade de Melo, Mateus de Oliveira Oliveira

Publication date 26 July 2022

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00224-022-10085-w

zbMATH Keywords

fixed-parameter tractabilityordered decision diagramssecond-order finite automata

Mathematics Subject Classification ID

Model theory (03Cxx) Computability and recursion theory (03Dxx) Theory of computing (68Qxx)

Recommendations

• On the minimization of (complete) ordered binary decision diagrams
• String-matching with OBDDs
• Set automata
• scientific article; zbMATH DE number 1059244
• Finite automata and ordinals

Cites work

• Abstract regular tree model checking
• Advice Automatic Structures and Uniformly Automatic Classes
• Automata and concurrency
• Automata-based presentations of infinite structures
• Automatic functions, linear time and learning
• Automatic learners with feedback queries
• Automatic learning from positive data and negative counterexamples
• Automatic structures: twenty years later
• Branching Programs and Binary Decision Diagrams
• Graph automata
• scientific article; zbMATH DE number 3841819 (Why is no real title available?)
• scientific article; zbMATH DE number 177513 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• Learnability of automatic classes
• Learning pattern languages over groups
• On testing computability by small width OBDDs
• On the minimization of (complete) ordered binary decision diagrams
• On the Width of Ordered Binary Decision Diagrams
• On the width of regular classes of finite structures
• Second-Order Finite Automata
• Second-order finite automata: expressive power and simple proofs using automatic structures
• Structures without scattered-automatic presentation
• Testing Computability by Width Two OBDDs
• Testing Membership in Languages that Have Small Width Branching Programs
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Transforming structures by set interpretations

Cited in

(1)

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

This page was built for publication: Second-order finite automata

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