Languages generated by conjunctive query fragments of FC [REG]
FC is a finite model variant on the theory of concatenation, FC [REG] extends FC with regular
constraints. This paper considers the languages generated by their conjunctive query …
constraints. This paper considers the languages generated by their conjunctive query …
Groups whose word problems are not semilinear
RH Gilman, RP Kropholler… - Groups Complexity …, 2018 - degruyter.com
Suppose that G is a finitely generated group and WP(G) is the formal language of words
defining the identity in G. We prove that if G is a virtually nilpotent group that is not virtually …
defining the identity in G. We prove that if G is a virtually nilpotent group that is not virtually …
Generalizations of the Muller–Schupp theorem and tree‐like inverse graphs
E Rodaro - Journal of the London Mathematical Society, 2024 - Wiley Online Library
We extend the characterization of context‐free groups of Muller and Schupp in two ways. We
first show that for a quasi‐transitive inverse graph Γ Γ, being quasi‐isometric to a tree, or …
first show that for a quasi‐transitive inverse graph Γ Γ, being quasi‐isometric to a tree, or …
Groups Whose Word Problems Are Accepted by Abelian -Automata
T Yuyama - … Conference on Developments in Language Theory, 2023 - Springer
Abstract Elder, Kambites, and Ostheimer showed that if a finitely generated group H has
word problem accepted by a G-automaton for an abelian group G, then H has an abelian …
word problem accepted by a G-automaton for an abelian group G, then H has an abelian …
On a class of poly-context-free groups generated by automata
This paper deals with graph automaton groups associated with trees and some
generalizations. We start by showing some algebraic properties of tree automaton groups …
generalizations. We start by showing some algebraic properties of tree automaton groups …
The language of self-avoiding walks
C Lindorfer, W Woess - Combinatorica, 2020 - Springer
Abstract Let X=(VX, EX) be an infinite, locally finite, connected graph without loops or
multiple edges. We consider the edges to be oriented, and EX is equipped with an involution …
multiple edges. We consider the edges to be oriented, and EX is equipped with an involution …
More on Groups and Counter Automata
T Yuyama - arxiv preprint arxiv:2210.16879, 2022 - arxiv.org
Elder, Kambites, and Ostheimer showed that if the word problem of a finitely generated
group $ H $ is accepted by a $ G $-automaton for an abelian group $ G $, then $ H $ is …
group $ H $ is accepted by a $ G $-automaton for an abelian group $ G $, then $ H $ is …
The Power of a Single Qubit: Two-Way Quantum Finite Automata and the Word Problem
Z Remscrim - arxiv preprint arxiv:2003.09879, 2020 - arxiv.org
The two-way finite automaton with quantum and classical states (2QCFA), defined by
Ambainis and Watrous, is a model of quantum computation whose quantum part is …
Ambainis and Watrous, is a model of quantum computation whose quantum part is …
4 Groups with multiple context-free word problems
R Gilman - Languages and Automata: GAGTA BOOK 3, 2024 - degruyter.com
4 Groups with multiple context-free word problems Page 169 Robert Gilman 4 Groups with
multiple context-free word problems Abstract: This chapter is an introduction to multiple …
multiple context-free word problems Abstract: This chapter is an introduction to multiple …
[PDF][PDF] Walks and boundaries
W WOESS - 2018 - math.tugraz.at
The three FWF projects “Asymptotic properties of random walks on graphs”(P15577, years
2002–2006),“Random walks, random configurations, and horocyclic products”(P19115 …
2002–2006),“Random walks, random configurations, and horocyclic products”(P19115 …