Automata Presenting Structures: A Survey of the Finite String Case
From MaRDI portal
decidability problem for finite automata and logical structuresfinite automatonfirst order logic of countable many predicatesfirst-order logiclogical structuremonadic second order logicrecognisability by finite automata and definability by logical formularelationship between definability and recognisabilitystrings and trees over finite alphabet
Recommendations
- Finite automata over structures (extended abstract)
- The finite automata approaches in stringology
- A Finite Axiomatisation of Finite-State Automata Using String Diagrams
- A string diagrammatic axiomatisation of finite-state automata
- scientific article; zbMATH DE number 2208070
- FINDING FINITE AUTOMATA THAT CERTIFY TERMINATION OF STRING REWRITING SYSTEMS
- Descriptional and computational complexity of finite automata -- a survey
- Finite presentations of infinite structures: Automata and interpretations
- An Evaluation of Automata Algorithms for String Analysis
- Automata-based presentations of infinite structures
Cites work
- Automatic linear orders and trees
- Automaticity of ordinals and of homogeneous graphs
- Definability hierarchies of generalized quantifiers
- Finite presentations of infinite structures: Automata and interpretations
- scientific article; zbMATH DE number 3660804 (Why is no real title available?)
- scientific article; zbMATH DE number 3767656 (Why is no real title available?)
- Invariants of Automatic Presentations and Semi-synchronous Transductions
- LICS 2001 special issue
- Logical Reversibility of Computation
- On direct products of automaton decidable theories
- Sets recognized by n-tape automata
- The theory of \(\langle \mathbb{N} , +, V_ k, V_ l\rangle\) is undecidable
- Tree acceptors and some of their applications
- Weak Second‐Order Arithmetic and Finite Automata
Cited in
(57)- Learning pattern languages over groups
- Learnability of automatic classes
- Finite presentations of infinite structures: Automata and interpretations
- Lamplighter groups and automata
- DEL-based epistemic planning: decidability and complexity
- A language hierarchy of binary relations
- The isomorphism problem for tree-automatic ordinals with addition
- On decidability of list structures
- An example of an automatic graph of intermediate growth
- Deciding the isomorphism problem in classes of unary automatic structures
- Isomorphisms of scattered automatic linear orders
- Automatic structures and the theory of lists
- Automatic learners with feedback queries
- Tree-automatic scattered linear orders
- A computation model with automatic functions and relations as primitive operations
- String compression in FA-presentable structures
- Learning pattern languages over groups
- The isomorphism problem on classes of automatic structures with transitive relations
- Finite automata over structures (extended abstract)
- An Evaluation of Automata Algorithms for String Analysis
- Size and computation of injective tree automatic presentations
- Automatic Learners with Feedback Queries
- Where automatic structures benefit from weighted automata
- Automatic structures of bounded degree revisited
- Automata-based presentations of infinite structures
- Regular Growth Automata: Properties of a Class of Finitely Induced Infinite Machines
- A Büchi-Elgot-Trakhtenbrot theorem for automata with MSO graph storage
- A Hierarchy of Automaticω-Words having a Decidable MSO Theory
- Some natural decision problems in automatic graphs
- Analysing Complexity in Classes of Unary Automatic Structures
- Automatic Structures of Bounded Degree Revisited
- Automatic models of first order theories
- scientific article; zbMATH DE number 2040323 (Why is no real title available?)
- scientific article; zbMATH DE number 1747445 (Why is no real title available?)
- String Analysis via Automata Manipulation with Logic Circuit Representation
- On automaton presentations of projective planes
- scientific article; zbMATH DE number 7438568 (Why is no real title available?)
- Climbing up the elementary complexity classes with theories of automatic structures
- AUTOMATIC AND POLYNOMIAL-TIME ALGEBRAIC STRUCTURES
- STACS 2004
- Automatic Structures: Richness and Limitations
- A hierarchy of tree-automatic structures
- Invariants of Automatic Presentations and Semi-synchronous Transductions
- Implementation and Application of Automata
- Learners based on transducers
- Clique‐convergence is undecidable for automatic graphs
- Addition machines, automatic functions and open problems of Floyd and Knuth
- Ramsey quantifiers over automatic structures: complexity and applications to verification
- An efficient quantifier elimination procedure for Presburger arithmetic
- Quasi-isometric reductions between infinite strings
- The theory of reachability of trace-pushdown systems
- Automatic learning of subclasses of pattern languages
- The isomorphism relation between tree-automatic structures
- The algebras for automatic relations
- Word structures and their automatic presentations
- Karp's NP-complete problems over first-order definable structures
- Second-order finite automata: expressive power and simple proofs using automatic structures
This page was built for publication: Automata Presenting Structures: A Survey of the Finite String Case
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3503740)
