FINITE-MEMORY AUTOMATA WITH NON-DETERMINISTIC REASSIGNMENT

DOI10.1142/S0129054110007532zbMath1207.68191MaRDI QIDQ3056277

Daniel Zeitlin, Michael Kaminski

Publication date: 11 November 2010

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

regular expressionsinfinite alphabetsfinite-memory automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (15)

On temporal logics with data variable quantifications: decidability and complexity ⋮ Reachability in pushdown register automata ⋮ Layered memory automata: recognizers for quasi-regular languages with unbounded memory ⋮ Unnamed Item ⋮ A taxonomy and reductions for common register automata formalisms ⋮ Nominal Automata with Name Binding ⋮ Unnamed Item ⋮ Parametrized automata simulation and application to service composition ⋮ Nondeterministic and co-nondeterministic implies deterministic, for data languages ⋮ Regular and context-free nominal traces ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The containment problem for unambiguous register automata and unambiguous timed automata ⋮ An Automaton over Data Words That Captures EMSO Logic ⋮ The Containment Problem for Unambiguous Register Automata

Cites Work

• Finite-memory automata
• Finite-state unification automata and relational languages
• Context-free languages over infinite alphabets
• The Power of Non-deterministic Reassignment in Infinite-Alphabet Pushdown Automata
• Finite state machines for strings over infinite alphabets
• Tree Automata over Infinite Alphabets

This page was built for publication: FINITE-MEMORY AUTOMATA WITH NON-DETERMINISTIC REASSIGNMENT