Results 141 to 150 of about 1,479 (163)
Some of the next articles are maybe not open access.
2019
Regulated rewriting is one of the classical areas in Formal Languages, as tree automata are a classical topic. Somewhat surprisingly, there have been no attempts so far to combine both areas. Here, we start this type of research, introducing regulated tree automata, proving in particular characterizations of the yields of such regulated automata.
Henning Fernau, Martin Vu
openaire +1 more source
Regulated rewriting is one of the classical areas in Formal Languages, as tree automata are a classical topic. Somewhat surprisingly, there have been no attempts so far to combine both areas. Here, we start this type of research, introducing regulated tree automata, proving in particular characterizations of the yields of such regulated automata.
Henning Fernau, Martin Vu
openaire +1 more source
Proceedings of the 19th Annual IEEE Symposium on Logic in Computer Science, 2004., 2004
We introduce a new class of automata, which we call vector addition tree automata. These automata are a natural generalization of vector addition systems with states, which are themselves equivalent to Petri nets. Then, we prove that the decidability of provability in multiplicative exponential linear logic (which is an open problem) is equivalent to ...
de Groote, Philippe +2 more
openaire +2 more sources
We introduce a new class of automata, which we call vector addition tree automata. These automata are a natural generalization of vector addition systems with states, which are themselves equivalent to Petri nets. Then, we prove that the decidability of provability in multiplicative exponential linear logic (which is an open problem) is equivalent to ...
de Groote, Philippe +2 more
openaire +2 more sources
1995
We summarize the main connections between rewriting, automata, and logical languages. We recall and illustrate from a rewriting point of view classical tree automata, Rabin and Buchi automata, which are associated with (W)SIS and (W)SkS logics. We introduce four recent classes of tree automata, closely linked to rewriting problems.
openaire +1 more source
We summarize the main connections between rewriting, automata, and logical languages. We recall and illustrate from a rewriting point of view classical tree automata, Rabin and Buchi automata, which are associated with (W)SIS and (W)SkS logics. We introduce four recent classes of tree automata, closely linked to rewriting problems.
openaire +1 more source
2008
A survey of tree-walking automata. The main focus is on how the expressive power is changed by adding features such as pebbles or nondeterminism.
openaire +1 more source
A survey of tree-walking automata. The main focus is on how the expressive power is changed by adding features such as pebbles or nondeterminism.
openaire +1 more source
Tree Automata and XPath on Compressed Trees
2006The complexity of various membership problems for tree automata on compressed trees is analyzed. Two compressed representations are considered: dags, which allow to share identical subtrees in a tree, and straight-line context-free tree grammars, which moreover allow to share identical intermediate parts of a tree.
Markus Lohrey, Sebastian Maneth
openaire +1 more source
Lattice-valued tree pushdown automata: Pumping lemma and closure properties
International Journal of Approximate Reasoning, 2022Maryam Ghorani +2 more
exaly
Tree-walking automata cannot be determinized
Theoretical Computer Science, 2006Mikołaj Bojanczyk
exaly
Fuzzy Tree Automata and Syntactic Pattern Recognition
IEEE Transactions on Pattern Analysis and Machine Intelligence, 1982Edward T Lee
exaly
Tree-Walking Automata Do Not Recognize All Regular Languages
SIAM Journal on Computing, 2008Mikołaj Bojanczyk
exaly