Finite state machines for strings over infinite alphabets

DOI10.1145/1013560.1013562zbMath1367.68175OpenAlexW2056665285MaRDI 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

zbMATH Keywords

XML automata first-order logic monadic second-order logic infinite alphabets expressiveness registers pebbles

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)

Related Items

Reactive synthesis from visibly register pushdown automata ⋮ On notions of regularity for data languages ⋮ Weighted Register Automata and Weighted Logic on Data Words ⋮ On Pebble Automata for Data Languages with Decidable Emptiness Problem ⋮ Reachability in pushdown register automata ⋮ On the freeze quantifier in Constraint LTL: Decidability and complexity ⋮ Automata for XML -- a survey ⋮ Containment of queries for graphs with data ⋮ Unnamed Item ⋮ Complexity results on register context-free grammars and related formalisms ⋮ Separation logics and modalities: a survey ⋮ A taxonomy and reductions for common register automata formalisms ⋮ Set augmented finite automata over infinite alphabets ⋮ Active learning for deterministic bottom-up nominal tree automata ⋮ On-the-fly bisimilarity checking for fresh-register automata ⋮ On computability of data word functions defined by transducers ⋮ Relating timed and register automata ⋮ A note on the emptiness problem for alternating finite-memory automata ⋮ On pebble automata for data languages with decidable emptiness problem ⋮ Program equivalence in a simple language with state ⋮ Nominal Automata with Name Binding ⋮ Logics of Repeating Values on Data Trees and Branching Counter Systems ⋮ Unnamed Item ⋮ Symbolic tree automata ⋮ Parametrized automata simulation and application to service composition ⋮ Synthesis of Data Word Transducers ⋮ Algorithmic Nominal Game Semantics ⋮ Polynomial-time equivalence testing for deterministic fresh-register automata ⋮ Nondeterministic and co-nondeterministic implies deterministic, for data languages ⋮ Walking on data words ⋮ Variable Tree Automata over Infinite Ranked Alphabets ⋮ CLASS COUNTING AUTOMATA ON DATAWORDS ⋮ Extending two-variable logic on data trees with order on data values and its automata ⋮ Regular and context-free nominal traces ⋮ Pebble Weighted Automata and Weighted Logics ⋮ Model checking memoryful linear-time logics over one-counter automata ⋮ Subsequence versus substring constraints in sequence pattern languages ⋮ Unnamed Item ⋮ FINITE-MEMORY AUTOMATA WITH NON-DETERMINISTIC REASSIGNMENT ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Weighted register automata and weighted logic on data words ⋮ Dynamic Behavior Matching: A Complexity Analysis and New Approximation Algorithms ⋮ Playing with Repetitions in Data Words Using Energy Games ⋮ Automated Program Verification ⋮ Weak and Nested Class Memory Automata ⋮ Tree Automata over Infinite Alphabets ⋮ Streamable regular transductions ⋮ Automata on Gauss Words ⋮ Optimal run problem for weighted register automata ⋮ The containment problem for unambiguous register automata and unambiguous timed automata ⋮ Two-way pebble transducers for partial functions and their composition ⋮ An Automaton over Data Words That Captures EMSO Logic ⋮ Universality Problem for Unambiguous VASS ⋮ The Containment Problem for Unambiguous Register Automata ⋮ Expressiveness of Hybrid Temporal Logic on Data Words ⋮ Algorithmic Analysis of Array-Accessing Programs ⋮ Decision Problems for Finite Automata over Infinite Algebraic Structures ⋮ Counting Multiplicity over Infinite Alphabets ⋮ Deterministic regular expressions with back-references ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Regular expressions for data words