Search results for: Jozef Gruska

Items from 1 to 20 out of 24 results

article

Testing Boolean Functions Properties

Zhengwei Xie, Daowen Qiu, Guangya Cai, Jozef Gruska, more

Fundamenta Informaticae > 2021 > Vol. 182, nr 4 > 321--344

The goal in the area of functions property testing is to determine whether a given black-box Boolean function has a particular given property or is ε-far from having that property. We investigate here several types of properties testing for Boolean functions (identity, correlations and balancedness) using the Deutsch-Jozsa algorithm (for the Deutsch-Jozsa (D-J) problem) and also the amplitude amplification...

article

Synthesis of quantum images using phase rotation

Shiping Du, Daowen Qiu, Jozef Gruska, Paulo Mateus

Quantum Information Processing > 2019 > 18 > 9 > 1-28

A topic about synthesis of quantum images is proposed, and a specific phase rotation transform constructed is adopted to theoretically realize the synthesis of two quantum images. The synthesis strategy of quantum images comprises three steps, which include: (1) in the stage of phase extraction, we obtain the phases of the state of the quantum image by transforming the state of the quantum image to...

article

Promise problems solved by quantum and classical finite automata

Shenggen Zheng, Lvzhou Li, Daowen Qiu, Jozef Gruska

Theoretical Computer Science > 2017 > 666 > C > 48-64

The concept of promise problems was introduced and started to be systematically explored by Even, Selman, Yacobi, Goldreich, and other scholars. It has been argued that promise problems should be seen as partial decision problems and as such that they are more fundamental than decision problems and formal languages that used to be considered as the basic ones for complexity theory. The main purpose...

chapter

Algebraic Methods in Quantum Informatics

Jozef Gruska

Lecture Notes in Computer Science > Algebraic Informatics > Invited Papers > 87-111

The paper presents and discuses several important problems and challenges of quantum informatics at which algebraic methods have been, or expect to be, very useful, or even of the key importance. Some of these problems came up quite naturally, at a very straightforward quantumization of the classical informatics concepts, models and problems. However, the most attractive/important ones come...

book

Mathematical Foundations of Computer Science 1977

Jozef Gruska

Lecture Notes in Computer Science

chapter

New Challenges for Theoretical Computer Science

Jozef Gruska

Lecture Notes in Computer Science > Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics > Panel Discussion on New Challanges for TCS > 599-601

This is a general introduction to the panel New Challenges for Theoretical Computer Science with panelists G. Ausiello, J. Gruska, U. Montanari, T. Nishizeki, Y. Toyama and J. Wiedermann. The aim of the panel is to point out and analyse new challenges theoretical computer science has to deal with in order to develop properly as fundamental science and in order to respond well to needs coming from...

chapter

Optimal Time and Communication Solutions of Firing Squad Synchronization Problems on Square Arrays, Toruses and Rings

Jozef Gruska, Salvatore Torre, Mimmo Parente

Lecture Notes in Computer Science > Developments in Language Theory > Contributed Papers > 200-211

A new solution for the Firing Squad Synchronization Problem (FSSP) on two-dimensional square arrays is presented and its correctness is demonstrated in detail. Our new solution is time as well as communication optimal (the so-called minimal time 1-bit solution). In addition, it is shown that the technique developed and the results obtained allow also to solve in optimal time & communication FSSP...

chapter

Systolic automata — power, characterizations, nonhomogeneity

Jozef Gruska

Lecture Notes in Computer Science > Mathematical Foundations of Computer Science 1984 > 32-49

chapter

Roots and Stimuli to a New Perception of Informatics

Jozef Gruska

Lecture Notes in Computer Science > Rainbow of Computer Science > The Practice of Informatics > 184-199

In the recent paper, “A perception of Informatics” [9], a new view of Informatics, visionary and philosophical in the essence, has been presented in quite general terms and ways. This new perception of Informatics has been then illustrated and put more “down to earth” in [9] through the presentation of some of the grand challenges of “new Informatics”. In the present paper some of the main...

chapter

Descriptional complexity (of languages) a short survey

Jozef Gruska

Lecture Notes in Computer Science > Mathematical Foundations of Computer Science 1976 > 65-80

The paper attempts (i) to present descriptional complexity as an identifiable part of the theory of complexity incorporating many diverse areas of research, (ii) to formulate basic problems and to survey some results (especially those concerning languages) in descriptional complexity, (iii) to discuss relation between descriptional and computational complexity.

chapter

Systolic architectures, systems and computations

Jozef Gruska

Lecture Notes in Computer Science > Automata, Languages and Programming > 254-270

A variety of problems related to systolic architectures, systems and computations is discussed. The emphases are on fundamental and general problems of broader interest. The paper concentrates on theoretical models, techniques and results. Main motivations are discussed and interesting/important applications are shown. The main attention is devoted to problems related with synthesis, transformations...

chapter

Quantumization of Theoretical Informatics

Jozef Gruska

Lecture Notes in Computer Science > Theoretical Computer Science: Exploring New Frontiers of Theoretical Informatics > Panel Discussion on New Challanges for TCS > 604-608

Maturing of informatics Recent developments in the area of quantum information processing and communications (QICP) made clear that foundations of computing have to be based not on the laws and limitations of the classical physics as so far, but on the laws and limitations of quantum physics.

chapter

Power, Puzzles and Properties of Entanglement

Jozef Gruska, Hiroshi Imai

Lecture Notes in Computer Science > Machines, Computations, and Universality > Invited Lectures Notes > 25-68

Quantum entanglement is behind various puzzling/mysterious or paradoxical phenomena of quantum mechanics in general and of quantum information processing and communication (QIPC) in particular. Or, using less strong terms, quantum entanglement leads to highly nonintuitive or even counterintuitive effects. Some of them have been known for long time. New are being discovered almost daily. At the same...

chapter

Towards adjusting informatics education to information era

Jozef Gruska, Roland Vollmar

Lecture Notes in Computer Science > Foundations of Computer Science > 49-67

Since the very beginning of the modern computing era, the scientific and educational community in informatics has been in a continuous search for a proper philosophy, viewpoints, aims, contents, methods and tools. Advances in software, communication and hardware have played by that search the most influencing role, with theory advances having only secondary and declining impacts — in spite of the...

book

Mathematical Foundations of Computer Science 1986

Jozef Gruska, Branislav Rovan, Juraj Wiedermann

Lecture Notes in Computer Science

book

Mathematical Foundations of Computer Science 1981

Jozef Gruska, Michal Chytil

Lecture Notes in Computer Science

book

Mathematical Foundations of Computer Science 1998

Luboš Brim, Jozef Gruska, Jiří Zlatuška

Lecture Notes in Computer Science

This book constitutes the refereed proceedings of the 23rd International Symposium on the Mathematical Foundations of Computer Science, MFCS'98, held in Brno, Czech Republic, in August 1998.The 71 revised full papers presented were carefully reviewed and selected from a total of 168 submissions. Also included are 11 full invited surveys by prominent leaders in the area. The papers are organized in...

article

Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata

Shenggen Zheng, Daowen Qiu, Jozef Gruska

Information and Computation > 2015 > 241 > Complete > 197-214

Interactive proof systems (IP) are very powerful – languages they can accept form exactly PSPACE. They represent also one of the very fundamental concepts of theoretical computing and a model of computation by interactions. One of the key players in IP is verifier. In the original model of IP whose power is that of PSPACE, the only restriction on verifiers is that they work in randomized polynomial...

article

State succinctness of two-way finite automata with quantum and classical states

Shenggen Zheng, Daowen Qiu, Jozef Gruska, Lvzhou Li, more

Theoretical Computer Science > 2013 > 499 > Complete > 98-112

Two-way finite automata with quantum and classical states (2QCFA) were introduced by Ambainis and Watrous in 2002. In this paper we study state succinctness of 2QCFA. For any m∈Z+ and any ϵ<1/2, we show that:1.there is a promise problem Aeq(m) which can be solved by a 2QCFA with one-sided error ϵ in a polynomial expected running time with a constant number (that depends neither on m nor on ε) of...

article

Multi-letter quantum finite automata: decidability of the equivalence and minimization of states

Daowen Qiu, Lvzhou Li, Xiangfu Zou, Paulo Mateus, more

Acta Informatica > 2011 > 48 > 5-6 > 271-290

Multi-letter quantum finite automata (QFAs) can be thought of quantum variants of the one-way multi-head finite automata (Hromkovič, Acta Informatica 19:377–384, 1983). It has been shown that this new one-way QFAs (multi-letter QFAs) can accept with no error some regular languages, for example (a + b)*b, that are not acceptable by QFAs of Moore and Crutchfield (Theor Comput Sci 237:275–306, 2000)...

Publication date

Last 3 years (1)

Close

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

From:

To:
Set your own date range

Content availability

Available (18)
None (6)

Publication type

book (14)
article (10)

INFONA - science communication portal

Search results for: Jozef Gruska

Testing Boolean Functions Properties

Synthesis of quantum images using phase rotation

Promise problems solved by quantum and classical finite automata

Algebraic Methods in Quantum Informatics

Mathematical Foundations of Computer Science 1977

New Challenges for Theoretical Computer Science

Optimal Time and Communication Solutions of Firing Squad Synchronization Problems on Square Arrays, Toruses and Rings

Systolic automata — power, characterizations, nonhomogeneity

Roots and Stimuli to a New Perception of Informatics

Descriptional complexity (of languages) a short survey

Systolic architectures, systems and computations

Quantumization of Theoretical Informatics

Power, Puzzles and Properties of Entanglement

Towards adjusting informatics education to information era

Mathematical Foundations of Computer Science 1986

Mathematical Foundations of Computer Science 1981

Mathematical Foundations of Computer Science 1998

Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata

State succinctness of two-way finite automata with quantum and classical states

Multi-letter quantum finite automata: decidability of the equivalence and minimization of states

Filter options

Publication date

Content availability

Publication type

Keywords

Data set

Journal

INFONA - science communication portal

Search results for: Jozef Gruska

Add recipient

Sending message cancelled

Are you sure you want to cancel sending this message?

Send message

Filter options

Publication date

Date range setting

Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.

Content availability

Publication type

Keywords

Data set

Journal

Reporting an error / abuse

Sending the report failed

Accessibility options