Wyniki wyszukiwania - BazTech

1

Minimal Size of Counters for (Real-Time) Multicounter Automata

Geffert Viliam, Bednárová Zuzana

Fundamenta Informaticae

|

2021

|

Vol. 181, nr 2-3

99--127

EN

We show that, for automata using a finite number of counters, the minimal space that is required for accepting a nonregular language is (log n)ɛ. This is required for weak space bounds on the size of their counters, for real-time and one-way, and for nondeterministic and alternating versions of these automata. The same holds for two-way automata, independent of whether they work with strong or weak space bounds, and of whether they are deterministic, nondeterministic, or alternating. (Here ɛ denotes an arbitrarily small — but fixed-constant; the “space” refers to the values stored in the counters, rather than to the lengths of their binary representation.) On the other hand, we show that the minimal space required for accepting a nonregular language is nɛ for multicounter automata with strong space bounds, both for real-time and one-way versions, independent of whether they are deterministic, nondeterministic, or alternating, and also for real-time and one-way deterministic multicounter automata with weak space bounds. All these bounds are optimal both for unary and general nonregular languages. However, for automata equipped with only one counter, it was known that one-way nondeterministic automata cannot recognize any unary nonregular languages at all, even if the size of the counter is not restricted, while, with weak space bound log n, we present a real-time nondeterministic automaton recognizing a binary nonregular language here.

2

On State-Synchronized Automata Systems

Meduna A., Kučera J.

Schedae Informaticae

|

2015

|

Vol. 24

221--237

EN

In this paper, we introduce a new kind of automata systems, called state-synchronized automata systems of degree n. In general, they consists of n pushdown automata, referred to as their components. These systems can perform a computation step provided that the concatenation of the current states of all their components belongs to a prescribed control language. As its main result, the paper demonstrates that these systems characterize the family of recursively enumerable languages. In fact, this characterization is demostrated in both deterministic and nondeterministic versions of these systems. Restricting their components, these systems provides less computational power.

3

Regulated Nondeterminism in Pushdown Automata: The Non-Regular Case

Masopust T.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 1/2

111-124

EN

We continue the investigation of pushdown automata which are allowed to make a nondeterministic decision if and only if their pushdown content forms a string belonging to a given control language. We prove that if the control language is linear and non-regular, then the power of pushdown automata regulated in this way is increased to the power of Turing machines. From a practical point of view, however, it is inefficient to check the form of the pushdown content in each computational step. Therefore, we prove that only two checks of the pushdown content are of interest for these machines to be computationally complete. Based on this observation, we introduce and discuss a new model of regulated pushdown automata.

4

Pushdown Automata Free of Explicit Nondeterminism and an Infinite Hierarchy of Context-free Languages

Bedregal B.R.C.

Fundamenta Informaticae

|

2007

|

Vol. 81, nr 4

367-377

EN

By explicit nondeterminism degree of a pushdown automata we mean the maximal number of choices in the transitions of the automata. In this paper we will prove that each pushdown automaton has an equivalent pushdown automaton with degree 1 of explicit nondeterminism, which implies that l-moves in pda are sufficient to simulate nondeterminism. Moreover, from this normal form (i.e. pda with degree 1 of explicit nondeterminism) we can measure the amount of (implicit) nondeterminism. This measure will be used to determine a countable infinite hierarchy of context-free language subclasses, whose bottom is the class of deterministic context-free languages and the top is the class of context-free languages.

5

On Winning Conditions of High Borel Complexity in Pushdown Games

Finkel O.

Fundamenta Informaticae

|

2005

|

Vol. 66, nr 3

277--298

EN

In a recent paper [19,20] Serre has presented some decidable winning conditions [...] of arbitrarily high finite Borel complexity for games on finite graphs or on pushdown graphs. We answer in this paper several questions which were raised by Serre in [19,20]. We study classes \mathbbCn(A), defined in [20], and show that these classes are included in the class of non-ambiguous context free w-languages. Moreover from the study of a larger class \mathbbCln(A) we infer that the complements of languages in \mathbbCn(A) are also non-ambiguous context free w-languages. We conclude the study of classes \mathbbCn(A) by showing that they are neither closed under union nor under intersection. We prove also that there exists pushdown games, equipped with winning conditions in the form [...], where the winning sets are not deterministic context free languages, giving examples of winning sets which are non-deterministic non-ambiguous context free languages, inherently ambiguous context free languages, or even non context free languages.

6

Decomposing Timed Push Down Automata

Krishnan P.

Fundamenta Informaticae

|

2001

|

Vol. 45, nr 3

215-229

EN

In this paper we define a particular type of timed push down automata. We show that the emptiness problem for this class is decidable. We also present a notion of homomorphism and parallel decomposition for these automata. These notions are a generalisation of the homomorphism and decomposition via partitions for finite automata.