java -Xss4m -Xmx4000000000 -jar ./plugins/org.eclipse.equinox.launcher_1.3.100.v20150511-1540.jar -data @noDefault -ultimatedata ./data -tc ../../../trunk/examples/toolchains/AutomizerCHC.xml --generate-csv --csv-dir ../../../releaseScripts/default/UAutomizer-linux/csv -s ../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf -i /storage/chc-comp/vmt-chc-benchmarks/cav12/pc_sfifo_2.smt2 -------------------------------------------------------------------------------- This is Ultimate 0.1.23-14921ce [2018-06-25 12:04:54,475 INFO L170 SettingsManager]: Resetting all preferences to default values... [2018-06-25 12:04:54,477 INFO L174 SettingsManager]: Resetting UltimateCore preferences to default values [2018-06-25 12:04:54,490 INFO L177 SettingsManager]: Ultimate Commandline Interface provides no preferences, ignoring... [2018-06-25 12:04:54,491 INFO L174 SettingsManager]: Resetting Boogie Preprocessor preferences to default values [2018-06-25 12:04:54,491 INFO L174 SettingsManager]: Resetting Boogie Procedure Inliner preferences to default values [2018-06-25 12:04:54,494 INFO L174 SettingsManager]: Resetting Abstract Interpretation preferences to default values [2018-06-25 12:04:54,497 INFO L174 SettingsManager]: Resetting LassoRanker preferences to default values [2018-06-25 12:04:54,498 INFO L174 SettingsManager]: Resetting Reaching Definitions preferences to default values [2018-06-25 12:04:54,499 INFO L174 SettingsManager]: Resetting SyntaxChecker preferences to default values [2018-06-25 12:04:54,502 INFO L177 SettingsManager]: Büchi Program Product provides no preferences, ignoring... [2018-06-25 12:04:54,502 INFO L174 SettingsManager]: Resetting LTL2Aut preferences to default values [2018-06-25 12:04:54,503 INFO L174 SettingsManager]: Resetting BlockEncodingV2 preferences to default values [2018-06-25 12:04:54,504 INFO L174 SettingsManager]: Resetting ChcToBoogie preferences to default values [2018-06-25 12:04:54,505 INFO L174 SettingsManager]: Resetting AutomataScriptInterpreter preferences to default values [2018-06-25 12:04:54,508 INFO L174 SettingsManager]: Resetting BuchiAutomizer preferences to default values [2018-06-25 12:04:54,510 INFO L174 SettingsManager]: Resetting CACSL2BoogieTranslator preferences to default values [2018-06-25 12:04:54,522 INFO L174 SettingsManager]: Resetting CodeCheck preferences to default values [2018-06-25 12:04:54,524 INFO L174 SettingsManager]: Resetting InvariantSynthesis preferences to default values [2018-06-25 12:04:54,525 INFO L174 SettingsManager]: Resetting RCFGBuilder preferences to default values [2018-06-25 12:04:54,526 INFO L174 SettingsManager]: Resetting TraceAbstraction preferences to default values [2018-06-25 12:04:54,531 INFO L177 SettingsManager]: TraceAbstractionConcurrent provides no preferences, ignoring... [2018-06-25 12:04:54,531 INFO L177 SettingsManager]: TraceAbstractionWithAFAs provides no preferences, ignoring... [2018-06-25 12:04:54,531 INFO L174 SettingsManager]: Resetting TreeAutomizer preferences to default values [2018-06-25 12:04:54,532 INFO L174 SettingsManager]: Resetting IcfgTransformer preferences to default values [2018-06-25 12:04:54,533 INFO L174 SettingsManager]: Resetting Boogie Printer preferences to default values [2018-06-25 12:04:54,533 INFO L174 SettingsManager]: Resetting ReqPrinter preferences to default values [2018-06-25 12:04:54,541 INFO L174 SettingsManager]: Resetting Witness Printer preferences to default values [2018-06-25 12:04:54,542 INFO L177 SettingsManager]: Boogie PL CUP Parser provides no preferences, ignoring... [2018-06-25 12:04:54,542 INFO L174 SettingsManager]: Resetting CDTParser preferences to default values [2018-06-25 12:04:54,543 INFO L174 SettingsManager]: Resetting PEA to Boogie preferences to default values [2018-06-25 12:04:54,543 INFO L177 SettingsManager]: AutomataScriptParser provides no preferences, ignoring... [2018-06-25 12:04:54,543 INFO L174 SettingsManager]: Resetting SmtParser preferences to default values [2018-06-25 12:04:54,549 INFO L174 SettingsManager]: Resetting Witness Parser preferences to default values [2018-06-25 12:04:54,549 INFO L181 SettingsManager]: Finished resetting all preferences to default values... [2018-06-25 12:04:54,550 INFO L98 SettingsManager]: Beginning loading settings from /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../trunk/examples/settings/chc/AutomizerCHC/AutomizerCHC_Goto.epf [2018-06-25 12:04:54,565 INFO L110 SettingsManager]: Loading preferences was successful [2018-06-25 12:04:54,565 INFO L112 SettingsManager]: Preferences different from defaults after loading the file: [2018-06-25 12:04:54,565 INFO L131 SettingsManager]: Preferences of UltimateCore differ from their defaults: [2018-06-25 12:04:54,566 INFO L133 SettingsManager]: * Logger pattern=[%d{ISO8601} %-5p]: %m%n [2018-06-25 12:04:54,567 INFO L131 SettingsManager]: Preferences of BlockEncodingV2 differ from their defaults: [2018-06-25 12:04:54,567 INFO L133 SettingsManager]: * Create parallel compositions if possible=false [2018-06-25 12:04:54,567 INFO L133 SettingsManager]: * Create interprocedural compositions=false [2018-06-25 12:04:54,567 INFO L133 SettingsManager]: * Use SBE=true [2018-06-25 12:04:54,567 INFO L131 SettingsManager]: Preferences of RCFGBuilder differ from their defaults: [2018-06-25 12:04:54,568 INFO L133 SettingsManager]: * Size of a code block=SequenceOfStatements [2018-06-25 12:04:54,571 INFO L133 SettingsManager]: * To the following directory=./dump/ [2018-06-25 12:04:54,571 INFO L133 SettingsManager]: * SMT solver=External_DefaultMode [2018-06-25 12:04:54,571 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 12:04:54,572 INFO L131 SettingsManager]: Preferences of TraceAbstraction differ from their defaults: [2018-06-25 12:04:54,572 INFO L133 SettingsManager]: * Interpolant automaton=TWOTRACK [2018-06-25 12:04:54,572 INFO L133 SettingsManager]: * Compute Interpolants along a Counterexample=FPandBP [2018-06-25 12:04:54,572 INFO L133 SettingsManager]: * Positions where we compute the Hoare Annotation=LoopsAndPotentialCycles [2018-06-25 12:04:54,572 INFO L133 SettingsManager]: * Trace refinement strategy=CAMEL [2018-06-25 12:04:54,573 INFO L133 SettingsManager]: * SMT solver=External_ModelsAndUnsatCoreMode [2018-06-25 12:04:54,573 INFO L133 SettingsManager]: * Command for external solver=z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in [2018-06-25 12:04:54,573 INFO L133 SettingsManager]: * Compute trace for counterexample result=false [2018-06-25 12:04:54,574 INFO L131 SettingsManager]: Preferences of SmtParser differ from their defaults: [2018-06-25 12:04:54,575 INFO L133 SettingsManager]: * Use TreeAutomizer as solver for the given file (assumes the file contains Horn clauses only).=true [2018-06-25 12:04:54,629 INFO ]: Repository-Root is: /tmp [2018-06-25 12:04:54,647 INFO ]: [Toolchain 1]: Applicable parser(s) successfully (re)initialized [2018-06-25 12:04:54,652 INFO ]: [Toolchain 1]: Toolchain data selected. [2018-06-25 12:04:54,653 INFO ]: Initializing SmtParser... [2018-06-25 12:04:54,654 INFO ]: SmtParser initialized [2018-06-25 12:04:54,654 INFO ]: [Toolchain 1]: Parsing single file: /storage/chc-comp/vmt-chc-benchmarks/cav12/pc_sfifo_2.smt2 [2018-06-25 12:04:54,655 INFO ]: Parsing .smt2 file as a set of Horn Clauses No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 1 with z3 SMTLIB2_COMPLIANT=true -memory:1024 -smt2 -in -t:12000 [2018-06-25 12:04:54,737 INFO ]: Executing SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/pc_sfifo_2.smt2 unknown [2018-06-25 12:04:55,189 INFO ]: Succesfully executed SMT file /storage/chc-comp/vmt-chc-benchmarks/cav12/pc_sfifo_2.smt2 [2018-06-25 12:04:55,193 INFO ]: ####################### [Toolchain 1] ####################### [2018-06-25 12:04:55,208 INFO ]: Walking toolchain with 4 elements. [2018-06-25 12:04:55,209 INFO ]: ------------------------ChcToBoogie---------------------------- [2018-06-25 12:04:55,209 INFO ]: Initializing ChcToBoogie... [2018-06-25 12:04:55,209 INFO ]: ChcToBoogie initialized [2018-06-25 12:04:55,214 INFO ]: Executing the observer ChcToBoogieObserver from plugin ChcToBoogie for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:04:55" (1/1) ... [2018-06-25 12:04:55,300 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:04:55 Unit [2018-06-25 12:04:55,300 INFO ]: ------------------------ END ChcToBoogie---------------------------- [2018-06-25 12:04:55,300 INFO ]: ------------------------Boogie Preprocessor---------------------------- [2018-06-25 12:04:55,300 INFO ]: Initializing Boogie Preprocessor... [2018-06-25 12:04:55,300 INFO ]: Boogie Preprocessor initialized [2018-06-25 12:04:55,338 INFO ]: Executing the observer EnsureBoogieModelObserver from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:04:55" (1/1) ... [2018-06-25 12:04:55,338 INFO ]: Executing the observer TypeChecker from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:04:55" (1/1) ... [2018-06-25 12:04:55,359 INFO ]: Executing the observer ConstExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:04:55" (1/1) ... [2018-06-25 12:04:55,359 INFO ]: Executing the observer StructExpander from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:04:55" (1/1) ... [2018-06-25 12:04:55,378 INFO ]: Executing the observer UnstructureCode from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:04:55" (1/1) ... [2018-06-25 12:04:55,380 INFO ]: Executing the observer FunctionInliner from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:04:55" (1/1) ... [2018-06-25 12:04:55,383 INFO ]: Executing the observer BoogieSymbolTableConstructor from plugin Boogie Preprocessor for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:04:55" (1/1) ... [2018-06-25 12:04:55,396 INFO ]: ------------------------ END Boogie Preprocessor---------------------------- [2018-06-25 12:04:55,396 INFO ]: ------------------------RCFGBuilder---------------------------- [2018-06-25 12:04:55,396 INFO ]: Initializing RCFGBuilder... [2018-06-25 12:04:55,396 INFO ]: RCFGBuilder initialized [2018-06-25 12:04:55,397 INFO ]: Executing the observer RCFGBuilderObserver from plugin RCFGBuilder for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:04:55" (1/1) ... No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 (exit command is (exit), workingDir is null) [2018-06-25 12:04:55,427 INFO ]: Specification and implementation of procedure gotoProc given in one single declaration [2018-06-25 12:04:55,427 INFO ]: Found specification of procedure gotoProc [2018-06-25 12:04:55,427 INFO ]: Found implementation of procedure gotoProc [2018-06-25 12:04:55,427 INFO ]: Specification and implementation of procedure Ultimate.START given in one single declaration [2018-06-25 12:04:55,427 INFO ]: Found specification of procedure Ultimate.START [2018-06-25 12:04:55,427 INFO ]: Found implementation of procedure Ultimate.START Waiting until toolchain timeout for monitored process 2 with z3 SMTLIB2_COMPLIANT=true -memory:2024 -smt2 -in -t:2000 [2018-06-25 12:04:55,794 INFO ]: Using library mode [2018-06-25 12:04:55,804 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:04:55 BoogieIcfgContainer [2018-06-25 12:04:55,804 INFO ]: ------------------------ END RCFGBuilder---------------------------- [2018-06-25 12:04:55,805 INFO ]: ------------------------TraceAbstraction---------------------------- [2018-06-25 12:04:55,805 INFO ]: Initializing TraceAbstraction... [2018-06-25 12:04:55,809 INFO ]: TraceAbstraction initialized [2018-06-25 12:04:55,809 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.source.smtparser OTHER 25.06 12:04:55" (1/3) ... [2018-06-25 12:04:55,810 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@8d6f261 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction OTHER 25.06 12:04:55, skipping insertion in model container [2018-06-25 12:04:55,810 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.chctoboogie AST 25.06 12:04:55" (2/3) ... [2018-06-25 12:04:55,810 INFO ]: Invalid model from TraceAbstraction for observer de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction.TraceAbstractionObserver@8d6f261 and model type de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction AST 25.06 12:04:55, skipping insertion in model container [2018-06-25 12:04:55,810 INFO ]: Executing the observer TraceAbstractionObserver from plugin TraceAbstraction for "de.uni_freiburg.informatik.ultimate.plugins.generator.rcfgbuilder CFG 25.06 12:04:55" (3/3) ... [2018-06-25 12:04:55,812 INFO ]: Analyzing ICFG de.uni_freiburg.informatik.ultimate.plugins.chctoboogie.ChcToBoogieObserver [2018-06-25 12:04:55,823 INFO ]: Automizer settings: Hoare:false NWA Interpolation:FPandBP Determinization: PREDICATE_ABSTRACTION [2018-06-25 12:04:55,832 INFO ]: Appying trace abstraction to program that has 1 error locations. [2018-06-25 12:04:55,876 INFO ]: Using default assertion order modulation [2018-06-25 12:04:55,876 INFO ]: Interprodecural is true [2018-06-25 12:04:55,877 INFO ]: Hoare is false [2018-06-25 12:04:55,877 INFO ]: Compute interpolants for FPandBP [2018-06-25 12:04:55,877 INFO ]: Backedges is TWOTRACK [2018-06-25 12:04:55,877 INFO ]: Determinization is PREDICATE_ABSTRACTION [2018-06-25 12:04:55,877 INFO ]: Difference is false [2018-06-25 12:04:55,877 INFO ]: Minimize is MINIMIZE_SEVPA [2018-06-25 12:04:55,877 INFO ]: ======== Iteration 0==of CEGAR loop == AllErrorsAtOnce======== [2018-06-25 12:04:55,891 INFO ]: Start isEmpty. Operand 10 states. [2018-06-25 12:04:55,907 INFO ]: Finished isEmpty. Found accepting run of length 8 [2018-06-25 12:04:55,907 INFO ]: Found error trace [2018-06-25 12:04:55,908 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:04:55,908 INFO ]: === Iteration 1 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:04:55,912 INFO ]: Analyzing trace with hash 1285054476, now seen corresponding path program 1 times [2018-06-25 12:04:55,913 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:04:55,914 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:04:55,946 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:04:55,946 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:04:55,946 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:04:56,015 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:04:56,153 INFO ]: Checked inductivity of 0 backedges. 0 proven. 0 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:04:56,156 INFO ]: Constructing automaton from 1 perfect and 0 imperfect interpolant sequences. [2018-06-25 12:04:56,156 INFO ]: Number of different interpolants: perfect sequences [3] imperfect sequences [] total 3 [2018-06-25 12:04:56,158 INFO ]: Interpolant automaton has 3 states [2018-06-25 12:04:56,173 INFO ]: Constructing interpolant automaton starting with 3 interpolants. [2018-06-25 12:04:56,173 INFO ]: CoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:04:56,176 INFO ]: Start difference. First operand 10 states. Second operand 3 states. [2018-06-25 12:04:56,275 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:04:56,275 INFO ]: Finished difference Result 9 states and 9 transitions. [2018-06-25 12:04:56,276 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 3 states. [2018-06-25 12:04:56,278 INFO ]: Start accepts. Automaton has 3 states. Word has length 7 [2018-06-25 12:04:56,278 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:04:56,288 INFO ]: With dead ends: 9 [2018-06-25 12:04:56,288 INFO ]: Without dead ends: 9 [2018-06-25 12:04:56,290 INFO ]: 0 DeclaredPredicates, 3 GetRequests, 2 SyntacticMatches, 0 SemanticMatches, 1 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.0s TimeCoverageRelationStatistics Valid=3, Invalid=3, Unknown=0, NotChecked=0, Total=6 [2018-06-25 12:04:56,306 INFO ]: Start minimizeSevpa. Operand 9 states. [2018-06-25 12:04:56,337 INFO ]: Finished minimizeSevpa. Reduced states from 9 to 9. [2018-06-25 12:04:56,338 INFO ]: Start removeUnreachable. Operand 9 states. [2018-06-25 12:04:56,339 INFO ]: Finished removeUnreachable. Reduced from 9 states to 9 states and 9 transitions. [2018-06-25 12:04:56,340 INFO ]: Start accepts. Automaton has 9 states and 9 transitions. Word has length 7 [2018-06-25 12:04:56,340 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:04:56,340 INFO ]: Abstraction has 9 states and 9 transitions. [2018-06-25 12:04:56,340 INFO ]: Interpolant automaton has 3 states. [2018-06-25 12:04:56,340 INFO ]: Start isEmpty. Operand 9 states and 9 transitions. [2018-06-25 12:04:56,340 INFO ]: Finished isEmpty. Found accepting run of length 9 [2018-06-25 12:04:56,340 INFO ]: Found error trace [2018-06-25 12:04:56,340 INFO ]: trace histogram [1, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:04:56,341 INFO ]: === Iteration 2 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:04:56,341 INFO ]: Analyzing trace with hash 1180100628, now seen corresponding path program 1 times [2018-06-25 12:04:56,341 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:04:56,341 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:04:56,342 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:04:56,342 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:04:56,342 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:04:56,514 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:04:56,734 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:04:56,734 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:04:56,734 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 3 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:04:56,741 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:04:56,827 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:04:56,838 INFO ]: Computing forward predicates... [2018-06-25 12:04:57,149 INFO ]: Checked inductivity of 1 backedges. 0 proven. 1 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:04:57,174 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:04:57,174 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [4, 4] total 5 [2018-06-25 12:04:57,175 INFO ]: Interpolant automaton has 5 states [2018-06-25 12:04:57,175 INFO ]: Constructing interpolant automaton starting with 5 interpolants. [2018-06-25 12:04:57,175 INFO ]: CoverageRelationStatistics Valid=9, Invalid=11, Unknown=0, NotChecked=0, Total=20 [2018-06-25 12:04:57,175 INFO ]: Start difference. First operand 9 states and 9 transitions. Second operand 5 states. [2018-06-25 12:04:57,368 WARN ]: Spent 119.00 ms on a formula simplification that was a NOOP. DAG size: 6 [2018-06-25 12:04:57,431 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:04:57,431 INFO ]: Finished difference Result 10 states and 10 transitions. [2018-06-25 12:04:57,432 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 4 states. [2018-06-25 12:04:57,432 INFO ]: Start accepts. Automaton has 5 states. Word has length 8 [2018-06-25 12:04:57,432 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:04:57,432 INFO ]: With dead ends: 10 [2018-06-25 12:04:57,432 INFO ]: Without dead ends: 10 [2018-06-25 12:04:57,433 INFO ]: 0 DeclaredPredicates, 12 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 4 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 0 ImplicationChecksByTransitivity, 0.2s TimeCoverageRelationStatistics Valid=14, Invalid=16, Unknown=0, NotChecked=0, Total=30 [2018-06-25 12:04:57,433 INFO ]: Start minimizeSevpa. Operand 10 states. [2018-06-25 12:04:57,434 INFO ]: Finished minimizeSevpa. Reduced states from 10 to 10. [2018-06-25 12:04:57,434 INFO ]: Start removeUnreachable. Operand 10 states. [2018-06-25 12:04:57,435 INFO ]: Finished removeUnreachable. Reduced from 10 states to 10 states and 10 transitions. [2018-06-25 12:04:57,435 INFO ]: Start accepts. Automaton has 10 states and 10 transitions. Word has length 8 [2018-06-25 12:04:57,435 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:04:57,435 INFO ]: Abstraction has 10 states and 10 transitions. [2018-06-25 12:04:57,435 INFO ]: Interpolant automaton has 5 states. [2018-06-25 12:04:57,435 INFO ]: Start isEmpty. Operand 10 states and 10 transitions. [2018-06-25 12:04:57,435 INFO ]: Finished isEmpty. Found accepting run of length 10 [2018-06-25 12:04:57,435 INFO ]: Found error trace [2018-06-25 12:04:57,435 INFO ]: trace histogram [2, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:04:57,435 INFO ]: === Iteration 3 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:04:57,436 INFO ]: Analyzing trace with hash -2073468660, now seen corresponding path program 2 times [2018-06-25 12:04:57,436 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:04:57,436 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:04:57,436 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:04:57,436 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:04:57,436 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:04:57,572 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:04:57,780 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:04:57,781 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:04:57,781 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 4 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:04:57,787 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST1 [2018-06-25 12:04:57,910 INFO ]: Assert order OUTSIDE_LOOP_FIRST1 issued 2 check-sat command(s) [2018-06-25 12:04:57,910 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:04:57,921 INFO ]: Computing forward predicates... [2018-06-25 12:04:58,923 WARN ]: Spent 182.00 ms on a formula simplification. DAG size of input: 17 DAG size of output: 13 [2018-06-25 12:04:58,940 INFO ]: Checked inductivity of 3 backedges. 0 proven. 3 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:04:58,974 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:04:58,974 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [5, 5] total 7 [2018-06-25 12:04:58,974 INFO ]: Interpolant automaton has 7 states [2018-06-25 12:04:58,974 INFO ]: Constructing interpolant automaton starting with 7 interpolants. [2018-06-25 12:04:58,974 INFO ]: CoverageRelationStatistics Valid=16, Invalid=26, Unknown=0, NotChecked=0, Total=42 [2018-06-25 12:04:58,974 INFO ]: Start difference. First operand 10 states and 10 transitions. Second operand 7 states. [2018-06-25 12:04:59,295 WARN ]: Spent 257.00 ms on a formula simplification. DAG size of input: 14 DAG size of output: 6 [2018-06-25 12:04:59,385 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:04:59,385 INFO ]: Finished difference Result 12 states and 12 transitions. [2018-06-25 12:04:59,386 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 6 states. [2018-06-25 12:04:59,386 INFO ]: Start accepts. Automaton has 7 states. Word has length 9 [2018-06-25 12:04:59,386 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:04:59,386 INFO ]: With dead ends: 12 [2018-06-25 12:04:59,386 INFO ]: Without dead ends: 12 [2018-06-25 12:04:59,386 INFO ]: 0 DeclaredPredicates, 15 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 7 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 4 ImplicationChecksByTransitivity, 0.7s TimeCoverageRelationStatistics Valid=30, Invalid=42, Unknown=0, NotChecked=0, Total=72 [2018-06-25 12:04:59,386 INFO ]: Start minimizeSevpa. Operand 12 states. [2018-06-25 12:04:59,388 INFO ]: Finished minimizeSevpa. Reduced states from 12 to 12. [2018-06-25 12:04:59,388 INFO ]: Start removeUnreachable. Operand 12 states. [2018-06-25 12:04:59,388 INFO ]: Finished removeUnreachable. Reduced from 12 states to 12 states and 12 transitions. [2018-06-25 12:04:59,388 INFO ]: Start accepts. Automaton has 12 states and 12 transitions. Word has length 9 [2018-06-25 12:04:59,388 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:04:59,388 INFO ]: Abstraction has 12 states and 12 transitions. [2018-06-25 12:04:59,388 INFO ]: Interpolant automaton has 7 states. [2018-06-25 12:04:59,388 INFO ]: Start isEmpty. Operand 12 states and 12 transitions. [2018-06-25 12:04:59,389 INFO ]: Finished isEmpty. Found accepting run of length 12 [2018-06-25 12:04:59,389 INFO ]: Found error trace [2018-06-25 12:04:59,389 INFO ]: trace histogram [4, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:04:59,389 INFO ]: === Iteration 4 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:04:59,389 INFO ]: Analyzing trace with hash 201204236, now seen corresponding path program 3 times [2018-06-25 12:04:59,389 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:04:59,389 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:04:59,390 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:04:59,390 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:04:59,390 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:04:59,500 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:04:59,845 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:04:59,845 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:04:59,845 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 5 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:04:59,851 INFO ]: Keeping assertion order OUTSIDE_LOOP_FIRST2 [2018-06-25 12:05:00,017 INFO ]: Assert order OUTSIDE_LOOP_FIRST2 issued 3 check-sat command(s) [2018-06-25 12:05:00,017 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:05:00,030 INFO ]: Computing forward predicates... [2018-06-25 12:05:02,177 INFO ]: Checked inductivity of 10 backedges. 0 proven. 10 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:05:02,214 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:05:02,214 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [7, 7] total 11 [2018-06-25 12:05:02,215 INFO ]: Interpolant automaton has 11 states [2018-06-25 12:05:02,215 INFO ]: Constructing interpolant automaton starting with 11 interpolants. [2018-06-25 12:05:02,215 INFO ]: CoverageRelationStatistics Valid=44, Invalid=66, Unknown=0, NotChecked=0, Total=110 [2018-06-25 12:05:02,215 INFO ]: Start difference. First operand 12 states and 12 transitions. Second operand 11 states. [2018-06-25 12:05:02,709 WARN ]: Spent 434.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 6 [2018-06-25 12:05:03,234 WARN ]: Spent 235.00 ms on a formula simplification. DAG size of input: 10 DAG size of output: 10 [2018-06-25 12:05:03,235 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:05:03,235 INFO ]: Finished difference Result 14 states and 14 transitions. [2018-06-25 12:05:03,235 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 9 states. [2018-06-25 12:05:03,235 INFO ]: Start accepts. Automaton has 11 states. Word has length 11 [2018-06-25 12:05:03,235 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:05:03,235 INFO ]: With dead ends: 14 [2018-06-25 12:05:03,235 INFO ]: Without dead ends: 14 [2018-06-25 12:05:03,236 INFO ]: 0 DeclaredPredicates, 19 GetRequests, 8 SyntacticMatches, 0 SemanticMatches, 11 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 31 ImplicationChecksByTransitivity, 1.2s TimeCoverageRelationStatistics Valid=65, Invalid=91, Unknown=0, NotChecked=0, Total=156 [2018-06-25 12:05:03,236 INFO ]: Start minimizeSevpa. Operand 14 states. [2018-06-25 12:05:03,237 INFO ]: Finished minimizeSevpa. Reduced states from 14 to 14. [2018-06-25 12:05:03,237 INFO ]: Start removeUnreachable. Operand 14 states. [2018-06-25 12:05:03,238 INFO ]: Finished removeUnreachable. Reduced from 14 states to 14 states and 14 transitions. [2018-06-25 12:05:03,238 INFO ]: Start accepts. Automaton has 14 states and 14 transitions. Word has length 11 [2018-06-25 12:05:03,238 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:05:03,238 INFO ]: Abstraction has 14 states and 14 transitions. [2018-06-25 12:05:03,238 INFO ]: Interpolant automaton has 11 states. [2018-06-25 12:05:03,238 INFO ]: Start isEmpty. Operand 14 states and 14 transitions. [2018-06-25 12:05:03,238 INFO ]: Finished isEmpty. Found accepting run of length 14 [2018-06-25 12:05:03,238 INFO ]: Found error trace [2018-06-25 12:05:03,238 INFO ]: trace histogram [6, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:05:03,239 INFO ]: === Iteration 5 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:05:03,239 INFO ]: Analyzing trace with hash 23503628, now seen corresponding path program 4 times [2018-06-25 12:05:03,239 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:05:03,239 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:05:03,240 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:05:03,240 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:05:03,240 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:05:03,426 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:05:03,817 WARN ]: Spent 104.00 ms on a formula simplification that was a NOOP. DAG size: 4 [2018-06-25 12:05:04,501 WARN ]: Spent 634.00 ms on a formula simplification. DAG size of input: 15 DAG size of output: 8 [2018-06-25 12:05:04,702 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:05:04,702 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:05:04,702 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 6 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:05:04,708 INFO ]: Keeping assertion order TERMS_WITH_SMALL_CONSTANTS_FIRST [2018-06-25 12:05:04,955 INFO ]: Assert order TERMS_WITH_SMALL_CONSTANTS_FIRST issued 0 check-sat command(s) [2018-06-25 12:05:04,955 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:05:04,967 INFO ]: Computing forward predicates... [2018-06-25 12:05:07,823 WARN ]: Spent 188.00 ms on a formula simplification. DAG size of input: 32 DAG size of output: 22 [2018-06-25 12:05:08,052 INFO ]: Checked inductivity of 21 backedges. 0 proven. 21 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:05:08,073 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:05:08,073 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [9, 9] total 14 [2018-06-25 12:05:08,073 INFO ]: Interpolant automaton has 14 states [2018-06-25 12:05:08,073 INFO ]: Constructing interpolant automaton starting with 14 interpolants. [2018-06-25 12:05:08,073 INFO ]: CoverageRelationStatistics Valid=67, Invalid=115, Unknown=0, NotChecked=0, Total=182 [2018-06-25 12:05:08,074 INFO ]: Start difference. First operand 14 states and 14 transitions. Second operand 14 states. [2018-06-25 12:05:08,487 WARN ]: Spent 130.00 ms on a formula simplification. DAG size of input: 27 DAG size of output: 27 [2018-06-25 12:05:08,488 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:05:08,488 INFO ]: Finished difference Result 15 states and 15 transitions. [2018-06-25 12:05:08,488 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 10 states. [2018-06-25 12:05:08,488 INFO ]: Start accepts. Automaton has 14 states. Word has length 13 [2018-06-25 12:05:08,488 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:05:08,489 INFO ]: With dead ends: 15 [2018-06-25 12:05:08,489 INFO ]: Without dead ends: 15 [2018-06-25 12:05:08,489 INFO ]: 0 DeclaredPredicates, 25 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 16 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 63 ImplicationChecksByTransitivity, 1.8s TimeCoverageRelationStatistics Valid=115, Invalid=191, Unknown=0, NotChecked=0, Total=306 [2018-06-25 12:05:08,489 INFO ]: Start minimizeSevpa. Operand 15 states. [2018-06-25 12:05:08,490 INFO ]: Finished minimizeSevpa. Reduced states from 15 to 15. [2018-06-25 12:05:08,490 INFO ]: Start removeUnreachable. Operand 15 states. [2018-06-25 12:05:08,491 INFO ]: Finished removeUnreachable. Reduced from 15 states to 15 states and 15 transitions. [2018-06-25 12:05:08,491 INFO ]: Start accepts. Automaton has 15 states and 15 transitions. Word has length 13 [2018-06-25 12:05:08,491 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:05:08,491 INFO ]: Abstraction has 15 states and 15 transitions. [2018-06-25 12:05:08,491 INFO ]: Interpolant automaton has 14 states. [2018-06-25 12:05:08,491 INFO ]: Start isEmpty. Operand 15 states and 15 transitions. [2018-06-25 12:05:08,492 INFO ]: Finished isEmpty. Found accepting run of length 15 [2018-06-25 12:05:08,492 INFO ]: Found error trace [2018-06-25 12:05:08,492 INFO ]: trace histogram [7, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:05:08,492 INFO ]: === Iteration 6 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:05:08,492 INFO ]: Analyzing trace with hash 726730004, now seen corresponding path program 5 times [2018-06-25 12:05:08,492 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:05:08,492 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:05:08,493 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:05:08,493 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:05:08,493 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:05:08,710 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:05:09,561 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:05:09,561 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:05:09,561 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 7 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:05:09,578 INFO ]: Keeping assertion order INSIDE_LOOP_FIRST1 [2018-06-25 12:05:09,816 INFO ]: Assert order INSIDE_LOOP_FIRST1 issued 5 check-sat command(s) [2018-06-25 12:05:09,816 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:05:09,830 INFO ]: Computing forward predicates... [2018-06-25 12:05:11,317 WARN ]: Spent 127.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 26 [2018-06-25 12:05:13,053 WARN ]: Spent 200.00 ms on a formula simplification. DAG size of input: 49 DAG size of output: 27 [2018-06-25 12:05:13,267 INFO ]: Checked inductivity of 28 backedges. 0 proven. 28 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:05:13,292 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:05:13,292 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [10, 10] total 15 [2018-06-25 12:05:13,292 INFO ]: Interpolant automaton has 15 states [2018-06-25 12:05:13,292 INFO ]: Constructing interpolant automaton starting with 15 interpolants. [2018-06-25 12:05:13,292 INFO ]: CoverageRelationStatistics Valid=77, Invalid=133, Unknown=0, NotChecked=0, Total=210 [2018-06-25 12:05:13,292 INFO ]: Start difference. First operand 15 states and 15 transitions. Second operand 15 states. [2018-06-25 12:05:13,547 WARN ]: Spent 104.00 ms on a formula simplification. DAG size of input: 38 DAG size of output: 26 [2018-06-25 12:05:13,925 WARN ]: Spent 125.00 ms on a formula simplification. DAG size of input: 31 DAG size of output: 28 [2018-06-25 12:05:13,926 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:05:13,926 INFO ]: Finished difference Result 16 states and 16 transitions. [2018-06-25 12:05:13,926 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 11 states. [2018-06-25 12:05:13,926 INFO ]: Start accepts. Automaton has 15 states. Word has length 14 [2018-06-25 12:05:13,926 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:05:13,927 INFO ]: With dead ends: 16 [2018-06-25 12:05:13,927 INFO ]: Without dead ends: 16 [2018-06-25 12:05:13,927 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 8 SyntacticMatches, 2 SemanticMatches, 19 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 87 ImplicationChecksByTransitivity, 1.6s TimeCoverageRelationStatistics Valid=165, Invalid=255, Unknown=0, NotChecked=0, Total=420 [2018-06-25 12:05:13,927 INFO ]: Start minimizeSevpa. Operand 16 states. [2018-06-25 12:05:13,931 INFO ]: Finished minimizeSevpa. Reduced states from 16 to 16. [2018-06-25 12:05:13,931 INFO ]: Start removeUnreachable. Operand 16 states. [2018-06-25 12:05:13,932 INFO ]: Finished removeUnreachable. Reduced from 16 states to 16 states and 16 transitions. [2018-06-25 12:05:13,932 INFO ]: Start accepts. Automaton has 16 states and 16 transitions. Word has length 14 [2018-06-25 12:05:13,932 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:05:13,932 INFO ]: Abstraction has 16 states and 16 transitions. [2018-06-25 12:05:13,932 INFO ]: Interpolant automaton has 15 states. [2018-06-25 12:05:13,932 INFO ]: Start isEmpty. Operand 16 states and 16 transitions. [2018-06-25 12:05:13,932 INFO ]: Finished isEmpty. Found accepting run of length 16 [2018-06-25 12:05:13,932 INFO ]: Found error trace [2018-06-25 12:05:13,932 INFO ]: trace histogram [8, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:05:13,932 INFO ]: === Iteration 7 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:05:13,932 INFO ]: Analyzing trace with hash 1051911180, now seen corresponding path program 6 times [2018-06-25 12:05:13,932 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:05:13,932 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:05:13,933 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:05:13,933 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:05:13,933 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:05:14,156 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:05:15,059 WARN ]: Spent 422.00 ms on a formula simplification. DAG size of input: 11 DAG size of output: 8 [2018-06-25 12:05:15,322 WARN ]: Spent 210.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 39 [2018-06-25 12:05:15,520 WARN ]: Spent 186.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 32 [2018-06-25 12:05:15,694 WARN ]: Spent 161.00 ms on a formula simplification. DAG size of input: 62 DAG size of output: 31 [2018-06-25 12:05:15,789 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:05:15,789 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:05:15,789 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 8 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:05:15,796 INFO ]: Keeping assertion order MIX_INSIDE_OUTSIDE [2018-06-25 12:05:16,014 INFO ]: Assert order MIX_INSIDE_OUTSIDE issued 5 check-sat command(s) [2018-06-25 12:05:16,014 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:05:16,028 INFO ]: Computing forward predicates... [2018-06-25 12:05:17,880 WARN ]: Spent 145.00 ms on a formula simplification. DAG size of input: 35 DAG size of output: 26 [2018-06-25 12:05:19,698 WARN ]: Spent 227.00 ms on a formula simplification. DAG size of input: 61 DAG size of output: 25 [2018-06-25 12:05:22,106 WARN ]: Spent 626.00 ms on a formula simplification. DAG size of input: 71 DAG size of output: 25 [2018-06-25 12:05:22,472 INFO ]: Checked inductivity of 36 backedges. 0 proven. 36 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:05:22,493 INFO ]: Constructing automaton from 0 perfect and 2 imperfect interpolant sequences. [2018-06-25 12:05:22,493 INFO ]: Number of different interpolants: perfect sequences [] imperfect sequences [11, 11] total 18 [2018-06-25 12:05:22,493 INFO ]: Interpolant automaton has 18 states [2018-06-25 12:05:22,494 INFO ]: Constructing interpolant automaton starting with 18 interpolants. [2018-06-25 12:05:22,494 INFO ]: CoverageRelationStatistics Valid=110, Invalid=196, Unknown=0, NotChecked=0, Total=306 [2018-06-25 12:05:22,494 INFO ]: Start difference. First operand 16 states and 16 transitions. Second operand 18 states. [2018-06-25 12:05:22,887 WARN ]: Spent 214.00 ms on a formula simplification. DAG size of input: 48 DAG size of output: 43 [2018-06-25 12:05:22,889 INFO ]: Subtrahend was deterministic. Have not used determinization. [2018-06-25 12:05:22,889 INFO ]: Finished difference Result 19 states and 19 transitions. [2018-06-25 12:05:22,889 INFO ]: Switched to read-only mode: deterministic interpolant automaton has 14 states. [2018-06-25 12:05:22,889 INFO ]: Start accepts. Automaton has 18 states. Word has length 15 [2018-06-25 12:05:22,889 INFO ]: Finished accepts. some prefix is accepted. [2018-06-25 12:05:22,890 INFO ]: With dead ends: 19 [2018-06-25 12:05:22,890 INFO ]: Without dead ends: 19 [2018-06-25 12:05:22,890 INFO ]: 0 DeclaredPredicates, 29 GetRequests, 8 SyntacticMatches, 1 SemanticMatches, 20 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 112 ImplicationChecksByTransitivity, 3.1s TimeCoverageRelationStatistics Valid=167, Invalid=295, Unknown=0, NotChecked=0, Total=462 [2018-06-25 12:05:22,890 INFO ]: Start minimizeSevpa. Operand 19 states. [2018-06-25 12:05:22,891 INFO ]: Finished minimizeSevpa. Reduced states from 19 to 19. [2018-06-25 12:05:22,891 INFO ]: Start removeUnreachable. Operand 19 states. [2018-06-25 12:05:22,892 INFO ]: Finished removeUnreachable. Reduced from 19 states to 19 states and 19 transitions. [2018-06-25 12:05:22,892 INFO ]: Start accepts. Automaton has 19 states and 19 transitions. Word has length 15 [2018-06-25 12:05:22,892 INFO ]: Finished accepts. word is rejected. [2018-06-25 12:05:22,892 INFO ]: Abstraction has 19 states and 19 transitions. [2018-06-25 12:05:22,892 INFO ]: Interpolant automaton has 18 states. [2018-06-25 12:05:22,892 INFO ]: Start isEmpty. Operand 19 states and 19 transitions. [2018-06-25 12:05:22,892 INFO ]: Finished isEmpty. Found accepting run of length 19 [2018-06-25 12:05:22,892 INFO ]: Found error trace [2018-06-25 12:05:22,892 INFO ]: trace histogram [11, 1, 1, 1, 1, 1, 1, 1] [2018-06-25 12:05:22,892 INFO ]: === Iteration 8 === [Ultimate.STARTErr0AssertViolationASSERT]=== [2018-06-25 12:05:22,893 INFO ]: Analyzing trace with hash -464714988, now seen corresponding path program 7 times [2018-06-25 12:05:22,893 INFO ]: Switched to mode SMTINTERPOL_TREE_INTERPOLANTS [2018-06-25 12:05:22,893 INFO ]: Using refinement strategy CamelRefinementStrategy [2018-06-25 12:05:22,893 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:05:22,893 INFO ]: Changing assertion order to NOT_INCREMENTALLY [2018-06-25 12:05:22,893 INFO ]: Craig_TreeInterpolation forces the order to NOT_INCREMENTALLY [2018-06-25 12:05:23,235 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:05:23,798 WARN ]: Spent 104.00 ms on a formula simplification that was a NOOP. DAG size: 4 [2018-06-25 12:05:24,389 WARN ]: Spent 538.00 ms on a formula simplification. DAG size of input: 21 DAG size of output: 8 [2018-06-25 12:05:24,736 WARN ]: Spent 246.00 ms on a formula simplification. DAG size of input: 42 DAG size of output: 25 [2018-06-25 12:05:24,966 WARN ]: Spent 220.00 ms on a formula simplification. DAG size of input: 64 DAG size of output: 52 [2018-06-25 12:05:25,107 WARN ]: Spent 131.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 48 [2018-06-25 12:05:25,305 WARN ]: Spent 183.00 ms on a formula simplification. DAG size of input: 57 DAG size of output: 51 [2018-06-25 12:05:25,472 WARN ]: Spent 118.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 46 [2018-06-25 12:05:25,622 WARN ]: Spent 125.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 37 [2018-06-25 12:05:25,742 WARN ]: Spent 102.00 ms on a formula simplification. DAG size of input: 55 DAG size of output: 38 [2018-06-25 12:05:25,867 INFO ]: Checked inductivity of 66 backedges. 0 proven. 66 refuted. 0 times theorem prover too weak. 0 trivial. 0 not checked. [2018-06-25 12:05:25,867 INFO ]: The current sequences of interpolants are not accepted, trying to find more. [2018-06-25 12:05:25,867 INFO ]: Switched to mode Z3_FP No working directory specified, using /storage/ultimate/releaseScripts/default/UAutomizer-linux/z3 Starting monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 (exit command is (exit), workingDir is null) Waiting until toolchain timeout for monitored process 9 with z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:05:25,873 INFO ]: Keeping assertion order NOT_INCREMENTALLY [2018-06-25 12:05:26,173 INFO ]: Conjunction of SSA is unsat [2018-06-25 12:05:26,194 INFO ]: Computing forward predicates... [2018-06-25 12:05:26,779 WARN ]: Spent 106.00 ms on a formula simplification. DAG size of input: 40 DAG size of output: 31 [2018-06-25 12:05:28,034 WARN ]: Spent 217.00 ms on a formula simplification. DAG size of input: 54 DAG size of output: 43 [2018-06-25 12:05:28,604 WARN ]: Spent 437.00 ms on a formula simplification. DAG size of input: 65 DAG size of output: 55 [2018-06-25 12:05:36,505 WARN ]: Spent 1.02 s on a formula simplification. DAG size of input: 122 DAG size of output: 69 [2018-06-25 12:05:39,245 WARN ]: Simplifying disjunction of 6400 conjuctions. This might take some time... [2018-06-25 12:05:52,152 INFO ]: Simplified to disjunction of 6400 conjuctions. [2018-06-25 12:05:53,860 WARN ]: Simplifying disjunction of 6400 conjuctions. This might take some time... Received shutdown request... [2018-06-25 12:05:55,332 INFO ]: Timeout while computing interpolants [2018-06-25 12:05:55,533 WARN ]: Destroyed unattended storables created during the last iteration: 9 z3 -smt2 -in SMTLIB2_COMPLIANT=true -t:12000 [2018-06-25 12:05:55,533 WARN ]: Verification canceled [2018-06-25 12:05:55,538 WARN ]: Timeout [2018-06-25 12:05:55,538 INFO ]: Adding new model de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction CFG 25.06 12:05:55 BoogieIcfgContainer [2018-06-25 12:05:55,538 INFO ]: ------------------------ END TraceAbstraction---------------------------- [2018-06-25 12:05:55,539 INFO ]: Toolchain (without parser) took 60344.73 ms. Allocated memory was 305.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 239.7 MB in the beginning and 861.9 MB in the end (delta: -622.2 MB). Peak memory consumption was 1.3 GB. Max. memory is 3.6 GB. [2018-06-25 12:05:55,539 INFO ]: SmtParser took 0.07 ms. Allocated memory is still 305.1 MB. Free memory is still 270.8 MB. There was no memory consumed. Max. memory is 3.6 GB. [2018-06-25 12:05:55,540 INFO ]: ChcToBoogie took 91.19 ms. Allocated memory is still 305.1 MB. Free memory was 238.7 MB in the beginning and 236.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:05:55,540 INFO ]: Boogie Preprocessor took 95.36 ms. Allocated memory is still 305.1 MB. Free memory was 236.7 MB in the beginning and 234.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:05:55,540 INFO ]: RCFGBuilder took 407.83 ms. Allocated memory is still 305.1 MB. Free memory was 234.7 MB in the beginning and 205.7 MB in the end (delta: 29.0 MB). Peak memory consumption was 29.0 MB. Max. memory is 3.6 GB. [2018-06-25 12:05:55,541 INFO ]: TraceAbstraction took 59732.46 ms. Allocated memory was 305.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 205.7 MB in the beginning and 861.9 MB in the end (delta: -656.2 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. [2018-06-25 12:05:55,543 INFO ]: ####################### End [Toolchain 1] ####################### --- Results --- * Results from de.uni_freiburg.informatik.ultimate.core: - StatisticsResult: Toolchain Benchmarks Benchmark results are: * SmtParser took 0.07 ms. Allocated memory is still 305.1 MB. Free memory is still 270.8 MB. There was no memory consumed. Max. memory is 3.6 GB. * ChcToBoogie took 91.19 ms. Allocated memory is still 305.1 MB. Free memory was 238.7 MB in the beginning and 236.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * Boogie Preprocessor took 95.36 ms. Allocated memory is still 305.1 MB. Free memory was 236.7 MB in the beginning and 234.7 MB in the end (delta: 2.0 MB). Peak memory consumption was 2.0 MB. Max. memory is 3.6 GB. * RCFGBuilder took 407.83 ms. Allocated memory is still 305.1 MB. Free memory was 234.7 MB in the beginning and 205.7 MB in the end (delta: 29.0 MB). Peak memory consumption was 29.0 MB. Max. memory is 3.6 GB. * TraceAbstraction took 59732.46 ms. Allocated memory was 305.1 MB in the beginning and 1.5 GB in the end (delta: 1.2 GB). Free memory was 205.7 MB in the beginning and 861.9 MB in the end (delta: -656.2 MB). Peak memory consumption was 1.2 GB. Max. memory is 3.6 GB. * Results from de.uni_freiburg.informatik.ultimate.plugins.generator.traceabstraction: - TimeoutResultAtElement [UNKNOWN] : Timeout (TraceAbstraction) Unable to prove that assertion always holds (line 0). Cancelled while BasicCegarLoop was analyzing trace of length 19 with TraceHistMax 11, while TraceCheckSpWp was constructing forward predicates, while PartialQuantifierElimination was eliminating quantifiers from formula with 0 quantifier alternations, while DnfTransformerHelper was XNF transformer was simplifying 6400 conjuctions. . - StatisticsResult: Ultimate Automizer benchmark data CFG has 2 procedures, 10 locations, 1 error locations. TIMEOUT Result, 59.6s OverallTime, 8 OverallIterations, 11 TraceHistogramMax, 3.2s AutomataDifference, 0.0s DeadEndRemovalTime, 0.0s HoareAnnotationTime, HoareTripleCheckerStatistics: 49 SDtfs, 9 SDslu, 177 SDs, 0 SdLazy, 83 SolverSat, 29 SolverUnsat, 0 SolverUnknown, 0 SolverNotchecked, 0.6s Time, PredicateUnifierStatistics: 0 DeclaredPredicates, 132 GetRequests, 50 SyntacticMatches, 4 SemanticMatches, 78 ConstructedPredicates, 0 IntricatePredicates, 0 DeprecatedPredicates, 297 ImplicationChecksByTransitivity, 8.9s Time, 0.0s BasicInterpolantAutomatonTime, BiggestAbstraction: size=19occurred in iteration=7, traceCheckStatistics: No data available, InterpolantConsolidationStatistics: No data available, PathInvariantsStatistics: No data available, 0/0 InterpolantCoveringCapability, TotalInterpolationStatistics: No data available, 0.0s AbstIntTime, 0 AbstIntIterations, 0 AbstIntStrong, NaN AbsIntWeakeningRatio, NaN AbsIntAvgWeakeningVarsNumRemoved, NaN AbsIntAvgWeakenedConjuncts, 0.0s DumpTime, AutomataMinimizationStatistics: 0.0s AutomataMinimizationTime, 7 MinimizatonAttempts, 0 StatesRemovedByMinimization, 0 NontrivialMinimizations, HoareAnnotationStatistics: No data available, RefinementEngineStatistics: TraceCheckStatistics: 0.3s SsaConstructionTime, 1.8s SatisfiabilityAnalysisTime, 21.1s InterpolantComputationTime, 147 NumberOfCodeBlocks, 147 NumberOfCodeBlocksAsserted, 24 NumberOfCheckSat, 134 ConstructedInterpolants, 0 QuantifiedInterpolants, 18706 SizeOfPredicates, 20 NumberOfNonLiveVariables, 3342 ConjunctsInSsa, 257 ConjunctsInUnsatCore, 13 InterpolantComputations, 1 PerfectInterpolantSequences, 0/198 InterpolantCoveringCapability, InvariantSynthesisStatistics: No data available, InterpolantConsolidationStatistics: No data available, ReuseStatistics: No data available RESULT: Ultimate could not prove your program: Timeout Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/pc_sfifo_2.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-Benchmark-0-2018-06-25_12-05-55-557.csv Written .csv to /storage/ultimate/releaseScripts/default/UAutomizer-linux/../../../releaseScripts/default/UAutomizer-linux/csv/pc_sfifo_2.smt2_AutomizerCHC_Goto.epf_AutomizerCHC.xml/Csv-TraceAbstractionBenchmarks-0-2018-06-25_12-05-55-557.csv Completed graceful shutdown