News Column

New Information Technology Findings from University of Milan Described (Oblivious two-way finite automata: Decidability and complexity)

August 26, 2014

By a News Reporter-Staff News Editor at Information Technology Newsweekly -- Research findings on Information Technology are discussed in a new report. According to news reporting from Milan, Italy, by VerticalNews journalists, research stated, "We investigate the descriptional complexity and decidability of obliviousness for two-way finite automata."

The news correspondents obtained a quote from the research from the University of Milan, "In particular, we consider the simulation of two-way deterministic finite automata (2DFAs) by oblivious 2DFAs, the simulation of oblivious 2DFAs by sweeping 2DFAs and one-way nondeterministic finite automata (1NFAs) as well as the simulation of sweeping 2DFAs by 1NFAs. In all cases exponential lower bounds on the number of states are obtained for languages over an alphabet with at most four letters."

According to the news reporters, the research concluded: "Finally, a procedure for deciding obliviousness of an arbitrary 2DFA is given and, moreover, the problem is shown to be PSPACE-complete."

For more information on this research see: Oblivious two-way finite automata: Decidability and complexity. Information and Computation, 2014;237():294-302. Information and Computation can be contacted at: Academic Press Inc Elsevier Science, 525 B St, Ste 1900, San Diego, CA 92101-4495, USA. (Elsevier -; Information and Computation -

Our news journalists report that additional information may be obtained by contacting M. Kutrib, University of Milan, Dipartimento Informat, I-20135 Milan, Italy. Additional authors for this research include A. Malcher and G. Pighizzini.

Keywords for this news article include: Milan, Italy, Europe, Information Technology

Our reports deliver fact-based news of research and discoveries from around the world. Copyright 2014, NewsRx LLC

For more stories covering the world of technology, please see HispanicBusiness' Tech Channel

Source: Information Technology Newsweekly

Story Tools Facebook Linkedin Twitter RSS Feed Email Alerts & Newsletters