Wyniki wyszukiwania - BazTech

1

Visibly Pushdown Automata and Transducers with Counters

Ibarra O. H.

Fundamenta Informaticae

|

2016

|

Vol. 148, nr 3/4

291--308

EN

We generalize the models of visibly pushdown automata (VPDAs) and visibly pushdown transducers (VPDTs) by equipping them with reversal-bounded counters. We show that some of the results for VPDAs and VPDTs (e.g., closure under intersection and decidability of emptiness for VPDA languages) carry over to the generalized models, but other results (e.g., determinization and closure under complementation) do not carry over, in general. We define a model that combines the desirable features of a VPDA and reversal-bounded counters, called 2- phase VPCM, and show that the deterministic and nondeterministic versions are equivalent and that the family of languages they define is closed under Boolean operations and has decidable emptiness, infiniteness, disjointness, containment, and equivalence problems. We also investigate the finite-ambiguity and finite-valuedness problems concerning these devices.

2

Semilinear Sets and Counter Machines : a Brief Survey

Ibarra O. H., Seki S.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

61--76

EN

Semilinear sets are one of the most important concepts in theoretical computer science, as illustrated by the fact that the set of nonnegative integer solutions to any system of Diophantine equations is semilinear. Parikh’s theorem enables us to represent any semilinear set as a pushdown automaton (PDA).We summarize recent results on the descriptional complexity of conversions among different representations of a semilinear set: as a vector set (conventional), a finite automaton (FA), a PDA, etc.. We also discuss semilinearity-preserving operations like union, intersection, and complement. We use Parikh’s theorem to enlarge the class of finite-state machines that can represent semilinear sets. In particular, we give a simpler proof of a known result that characterizes semilinear sets in terms of machines with reversal-bounded counters. We then investigate the power of such a machine with only one counter in the context of a long-standing conjecture about repetition on words.

3

A Survey of Results on Stateless Multicounter Automata

Ibarra O.H., Egecioglu Ö.

Fundamenta Informaticae

|

2012

|

Vol. 116, nr 1-4

129-140

EN

A stateless multicountermachine hasm-counters operating on a one-way input delimited by left and right end markers. A move of the machine depends only on the symbol under the input head and the sign pattern of the counters. An input string is accepted if, when the input head is started on the left end marker with all counters zero, themachine eventually reaches the configurationwhere the input head is on the right end marker with all the counters again zero. We bring together a number of results on stateless multicounter automata of various different types: deterministic, nondeterministic, realtime (the input head moves right at every step), or non-realtime. We investigate realtime and non-realtime machines in both deterministic and nondeterministic cases with respect to the number of counters and reversals. In addition to hierarchy results, we also consider closure properties and the connections to stateless multihead automata.

4

On the Computational Power of 1-Deterministic and Sequential P Systems

Ibarra O.H., Woodworth S., Yen H-C., Dang Z.

Fundamenta Informaticae

|

2006

|

Vol. 73, nr 1-2

133-152

EN

The original definition of P systems calls for rules to be applied in a maximally parallel fashion. However, in some cases a sequential model may be a more reasonable assumption. Here we study the computational power of different variants of sequential P systems. Initially we look at cooperative systems operating on symbol objects and without prioritized rules, but which allow membrane dissolution and bounded creation rules. We show that they are equivalent to vector addition systems and, hence, nonuniversal. When these systems are used as language acceptors, they are equivalent to communicating P systems which, in turn, are equivalent to partially blind multicounter machines. In contrast, if such cooperative systems are allowed to create an unbounded number of new membranes (i.e., with unbounded membrane creation rules) during the course of the computation, then they become universal. We then consider systems with prioritized rules operating on symbol objects. We show two types of results: there are sequential P systems that are universal and sequential P systems that are nonuniversal. In particular, both communicating and cooperative P systems are universal, even if restricted to 1-deterministic systems with one membrane. However, the reachability problem for multi-membrane catalytic P systems with prioritized rules is NP-complete and, hence, these systems are nonuniversal.