Author name cluster

Petr Jancar

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.

8 papers

2 author rows

MFCS Conference 2021 Conference Paper

The Simplest Non-Regular Deterministic Context-Free Language

Petr Jancar
Jirí Síma

We introduce a new notion of 𝒞-simple problems for a class 𝒞 of decision problems (i. e. languages), w. r. t. a particular reduction. A problem is 𝒞-simple if it can be reduced to each problem in 𝒞. This can be viewed as a conceptual counterpart to 𝒞-hard problems to which all problems in 𝒞 reduce. Our concrete example is the class of non-regular deterministic context-free languages (DCFL'), with a truth-table reduction by Mealy machines. The main technical result is a proof that the DCFL' language L_# = {0^n1^n ∣ n ≥ 1} is DCFL'-simple, and can be thus viewed as one of the simplest languages in the class DCFL', in a precise sense. The notion of DCFL'-simple languages is nontrivial: e. g. , the language L_R = {wcw^R∣ w ∈ {a, b}^*} is not DCFL'-simple. By describing an application in the area of neural networks (elaborated in another paper), we demonstrate that 𝒞-simple problems under suitable reductions can provide a tool for expanding the lower-bound results known for single problems to the whole classes of problems.

Details

MFCS Conference 2016 Conference Paper

Deciding Semantic Finiteness of Pushdown Processes and First-Order Grammars w. r. t. Bisimulation Equivalence

Petr Jancar

The problem if a given configuration of a pushdown automaton (PDA) is bisimilar with some (unspecified) finite-state process is shown to be decidable. The decidability is proven in the framework of first-order grammars, which are given by finite sets of labelled rules that rewrite roots of first-order terms. The framework is equivalent to PDA where also deterministic popping epsilon-steps are allowed, i. e. to the model for which Senizergues showed an involved procedure deciding bisimilarity (FOCS 1998). Such a procedure is here used as a black-box part of the algorithm. For deterministic PDA the regularity problem was shown decidable by Valiant (JACM 1975) but the decidability question for nondeterministic PDA, answered positively here, had been open (as indicated, e. g. , by Broadbent and Goeller, FSTTCS 2012).

Details

Highlights Conference 2015 Conference Abstract

Normed BPA processes as a rational monoid w. r. t. branching bisimilarity

Petr Jancar

The proposed talk would aim to highlight why finite transducers are a natural device for deciding branching bisimilarity on normed BPA processes. There has been a recent revival of the research interest in this intriguing equivalence on infinite-state systems, and the proposed talk is based on the paper "Branching Bisimilarity of Normed BPA Processes is in NEXPTIME" by Wojciech Czerwinski and Petr Jancar that has been accepted to LiCS 2015. In this connection it is appropriate to mention that there is the paper "Branching Bisimilarity on Normed BPA Is EXPTIME-complete" by Chaodong He and Mingzhang Huang that has been also accepted to LiCS 2015.

Details

MFCS Conference 2013 Conference Paper

Complexity of Checking Bisimilarity between Sequential and Parallel Processes

Wojciech Czerwinski
Petr Jancar
Martin Kot
Zdenek Sawa

Abstract Decidability of bisimilarity for Process Algebra (PA) processes, arising by mixing sequential and parallel composition, is a long-standing open problem. The known results for subclasses contain the decidability of bisimilarity between basic sequential (i. e. BPA) processes and basic parallel processes (BPP). Here we revisit this subcase and derive an exponential-time upper bound. Moreover, we show that the problem if a given basic parallel process is inherently sequential, i. e. bisimilar with an unspecified BPA process, is PSPACE-complete. We also introduce a model of one-counter automata, with no zero tests but with counter resets, that capture the behaviour of processes in the intersection of BPA and BPP.

Details

STOC Conference 2013 Conference Paper

Equivalence of deterministic one-counter automata is NL-complete

Stanislav Böhm
Stefan Göller
Petr Jancar

We prove that language equivalence of deterministic one-counter automata is NL-complete. This improves the superpolynomial time complexity upper bound shown by Valiant and Paterson in 1975. Our main contribution is to prove that two deterministic one-counter automata are inequivalent if and only if they can be distinguished by a word of length polynomial in the size of the two input automata.

Details

MFCS Conference 1993 Conference Paper

A Taxonomy of Forgetting Automata

Petr Jancar
Frantisek Mráz
Martin Plátek

Abstract Forgetting automata are nondeterministic linear bounded automata whose rewriting capability is restricted as follows: each cell of the tape can only be “erased” (rewritten by a special symbol) or completely “deleted”. We consider all classes of languages corresponding to various combinations of operations (erasing and deleting combined with moving the head), classify them according to the Chomsky hierarchy and show (some) other relations among them.

Details

MFCS Conference 1992 Conference Paper

Characterization of Context-Free Languages by Erasing Automata

Petr Jancar
Frantisek Mráz
Martin Plátek

Abstract It is shown that context-free languages are recognizable by (non-deterministic) erasing automata; thereby a hypothesis of [1] is denied. In addition, the class of context-free languages is characterized by means of the automata which erase each cell at the second visit at latest.

Details

MFCS Conference 1991 Conference Paper

Single-Path Petri Nets

Rodney R. Howell
Petr Jancar
Louis E. Rosier

Abstract We examine a subclass of persistent Petri nets called single-path Petri nets. Our intention is to consider a class of Petri nets whose study might yield some insight into the mathematical properties of persistent Petri nets or even general Petri nets. We conjecture that the Karp-Miller coverability tree for a persistent net is small enough to be searched in polynomial space. Although we are unable to prove this conjecture, we do show that single-path Petri nets have this property. We then use this fact to show that the canonical analysis problems (i. e. , boundedness, reachability, containment, and equivalence) for single-path Petri nets are PSPACE-complete in the strong sense. Furthermore, we show that the problem of recognizing a single-path Petri net is also PSPACE-complete.

Details