Automata theory in nominal sets
From MaRDI portal
Abstract: We study languages over infinite alphabets equipped with some structure that can be tested by recognizing automata. We develop a framework for studying such alphabets and the ensuing automata theory, where the key role is played by an automorphism group of the alphabet. In the process, we generalize nominal sets due to Gabbay and Pitts.
Recommendations
Cited in
(71)- Simple and subdirectly irreducible finitely supported \(Cb\)-sets
- Free functor from the category of G-nominal sets to that of 01-G-nominal sets
- From generic partition refinement to weighted tree automata minimization
- Permutation groups with small orbit growth
- Coalgebraic semantics for nominal automata
- Reactive synthesis from visibly register pushdown automata
- Selective monitoring
- Nondeterministic and co-nondeterministic implies deterministic, for data languages
- Completeness and incompleteness in nominal Kleene algebra
- General lower bounds and improved algorithms for infinite-domain CSPs
- Coverability trees for Petri nets with unordered data
- A class of automata for the verification of infinite, resource-allocating behaviours
- Decidability Border for Petri Nets with Data: WQO Dichotomy Conjecture
- On nominal regular languages with binders
- Towards nominal computation
- Nominal automata with name binding
- Nominal Kleene coalgebra
- A dichotomy for first-order reducts of unary structures
- The language of stratified sets is confluent and strongly normalising
- scientific article; zbMATH DE number 7136664 (Why is no real title available?)
- Polynomial-time equivalence testing for deterministic fresh-register automata
- Selective monitoring
- SMT solving for functional programming over infinite structures
- scientific article; zbMATH DE number 7453188 (Why is no real title available?)
- Residuality and learning for nondeterministic nominal automata
- Solving Infinite Games in the Baire Space
- On nominal sets with support-preorder
- Algebras of UTxO blockchains
- scientific article; zbMATH DE number 7559500 (Why is no real title available?)
- A Kleene theorem for nominal automata
- scientific article; zbMATH DE number 7561623 (Why is no real title available?)
- Determinisability of register and timed automata
- Computability of data-word transductions over different data domains
- scientific article; zbMATH DE number 7204453 (Why is no real title available?)
- scientific article; zbMATH DE number 7147443 (Why is no real title available?)
- Regular and context-free nominal traces
- Towards nominal context-free model-checking
- Learning nominal automata
- \(\mathbb {N}\)-memory automata over the alphabet \(\mathbb {N}\)
- From equational specifications of algebras with structure to varieties of data languages (invited paper)
- scientific article; zbMATH DE number 7649889 (Why is no real title available?)
- Graded monads and graded logics for the linear time -- branching time spectrum
- Completeness of Nominal PROPs
- Fast computations on ordered nominal sets
- WQO dichotomy for 3-graphs
- Optimal run problem for weighted register automata
- A taxonomy and reductions for common register automata formalisms
- The fresh-graph of a nominal set
- Active learning for deterministic bottom-up nominal tree automata
- On-the-fly bisimilarity checking for fresh-register automata
- $$\textsc {Reach}$$ on Register Automata via History Independence
- Generic partition refinement and weighted tree automata
- Orbit-finite-dimensional vector spaces and weighted register automata
- Solvability of orbit-finite systems of linear equations
- Reasoning on data words over numeric domains
- Orbit-finite linear programming
- Syntactically and semantically regular languages of -terms coincide through logical relations
- Nominal tree automata with name allocation
- Bi-reachability in Petri nets with data
- Passive learning of regular data languages in polynomial time and data
- Function spaces for orbit-finite sets
- Complete test suites for automata in monoidal closed categories
- Variable automata over infinite alphabets
- Pushdown normal-form bisimulation: a nominal context-free approach to program equivalence
- Equivariant ideals of polynomials
- Bisimilarity in fresh-register automata
- Register automata with permutations
- Karp's NP-complete problems over first-order definable structures
- \(SL^{\lambda}\): a scalable algorithm for register automata learning
- Active learning of symbolic mealy automata
- Descriptive set theoretic methods in automata theory. Decidability and topological complexity
This page was built for publication: Automata theory in nominal sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2878750)
