Finite state machines for strings over infinite alphabets
From MaRDI portal
Publication:5277703
DOI10.1145/1013560.1013562zbMath1367.68175MaRDI QIDQ5277703
Frank Neven, Thomas Schwentick, Victor Vianu
Publication date: 12 July 2017
Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1013560.1013562
XML; automata; first-order logic; monadic second-order logic; infinite alphabets; expressiveness; registers; pebbles
68Q45: Formal languages and automata
03D05: Automata and formal grammars in connection with logical questions
03B25: Decidability of theories and sets of sentences
Related Items
Separation logics and modalities: a survey, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Unnamed Item, Polynomial-time equivalence testing for deterministic fresh-register automata, Pebble Weighted Automata and Weighted Logics, Dynamic Behavior Matching: A Complexity Analysis and New Approximation Algorithms, Universality Problem for Unambiguous VASS, The Containment Problem for Unambiguous Register Automata, Extending two-variable logic on data trees with order on data values and its automata, Tree Automata over Infinite Alphabets, Unnamed Item, Optimal run problem for weighted register automata, Synthesis of Data Word Transducers, A taxonomy and reductions for common register automata formalisms, Active learning for deterministic bottom-up nominal tree automata, On-the-fly bisimilarity checking for fresh-register automata, Program equivalence in a simple language with state, Symbolic tree automata, Parametrized automata simulation and application to service composition, Walking on data words, Regular and context-free nominal traces, Two-way pebble transducers for partial functions and their composition, On notions of regularity for data languages, On the freeze quantifier in Constraint LTL: Decidability and complexity, Automata for XML -- a survey, Model checking memoryful linear-time logics over one-counter automata, Containment of queries for graphs with data, Weighted register automata and weighted logic on data words, On pebble automata for data languages with decidable emptiness problem, Subsequence versus substring constraints in sequence pattern languages, The containment problem for unambiguous register automata and unambiguous timed automata, Reactive synthesis from visibly register pushdown automata, On computability of data word functions defined by transducers, Nondeterministic and co-nondeterministic implies deterministic, for data languages, Streamable regular transductions, Deterministic regular expressions with back-references, Regular expressions for data words, Reachability in pushdown register automata, A note on the emptiness problem for alternating finite-memory automata, Complexity results on register context-free grammars and related formalisms, Automated Program Verification, Weak and Nested Class Memory Automata, Expressiveness of Hybrid Temporal Logic on Data Words, Decision Problems for Finite Automata over Infinite Algebraic Structures, Relating timed and register automata, Nominal Automata with Name Binding, Logics of Repeating Values on Data Trees and Branching Counter Systems, Algorithmic Nominal Game Semantics, Variable Tree Automata over Infinite Ranked Alphabets, CLASS COUNTING AUTOMATA ON DATAWORDS, FINITE-MEMORY AUTOMATA WITH NON-DETERMINISTIC REASSIGNMENT, An Automaton over Data Words That Captures EMSO Logic, Weighted Register Automata and Weighted Logic on Data Words, On Pebble Automata for Data Languages with Decidable Emptiness Problem, Playing with Repetitions in Data Words Using Energy Games, Automata on Gauss Words, Algorithmic Analysis of Array-Accessing Programs, Counting Multiplicity over Infinite Alphabets
