Author name cluster

Daniel Průša

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

NeurIPS Conference 2024 Conference Paper

Constrained Binary Decision Making

Daniel Průša
Vojtěch Franc

Binary statistical decision making involves choosing between two states based on statistical evidence. The optimal decision strategy is typically formulated through a constrained optimization problem, where both the objective and constraints are expressed as integrals involving two Lebesgue measurable functions, one of which represents the strategy being optimized. In this work, we present a comprehensive formulation of the binary decision making problem and provide a detailed characterization of the optimal solution. Our framework encompasses a wide range of well-known and recently proposed decision making problems as specific cases. We demonstrate how our generic approach can be used to derive the optimal decision strategies for these diverse instances. Our results offer a robust mathematical tool that simplifies the process of solving both existing and novel formulations of binary decision making problems which are in the core of many Machine Learning algorithms.

PDF Details DOI

I&C Journal 2023 Journal Article

Weight-reducing Turing machines

Bruno Guillon
Giovanni Pighizzini
Luca Prigioniero
Daniel Průša

It is well known that one-tape Turing machines running in linear time are no more powerful than finite automata; namely they recognize exactly the class of regular languages. We prove that it is not decidable if a one-tape machine runs in linear time, even if it is deterministic and restricted to use only the portion of the tape that initially contains the input. This motivates the introduction of a constructive variant of one-tape machines, called a weight-reducing machine, and the investigation of its properties. We focus on the deterministic case. In particular, we show that, paying a polynomial size increase only, each weight-reducing machine can be turned into a halting one that runs in linear time. Furthermore each weight-reducing machine can be converted into equivalent nondeterministic and deterministic finite automata by paying an exponential and doubly-exponential increase in size, respectively. These costs cannot be reduced in the worst case.

Details DOI

I&C Journal 2022 Journal Article

Converting nondeterministic two-way automata into small deterministic linear-time machines

Bruno Guillon
Giovanni Pighizzini
Luca Prigioniero
Daniel Průša

In 1978 Sakoda and Sipser raised the question of the cost, in terms of size of representations, of the transformation of two-way and one-way nondeterministic automata into equivalent two-way deterministic automata. Despite all the attempts, the question has been answered only for particular cases, while it remains open in general, the best upper bound currently known being exponential. We present a new approach in which unrestricted nondeterministic automata are simulated by deterministic models extending two-way deterministic automata, paying only a polynomial increase of size. Indeed, we study the costs of the conversions of nondeterministic automata into some variants of one-tape deterministic Turing machines working in linear time; namely Hennie machines, weight-reducing Turing machines, and weight-reducing Hennie machines. All these variants are known to share the same computational power: they characterize the class of regular languages.

Details DOI

TCS Journal 2021 Journal Article

Two-dimensional pattern matching against local and regular-like picture languages

František Mráz
Daniel Průša
Michael Wehar

Given a two-dimensional array of symbols and a picture language over a finite alphabet, we investigate how to find rectangular subarrays that belong to the picture language. Two-dimensional pattern matching problems can be formulated by interpreting subarrays as matches and picture languages as patterns. We formulate four particular problems – finding maximum, minimum, any or all match(es) – and describe algorithms solving the problems for basic classes of picture languages, which include local picture languages and picture languages accepted by various types of deterministic two-dimensional finite automata such as four-way, three-way and two-way automata, on-line tessellation automata, and returning finite automata. We also prove that the pattern matching problems cannot be solved for the class of local picture languages in time linear in the input area unless the well known problem of triangle finding in a graph is solvable in quadratic time. This shows a fundamental difference between the complexity of one-dimensional and two-dimensional pattern matching.

Details DOI

TCS Journal 2017 Journal Article

Undecidability of the emptiness problem for context-free picture languages

Daniel Průša
Klaus Reinhardt

A two-dimensional Kolam grammar as defined by Siromoney et al. in 1972 and independently by Matz in 1997 and Schlesinger in 1989 allows context-free productions of the form A → a, A → B C, A → B C, and S → λ which concatenate sub-pictures produced by B and C horizontally respectively vertically if their height respectively width fits. We demonstrate that this grammar is quite powerful by proving undecidability of the emptiness problem. We further analyze consequences of this finding and give additional characteristics related to size of generated pictures.

Details DOI

TCS Journal 2016 Journal Article

Non-recursive trade-offs between two-dimensional automata and grammars

Daniel Průša

We study succinctness of descriptional systems for picture languages. Basic models of two-dimensional finite automata and generalizations of context-free grammars are considered. They include the four-way automaton of Blum and Hewitt, the two-dimensional online tessellation automaton of Inoue and Nakamura and the context-free Kolam grammar of Siromoney et al. We show that non-recursive trade-offs between the systems are very common. Basically, each separation result proving that one system describes a picture language which cannot be described by another system can usually be turned into a non-recursive trade-off result between the systems. These findings are strongly based on the ability of the systems to simulate Turing machines.

Details DOI