4 citations · 11 across the 11 of their papers we have counts for
5 papers · 1 filter
Undecidability of Reachability for Constraint Automata
Jakub Michaliszyn
We prove that reachability for constraint automata over finite binary words is undecidable. Eight registers suffice, with conjunctive guards using only equality, proper prefix, pro…
Non-deterministic weighted automata evaluated over Markov chains
Jakub Michaliszyn, Jan Otop
We present the first study of non-deterministic weighted automata under probabilistic semantics. In this semantics words are random events, generated by a Markov chain, and functio…
Approximate Learning of Limit-Average Automata
Jakub Michaliszyn, Jan Otop
Limit-average automata are weighted automata on infinite words that use average to aggregate the weights seen in infinite runs. We study approximate learning problems for limit-ave…
Average Stack Cost of Buechi Pushdown Automata
Jakub Michaliszyn, Jan Otop
We study the average stack cost of Buechi pushdown automata (Buechi PDA). We associate a non-negative price with each stack symbol and define the cost of a stack as the sum of cost…
The cost of being co-Buchi is nonlinear
Jerzy Marcinkowski, Jakub Michaliszyn
It is well known, and easy to see, that not each nondeterministic Buchi automaton on infinite words can be simulated by a nondeterministic co-Buchi automaton. We show that in the c…