Finite-memory automata with non-deterministic reassignment

DOI10.1142/S0129054110007532MaRDI QIDQ3056277zbMATH OpenFDO

Authors Michael Kaminski, Daniel Zeitlin

Publication date 11 November 2010

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

Full work available at URL https://doi.org/10.1142/S0129054110007532

zbMATH Keywords

finite-memory automatainfinite alphabetsregular expressions

Mathematics Subject Classification ID

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

Recommendations

• Finite-memory automata
• The Power of Non-deterministic Reassignment in Infinite-Alphabet Pushdown Automata
• \(\mathbb {N}\)-memory automata over the alphabet \(\mathbb {N}\)
• Regular expressions for languages over infinite alphabets
• Computing and Combinatorics

Cites work

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

Cited in

(23)

• The containment problem for unambiguous register automata and unambiguous timed automata
• Layered memory automata: recognizers for quasi-regular languages with unbounded memory
• Nondeterministic and co-nondeterministic implies deterministic, for data languages
• Reachability in pushdown register automata
• Nominal automata with name binding
• An automaton over data words that captures EMSO logic
• On temporal logics with data variable quantifications: decidability and complexity
• The Power of Non-deterministic Reassignment in Infinite-Alphabet Pushdown Automata
• Parametrized automata simulation and application to service composition
• Residuality and learning for nondeterministic nominal automata
• scientific article; zbMATH DE number 7559500 (Why is no real title available?)
• The containment problem for unambiguous register automata
• Computability of data-word transductions over different data domains
• Regular and context-free nominal traces
• \(\mathbb {N}\)-memory automata over the alphabet \(\mathbb {N}\)
• Synthesis of data word transducers
• A taxonomy and reductions for common register automata formalisms
• On the complexity of decision problems for parameterized finite state synchronous transducers
• Nominal tree automata with name allocation
• Variable automata over infinite alphabets
• Complexity of membership and non-emptiness problems in unbounded memory automata
• Bidimensional linear recursive sequences and universality of unambiguous register automata
• New techniques for universality in unambiguous register automata

This page was built for publication: Finite-memory automata with non-deterministic reassignment

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