• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On Testing the Equality of Sofic Systems

Eugen Czeizler, Jarkko Kari, On Testing the Equality of Sofic Systems. In: Internal Proceedings of XIth Mons Days of Theoretical Computer Science, August 30th - September 2nd, 2006, Rennes, France, 2006.

Abstract:

In this paper we study three classes of finite automata satisfying the properties that every bi-infinite word is the label of at most one, at least one and exactly one bi-infinite path, respectively. In particular, we investigate the algorithmic complexity of testing whether or not a given finite automaton has one of these properties. Also, when restricted to the first class above, we give a polynomial time algorithm deciding whether for
two such automata, the languages of bi-infinite words obtained as labels of bi-infinite paths are equal. In terms of sofic systems, the result provides a polynomial time algorithm deciding the equality of two subshifts of finite type, given their representations as local automata.

BibTeX entry:

@INPROCEEDINGS{inpCzKa06a,
  title = {On Testing the Equality of Sofic Systems},
  booktitle = {Internal Proceedings of XIth Mons Days of Theoretical Computer Science, August 30th - September 2nd, 2006, Rennes, France},
  author = {Czeizler, Eugen and Kari, Jarkko},
  year = {2006},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication