Results 11 to 20 of about 1,576 (262)
On the Regular Emptiness Problem of Subzero Automata [PDF]
Electronic Proceedings in Theoretical Computer Science, 2016 Subzero automata is a class of tree automata whose acceptance condition can express probabilistic constraints. Our main result is that the problem of determining if a subzero automaton accepts some regular tree is decidable.
Henryk Michalewski +2 more
doaj +1 more source
Tree Automata and Automata on Linear Orderings [PDF]
RAIRO - Theoretical Informatics and Applications, 2009 Summary: We show that the inclusion problem is decidable for rational languages of words indexed by scattered countable linear orderings. The method leans on a reduction to the decidability of the monadic second-order theory of the infinite binary tree.
Bruyère, Véronique +2 more
openaire +2 more sources
Pushing for weighted tree automata [PDF]
Logical Methods in Computer Science, 2018 A weight normalization procedure, commonly called pushing, is introduced for weighted tree automata (wta) over commutative semifields. The normalization preserves the recognized weighted tree language even for nondeterministic wta, but it is most useful ...
Thomas Hanneforth +2 more
doaj +1 more source
Hyper-Minimization for Deterministic Weighted Tree Automata [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 Hyper-minimization is a state reduction technique that allows a finite change in the semantics. The theory for hyper-minimization of deterministic weighted tree automata is provided.
Andreas Maletti, Daniel Quernheim
doaj +1 more source
From Nondeterministic B\"uchi and Streett Automata to Deterministic Parity Automata [PDF]
Logical Methods in Computer Science, 2007 In this paper we revisit Safra's determinization constructions for automata on infinite words. We show how to construct deterministic automata with fewer states and, most importantly, parity acceptance conditions.
Nir Piterman
doaj +1 more source
A Finite Exact Representation of Register Automata Configurations [PDF]
Electronic Proceedings in Theoretical Computer Science, 2014 A register automaton is a finite automaton with finitely many registers ranging from an infinite alphabet. Since the valuations of registers are infinite, there are infinitely many configurations.
Yu-Fang Chen, Bow-Yaw Wang, Di-De Yen
doaj +1 more source
Topological properties of cellular automata on trees [PDF]
Electronic Proceedings in Theoretical Computer Science, 2012 We prove that there do not exist positively expansive cellular automata defined on the full k-ary tree shift (for k>=2). Moreover, we investigate some topological properties of these automata and their relationships, namely permutivity, surjectivity ...
Gabriele Fici, Francesca Fiorenzi
doaj +1 more source
Land, 2023 Urbanization and climate change pose significant challenges to urban ecosystems, underscoring the necessity for innovative strategies to enhance urban green infrastructure.
Yi Le, Sheng-Yang Huang
doaj +1 more source
Minimisation of Multiplicity Tree Automata [PDF]
Logical Methods in Computer Science, 2017 We consider the problem of minimising the number of states in a multiplicity tree automaton over the field of rational numbers. We give a minimisation algorithm that runs in polynomial time assuming unit-cost arithmetic.
Stefan Kiefer +2 more
doaj +1 more source
A Myhill-Nerode theorem for automata with advice [PDF]
Electronic Proceedings in Theoretical Computer Science, 2012 An automaton with advice is a finite state automaton which has access to an additional fixed infinite string called an advice tape. We refine the Myhill-Nerode theorem to characterize the languages of finite strings that are accepted by automata with ...
Alex Kruckman +3 more
doaj +1 more source